##### 连通图 - 连通图 - **连通图**指任意两个顶点之间有路径相连的[[图]] $G=(V,E)$, 或者说没有孤立点, 用于描述图中顶点之间的可达性. 一个[[无向图]]是连通图, 如果对于任意两个顶点都存在单向路径. 一个[[有向图]]是强连通图, 如果对于任意两个顶点都存在双向路径; 是弱连通图, 如果忽略方向后是连通的; 是单向连通图, 如果任意两点之间至少有一条单向路径 - 点连通度 $\kappa(G)$, 指从图中移除最少的顶点, 使图变为非连通 - 边连通度 $\lambda(G)$, 指从图中移除最少的边, 使图变为非连通 - 路径问题 - 连通分量 - 欧拉路径 - 哈密顿路径 - 最短路径算法