Section-4 Connectivity 第4节 连通 - KnowledgePoint 知识要点
知识要点
平凡图 - Trivial Graph：
只有一个节点，没有边的图。
非平凡图 - Nontrivial Graph：
有至少两个节点，一条边的图。
连通 - Connectivity：
若图(G)中从顶点(vi)到另一顶点(v_j)有路径相连，并且从(v_j)也可以移动到(v_i)，则称(v_i)和(v_j)是连通的（在无向图中，若(v_i)可以到达(v_j)，则显然(v_j)也可以到达(v_i)）。
连通图 - Connected Graph：
若图(G)中从任意两个顶点(v_i)和(v_j)都是连通的，则称图(G)是连通图。
极大连通子图 - Strong Components：
若图(G)中的子图(S)是一个连通图，且不论加入任意其他节点，都会使得子图(S)不再连通，则称(S)为极大连通子图。连通图的极大连通子图即为它自己，非连通图中存在多个极大连通子图。
连通分量（连通分支） - Connected Component，强连通分量（强连通分支） - Strongly Connected Component：
连通分量是无向图(G)中的一个极大连通子图，其中的任意节点(v_i)可以到达任意节点(v_j)，且(v_j)也可以到达(v_i)。类似的，强连通分量（强连通分支）是有向图(G)中的一个极大连通子图，其中的任意节点(v_i)可以到达任意节点(v_j)，且(v_j)也可以到达(v_i)。求强连通分量的算法有双向遍历后取交集、Tarjan算法、Kosaraju算法、Gabow算法
逆图：
图(G = (V, E))的逆图，是将其所有边都进行反向，得到(G’ = (V’, E’))。点集(V’)与(V)相同，而边集(E’)的任意边(e’ = (v, u))都在(E)中存在对应的边(e = (u, v))。逆图(G’)也称为图(G)的转置。无向图的逆图永远都是它自己。
割 - Cut：
割(C = (S, T))是图(G = (V, E))中点集V的划分，边(e = (u, v))中(u)属于子图(S)，(v)属于子图(T)，且S和T互不相交。割集(cut-set)是割的集合({ (u, v) \in E | u \in S, v \in T })，其中(S)和(T)是互不相交的子图。
点割集：
图(G = (V, E))的点集(V)中存在一个非空真子集(V_1)，满足(G)中删去(V_1)后不再连通。但对于(V_1)的任意真子集(V_2)，(G)中删去(V_2)后都仍然连通，称这样的点集(V_1)是(G)的一个点割集。非平凡的无向连通图存在点割集的充要条件是该图中至少存在两个不相邻的相异节点。
边割集：
图(G = (V, E))的边集(E)中有这样的非空真子集(E_1)，(G)中删去(E_1)后不再连通。但对于(E_1)的任意真子集(E_2)，(G)中删去(E_2)后都仍然连通，称这样的边集(E_1)是(G)的一个边割集。任何非平凡的无向连通图一定具有边割集。
点连通度：
非平凡的无向连通图(G)的所有点割集(V{cut})中的节点数量最少的那个点割集(V1)，其节点数量(k)即为图(G)的点连通度。即图(G)删除任意(k-1)个节点后都仍然能够连通，但存在一个方案（点割集）使删除(k)个节点后不连通。特别的，当(k = 2)时，即图(G)任意删除(1)个节点都仍然能够连通，但存在一个方案，删除(2)个节点后不再连通，称点连通度(k = 2)的连通分支(图)为点双连通分支。
边连通度：
非平凡的无向连通图(G)的所有边割集(E{cut})中的边数量最少的那个边割集(E_1)，其边数量(k)即为图(G)的边连通度，即图(G)删去任意(k-1)条边后都仍然能够连通，但存在一个方案(边割集)使删除k条边后不再连通。特别的，当k = 2时，即该图任意删除1条边都仍然连通，但存在一个方案使删除2条边后不再连通，称边连通度k = 2的连通分支(图)为边双连通分支。
割点：
无向图(G)中存在某个点(v_1)，删去该点后图的连通分支数量加1，即该点将原图分成两个连通分支，则称点(v_1)为无向图(G)的割点。假设删去一个割点后得到两个新的连通分支，则割点可以看作同时属于两个新连通分支，而非割点总是只属于一个连通分支。
割边（桥）：
无向图(G)中存在某条边(e_1)，删去该边后图的连通分支数量加1，即该边将原图分成两个连通分支。假设删去一条割边后得到两个新的连通分支，则割边的两端点可以看作分别属于两个新连通分支，而非割边的两端点只属于同一个连通分支。
双连通分支 - Double Connected Component：
有向图(G)的一个极大连通子图，强连通分量中的任意节点(v_i)可以到达任意节点(v_j)，且(v_j)也可以到达(v_i)。求强连通分量的算法有双向遍历后取交集、Tarjan算法、Kosaraju算法、Gabow算法