5.3 图的连通性

数学学习 · 爱知数学讲义

18
本章目录 · 1 节

本章导读

定义5.3.1:无向图中, 之间存在通路时称连通,记 ;每点规定与自身连通,可用长0通路理解。任意两点均连通的非空图称连通图,否则为非连通图。顶点间的连通关系自反、对称、传递,是等价关系。

定义5.3.2:每个连通等价类所导出的子图称连通分支,分支数记 。连通图恰有一个分支; 阶零图有 个分支,其中孤立顶点各自算一个分支。平凡图连通,顶点为空的运算结果则另行处理。

定义5.3.3:连通顶点之间长度最短的通路称短程线,长度记 ;同点距离为0,不连通距离为 。距离非负且为0当且仅当同点,满足对称性和三角不等式 。三角不等式由拼接两条通路得到一条候选路线,最短路线不会更长。这里边无权,每步长度为1;不能与后文任意边权的长度直接混用。

【例5.3.1】农夫带狗、羊、白菜渡河,每次只能带一样物品或空船往返;没有农夫看管时,狗不能与羊同岸,羊不能与白菜同岸。求最少渡河次数。

解:用四位状态 表示人、狗、羊、菜所在岸,0为南岸、1为北岸。只保留满足安全限制的状态;一条边表示农夫与至多一件同岸物品共同过河后仍安全。两个状态是否相连要同时检查船的容量、上船前同岸以及上岸后的安全,不能只看状态相差几个位置。

0000101000101011111000010100110101011111
图5.3.1:全部10个安全状态及合法渡河边;四位数字依次为人、狗、羊、菜,0南1北。

从0000到1111的最短距离为7。方案一:带羊北上,空手南返,带狗北上,带羊南返,带菜北上,空手南返,带羊北上。方案二交换狗与菜的角色,同样7次。每条合法边对应一次渡河,图中逐层搜索在第7层首次到达目标,从而证明“不仅可行,而且最少”。这里“7次”统计单程渡河,不是7个来回。

定义5.3.4:删除顶点集 后连通分支数增加,且删除其任何真子集都不增加时,称 为点割集;单元素点割集的顶点称割点。定义5.3.5:对边集作相同定义,称边割集,单条割边又称桥。定义中的“任何真子集”要求按包含关系极小,不表示必须在全图中条数最少;一个图可同时有不同大小的极小割集。

e1e2e3e4e5e6v1v2v3v4v5v6
图5.3.2:四边形v1v2v3v4外接路径v3v5v6,保留六条边的标号。

图中点割集为 ;边割集为 以及四边形四条边中任取两条的六个集合。 是桥。叶点 本身不是割点,删除它只会去掉一个叶子,不增加分支数;保留边的身份才能正确区分不同割集。

定义5.3.6:连通且非完全的无向图的点连通度 ,是点割集大小的最小值。规定 时 ,非连通图取0;平凡图通常另取0。 时称 连通图,表示少于 个顶点的删除不足以使其断开,须保留足够顶点才有通常的连通讨论。

定义5.3.7:边连通度 是最小边割集大小,非连通图取0; 时称 边连通图。对至少两顶点的连通图,删除任意少于 条边仍连通。 的边连通度为 。点连通度衡量顶点故障,边连通度衡量连接故障,两种数不能互相替代。

【例5.3.2】求教材八个图的点、边连通度并排序。

图5.3.3(a):K5,点、边连通度均为4。
图5.3.3(b):K5删去两条不共端点的边,点、边连通度均为3。
图5.3.3(c):五边形圈,点、边连通度均为2。
图5.3.3(d):五点路径,点、边连通度均为1。
图5.3.3(e):两个三角形共一个顶点,点连通度1、边连通度2。
图5.3.3(f):五边形添两条对角边,点、边连通度均为2。
图5.3.3(g):三角形与单边分属两个分支,点、边连通度均为0。
图5.3.3(h):五阶零图,点、边连通度均为0。

解: 依次为 。点连通程度为 ;边连通程度为 。若连通度为 ,它满足全部 的“至少 连通”条件,而不是只能叫作恰好一个等级。

定理5.3.1:无向简单图满足 (至少两点时使用上述惯例)。删去最小度顶点的全部关联边即可把它隔离,给出后一不等式;前一不等式表达最少顶点割不大于最少边割的标准连通性关系。对于特殊小图、环和多重边应先核对所采用的定义,不能忽视条件直接沿用简单图的全部结论。

【例5.3.3】分别给出 与 的无向简单图。

解:完全图 ()的三者同为 ;零图的三者同为0。严格不等的例子:取两个互不相交的 (),加一个新顶点 ,将它分别连接到两个完全图中的两个顶点。删除 即断开,所以 ;没有桥,但删去某一侧连向 的两条边即可断开,所以 ; 时最小度3, 时最小度4。

图5.3.4(a):两个K4通过度4的新顶点相接,1<2<3。
图5.3.4(b):两个K5通过新顶点相接,1<2<4。

定义5.3.8:有向图中, 到 有有向通路称 可达 ,记 ;规定每点可达自身。两个方向均可达称相互可达,记 ,这是顶点集上的等价关系。单方向可达只有自反、传递,一般不对称,不能当成等价关系。

定义5.3.9:有向最短通路的长度记 ,不可达时为 。仍满足非负性及三角不等式,但一般 ,不能把有向距离表强制填成对称矩阵。

定义5.3.10:基图连通称弱连通;每对顶点至少有一个方向可达称单向连通;每对顶点相互可达称强连通。强连通推出单向连通,再推出弱连通,反向一般不成立。

图5.3.5(a):强连通,任意两点均相互可达。
图5.3.5(b):单向连通但不强连通。
图5.3.5(c):弱连通,但有顶点对两个方向均不可达。

定理5.3.2:有限有向图强连通,当且仅当存在经过每个顶点至少一次的闭合有向通路;该通路允许重复顶点和边,不要求是哈密顿圈。必要性按任意顶点次序,逐一连接相邻顶点,最后连接回起点;充分性从闭合通路上任意一顶点沿方向继续行走就可到达任一其他顶点。单顶点无环情形使用长0闭合通路的约定,或单独按定义判定。

定理5.3.3:单向连通当且仅当存在经过全部顶点至少一次的有向通路,允许重复。可将相互可达的顶点缩成强连通分支,所得凝聚图为有向无圈图;单向连通使各分支按可达方向形成一条先后链,再把分支内部及分支间通路相接。反向,覆盖全部顶点的通路上,任意两点按其出现的先后就有一个方向可达。

极大路径是按本书扩路法不能继续在首尾添加新顶点的路径,不是“全图长度最长的路径”。两者不能混同;从一条路径出发不断在端点接上尚未使用的邻点,有限图中最终会停止,但可能有其他更长路径。

【例5.3.4】 的无向简单图满足 ,证明存在长度至少4的圈。

证明:可先取某个连通分支,构造极大路径 。端点 的全部邻点已在路径上;度至少3,所以除 外,还邻接两个不同的 ,可取 ,于是 。沿路径从 到 ,再由边 返回,构成长 的圈。若直接有 ,同样由路径长度至少3得到结论。

v0v1v2vkv(k+1)vtv(t+1)vl
图5.3.6:极大路径端点v0的邻点都在路径内;两条附加边指向vk、vt,且1<k<t,因此经vt返回的圈至少长4。

定义5.3.11:若顶点集可划分成两个非空部分 ,使每条边两端各在一部分,则称二部图,又称二分图或偶图。孤立顶点可按需要分到任一侧,环则立即破坏条件。若简单图中两侧所有跨部顶点对均有边,称完全二部图 ,,共有 条边。

图5.3.7(a):六点二部树,可将两部分分排绘制。
图5.3.7(b):六点偶圈的交叉画法;未标点交叉处不是顶点。
图5.3.7(c):K3,3的六边形画法。
图5.3.7(d):K2,3的五点画法。
图5.3.7(e):同一个K3,3的两排顶点画法,9条跨部边。
图5.3.7(f):同一个K2,3的两排顶点画法,6条跨部边。

定理5.3.4: 的无向图是二部图,当且仅当没有奇圈。必要性:每走一步就换到另一部,返回原点所走边数必为偶数。充分性:在每个连通分支选根,按到根的最短距离奇偶分组;若同组两点相邻,两条最短路与该边构成奇长度闭合通路,从中删去重复段可得到奇圈,矛盾。所有分支分别处理,孤立点自由分配;当图为多点零图时可把至少一个点放到另一侧,确保两部均非空。