道路与回路

道路与回路的定义
无向图的有限点边交替序列\(P=\{v_0,e_1,v_1,\cdots, e_m,v_m\}\)称为G的一条路径，m称为P的长度。
边均不相同的路径称为链，点均不相同（或者只有\(v_0=v_m\)）的路径称为道路/路。
起点与终点相同\(v_0=v_m\)的路径/链/路称为闭路径/闭链/回路。

设C是G中含顶点数大于3的一个回路，如果\(v_i,v_j\)在C中不相邻但\(e=(v_i,v_j)\in E\). 称e为C的一条弦。

Prop1. 如果\(\delta(G)\ge 2,\)则G中存在回路；如果\(\delta(G)\ge 3,\)则G中存在带弦回路。

如果两结点u,v之间存在路径，称u和v是连通的，记作\(u\sim v\). 此时u和v之间长度最短的路径称为u和v的距离，记作\(d(u,v)\). 最大距离\(d(G)\)称为G的直径。
连通是等价关系。G的连通分支数记为\(\kappa(G).\)

k-部图：如果图G的结点集V可以划分成k个非空子集\(V_1,\cdots,V_k\)，使得G的每条边的两个结点不会出现在同一个\(V_i\)中，称G是k部图。k=2时称为二部图。

Theorem 1. 无向图G是二部图当且仅当G中不包含奇回路。

对于有向图而言，如果任意两个结点之间互相可达，称为强连通图；如果任意两个结点可达，称为单连通图；如果G的基图是连通图，称为弱连通图。

Theorem 2.
有向图D是强连通图\(\Leftrightarrow\)D中存在一条闭路径包含D的所有结点；
D是单连通图\(\Leftrightarrow\)D中存在一条路径包含D的所有结点。

图G的连通性判断：
1. 代数法，定义路径矩阵\(P=(p_{i,j})_{n\times n}\), 使得\(p_{i,j}=1\)当且仅当\(v_i\)可达\(v_j\). 在布尔基意义下, P可由邻接矩阵Aa计算得到,\[P=A\lor A^2\lor\cdots A^n.\]也可用Warshall算法在\(O(n^3)\)时间内计算：对\(k,i,j\)依次循环\[P_{i,j}\leftarrow P_{i,j}\lor(P_{i,k}\land P_{k,j})\]
2. 搜索法：从某一结点出发，寻找所有与其连通的结点集，如深度优先/广度优先。

最短道路
寻找赋权图\(G=(V,E,w)\)中任意两结点的最短路径。
1. Dijkstra算法
从\(u_0\)出发，维护探索集S并初始化为\(S=\{u_0\}\).
每次寻找S以外的点到\(u_0\)距离最短，加入S中并更新\(u_0\)到S外其他点的距离。

2. Floyd算法
初始化距离矩阵\(D=(d(i,j))_{n\times n}\)和前趋矩阵\(P=(p(i,j))_{n\times n}\)其中\(p(i,j)=i\).
对\(k=1...n\)操作\(d(i,j) = d(i,k) + d(k,j)\)若此操作可以减小\(d(i,j)\), 并更新前趋\(p(i,j) = p(k,j)\).

    所属分类：离散数学     发表于2022-05-20