其它图

主讲教师

李辉

欧拉图

图论起源于18世纪, 1736年瑞士数学家欧拉(Euler)发表了图论的第一篇论文“哥尼斯堡七桥问题”.

图的环游: 指经过图的每条边至少一次的回路.

欧拉环游: 是经过每条边恰好一次的回路.一个图若包含欧拉环游, 则称为欧拉图(Eulerian graph).

类似地, 经过图的每条边的路径称为图的欧拉路径(Enler trail).

这些术语之所以以欧拉命名, 是因为1736年欧拉解决了著名的哥尼斯堡七桥问题.

哥尼斯堡七桥问题(The Konigsberg Bridge Problem, https://nrich.maths.org/2484)

定义: 对于图\(G\), 经过图中每条边一次且仅一次, 并且经过所有结点的一条路径(通路), 称为该图的一条欧拉路径(欧拉通路), 具有欧拉路径的图称为半欧拉图.

经过图中每条边一次且仅一次并且经过所有结点的一条回路, 称为该图的一条欧拉回路, 具有欧拉回路的图称为欧拉图.

显然, 欧拉路径是经过图中所有边的简单路径, 欧拉回路是经过图中所有边的简单回路.

半欧拉图对比欧拉图: 一个是路径, 一个是回路.

(a)有欧拉回路, 该图是欧拉图, 一条这样的欧拉回路是abcda (a, b, c, d, a); (b)有欧拉通路, 一条这样的欧拉通路是(b, c, d, a, b, d); (c)没有欧拉通路也没有欧拉回路.

一个图是否存在欧拉路径(回路)问题, 等价于该图是否可以一笔画出问题.

笔不离纸, 每条边只画一次不许重复, 画完该图, 若笔又回到出发点, 该图为欧拉图;若画完该图, 笔回不到出发点, 该图为半欧拉图.

(a)可以一笔画出后回到出发点; (b)可以一笔画出, 但笔不能回到出发点; (c)根本不能一笔画出所有边.

对于图中是否存在欧拉路径或欧拉回路, 存在一个简单的判别方法, 大数学家欧拉在解决哥尼斯堡七桥问题时发现了该方法并且给出了证明.

定理: 设无向图\(G={\langle}V, E{\rangle}\)是连通的, 则

\(G\)中存在欧拉回路, 当且仅当\(G\)中所有结点的度均为偶数.
\(G\)中存在欧拉路径但不存在欧拉回路, 当且仅当\(G\)中恰有两个结点的度为奇数.

例: 判断图(a)、(b)和(c)是否是存在欧拉通路和欧拉回路.

解: 图(a), \(d(a)=d(b)=d(c)=d(d)=2\), 所有结点度均为偶数, 故存在欧拉回路;

图(b), \(d(a)=d(c)=2, d(b)=d(d)=3\), 有两个结点度为奇数, 故存在欧拉路径;

图(c), \(d(a)=d(b)=d(d)=d(e)=3, d(c)=2\), 有4个结点度为奇数, 不存在欧拉路径和欧拉回路.

七桥问题:

\(d(A)=5\)

\(d(B)=3\)

\(d(C)=3\)

\(d(D)=3\)

4个结点度均为奇数, 故不存在欧拉回路, 七桥问题无解.

例: 如图是某街道图形.洒水车从\(A\)点出发执行洒水任务. 试问是否存在一条洒水线路, 使洒水车通过所有街道且不重复而最后回到车库\(B\).

解: 此为题即为求图中是否存在\(A\)到\(B\)的欧拉路径.由于只有\(A\)、\(B\)为奇数度结点, 因此这样的洒水路线是存在的, 如:

\(ACDEFBGCFGAB\)

或

\(AGFEDCFBGCAB.\)

例: “两只蚂蚁比赛问题”.两只蚂蚁甲、乙分别处在图\(G\)的结点\(A\)、\(B\)处, 并设图中各边长度相等. 甲提出同乙比赛: 从它们所在的结点出发, 走过图中所有边最后回到结点\(C\)处. 如果它们速度相同, 问谁最先到达目的地？

解: 图\(G\)中, 仅有两个奇数度结点\(B\)、\(C\), 因此存在欧拉路径, 其起点和终点为\(B\)和\(C\). 蚂蚁乙由\(B\)走到\(C\)处可以走一条欧拉路径, 边数为9. 而蚂蚁甲要想走完图中所有边到达\(C\), 至少要先走一条边到达\(B\), 再走一条欧拉路径, 它至少要走10条边到达\(C\), 所以乙必胜.

例: 一个公园的平面图如图所示, 能不能使游人走遍每一条路不重复？入口和出口应设在哪儿？

解: \(H\)点和\(B\)点是奇数度结点, 其余结点度数均为偶数, 所以入口出口设在\(H\)和\(B\)处, 游人走遍每一条路不重复.

实际上, 欧拉路径是经过图中所有边的路径中最短的路径; 欧拉回路是经过图中所有边的回路中最短的回路.

例: 如图所示的街道, 是否存在一条投递路线, 使邮递员从\(a\)出发经过所有街道一次再回到邮局\(a\)？

全部结点的度均为偶数, 故存在欧拉回路, 即所求投递路线. 例如: afjklgcbdfhkigedhieba.

Fleury算法求欧拉回路

定理: 设Fleury(弗罗莱)算法: 设欧拉图\[G={\langle}V, E{\rangle}\]

1 任取\(v_0{\in}V\), 令\(P_0=v_0\);

2 设路径\(p_i = v_0e_1v_1e_2{\cdots}e_iv_i\)已经走过, 按下面方法从\(E\)-\(\{e_1, e_2, e_3, {\cdots}, e_i\}\)中选取\(e_{i+1}\):

\(e_{i+1}\)与\(v_i\)关联;
除非没有别的边可以走, 否则\(e_{i+1}\)不应该为 \(G_i = G-\{e_1, e_2, e_3, {\cdots}, e_i\}\)中的桥.

3 当2不能再进行时, 算法停止.

例: 采用Fleury算法求如\(G={\langle}V, E{\rangle}\)的一条欧拉回路.

解: 任取\(v_0{\in}V\).

选\(e_1\), 得\(v_0e_1v_1\)

选\(e_2\), 得\(v_0e_1v_1 e_2v_2\)

选\(e_6\), 得\(v_0e_1v_1 e_2v_2 e_6v_0\)

选\(e_3\), 得\(v_0e_1v_1 e_2v_2 e_5v_0 e_3v_2\)

选\(e_4\), 得\(v_0e_1v_1 e_2v_2 e_5v_0 e_3v_2 e_4v_3\)

选\(e_5\), 得\(v_0e_1v_1 e_2v_2 e_5v_0 e_3v_2 e_4v_3 e_5v_0\)

定理: 设\(G\)是非平凡的欧拉图当且仅当\(G\)是连通的, 且为若干个边不重复的简单回路的并.

定理: 设有向图\(G={\langle}V, E{\rangle}\)是弱连通的, 则:

\(G\)中存在欧拉回路, 当且仅当\(G\)中每个结点的入度等于出度.
\(G\)中存在欧拉路径但不存在欧拉回路, 当且仅当\(G\)中除两个结点外, 其余结点的入度等于出度, 而除外的两个结点中, 一个结点的入度比出度大1, 另一个结点的入度比出度小1.

例: 判断图是否是存在欧拉路径和欧拉回路.

解: 对于\(G\), \[d^+(v_1)=1, d^-(v_1)=1\] \[d^+(v_2)=2, d^-(v_2)=1\] \[d^+(v_3)=1, d^-(v_3)=1\] \[d^+(v_4)=1, d^-(v_4)=1\] \[d^+(v_5)=1, d^-(v_2)=2\] 故存在欧拉路径, 例如\(v_2v_3v_4v_5v_2v_1v_5\).

例: 判断下图是否是存在欧拉通路或欧拉回路.

解: 对于\(G\), \[d^+(a)=d^-(a)=1 , d^+(b)=d^-(b)=1\] \[d^+(c)=d^-(c)=1, d^+(d)=d^-(d)=1\] \[d^+(e)=d^-(e)=2, d^+(f)=d^-(f)=2\] \[d^+(g)=d^-(g)=2, d^+(h)=d^-(h)=2\]

故存在欧拉回路.

哈密尔顿图

哈密尔顿图源于一种数学游戏，它是由爱尔兰数学家哈密尔顿于1859年提出的“周游世界问题”:

用一个正十二面体的20个顶点代表世界上20个著名城市，要求沿着正十二面体的棱，从一个城市出发，经过每个城市恰好一次，然后回到出发点.

与哥尼斯堡七桥问题不同的是，不久，哈密尔顿先生就收到来自世界各地的解决周游世界问题的答案.

定义: 对于图\(G\), 经过图中每个结点一次且仅一次的一条路径, 称为该图的一条哈密尔顿路径. 经过图中每个结点一次且仅一次的一条回路, 称为该图的一条哈密尔顿回路, 具有哈密尔顿回路的图称为哈密尔顿图.

如图:

(a)中存在哈密尔顿通路和哈密尔顿回路, 一条哈密尔顿通路是\((a, b, c, d)\), 一条哈密尔顿回路是\((a, b, c, d, a)\).

(b)中也存在哈密尔顿通路, 一条哈密尔顿通路是\((1, 2, 3, 4, 5)\), 无哈密尔顿回路.

正十二面体中存在哈密尔顿回路, 它是可以周游的, 例如: \(1\, 2\, 3\, 10\, 12\, 9\, 4\, 3\, 8\, 11\, {\cdots}20\, 6\).

与欧拉图情形不同, 到目前为止, 判断哈密尔顿回路非平凡的充要条件尚不清楚.

事实上, 这是图论尚未解决的主要问题之一.

但有一些关于哈密尔顿图的充分条件或必要条件.

定理: 设无向图\(G={\langle}V, E{\rangle}\)是哈密尔顿图, 则对于结点集\(V\)的每个非空真子集\(S\)均有: \[p(G-S){\leq}|S|\] 其中\(p(G-S)\)是\(G-S\)的连通分支数.

证明: 因为\(G\)是哈密尔顿图, 故\(G\)中存在哈密尔顿回路.

设\(C\)是这样的一条哈密尔顿回路, 显然有\(p(C-S){\leq}|S|\).

而\(C-S\)是\(G-S\)的生成子图, 因此\(p(G-S){\leq}p(C-S)\), 于是有\(p(G-S){\leq}|S|\).

此定理给出了无向图是哈密尔顿图的一个必要条件, 但并非充分条件.

推论: 设无向图\(G={\langle}V, E{\rangle}\)存在哈密尔顿路径, 则对于结点集\(V\)的每个非空真子集\(S\)均有: \[p(G-S){\leq}|S|+1\] 其中\(p(G-S)\)是\(G-S\)的连通分支数.

图中的彼得森(Petersen)图, 它满足 \[p(G-S){\leq}|S|,\] 然而该图不是哈密尔顿图.

但是, 不满足此条件的图一定不是哈密尔顿图, 因此可以利用它来证明某些图不是哈密尔顿图.

例: 如图\(G\)所示的无向图:

取\(S=\{v_1, v_4\}\), 则:

\(p(G-S)=3>|S|=2.\)

因而此无向图不是哈密尔顿图.

它存在哈密尔顿路径, 例如: \(v_2v_4v_7v_1v_3v_8v_6v_5\).

例: 如图\(G\)所示的无向图是否是哈密尔顿图或存在哈密尔顿路径？

解: 取\(S=\{a, f\}\), 则: \[p(G-S)=4>|S|=2\] 不满足

\(p(G-S){\leq}|S|\)

或

\(p(G-S){\leq}|S|+1.\)

因此, 这个无向图不是哈密尔顿图, 也不存在哈密尔顿路径.

例: 图\(G\)如图所示, 判断是否是哈密尔顿图或存在哈密尔顿路径？

解: 设取\(V_1=\{a, g, h, i, c\}\), \(V_2=\{b, e, f, j, k, d\}\), 则\(p(G-V_1)=|V_2|=6>|V_1|=5\), 可知\(G\)不是哈密尔顿图.

但存在哈密尔顿路径.

\(baegjckhfid\)是一条哈密尔顿了路径.

例: 以下图中, 哪些是哈密尔顿图, 哪些存在哈密尔顿路径？

解:

对\(G_1\), 设取\(V_1=\{a, b, c, d, e\}\), 则: \(p(G_1-V_1)=7>|V_1|=5\).

可知\(G_1\)不是哈密尔顿图, 也不存在哈密尔顿路径.

对\(G_2\), 设取\(V_1=\{b, e, h\}\), 从图中删除\(V_1\)得4个连通分支, 则\(p(G_2-V_1)=4>|V_1|=3\).

可知\(G_2\)不是哈密尔顿图.

但存在哈密尔顿路径.

定理: 设图\(G\)是有\(n\)个结点的简单无向图, 如果\(G\)的每一对结点的度数之和大于等于\(n-1\), 则\(G\)中存在哈密尔顿路径(通路).

定理给出的只是充分条件, 不是必要条件.

例如, 图\(G_1\)中, 任意两个结点度之和\({\geq}n-1=3\), 故存在哈密尔顿路径;图\(G_2\)中, 虽然任意两结点的度之和为\(4<n-1=5\), 但图中还是存在哈密尔顿通路.

定理: 设图\(G\)是有\(n(n{\geq}3)\)个结点的简单无向图, 如果\(G\)的每一对结点的度数之和大于等于\(n\), 则\(G\)为哈密尔顿图.

定理给出的只是充分条件, 不是必要条件.

例如, 图\(G_1\)中, 任意两个结点度之和\({\geq}n=4\), 故存在哈密尔顿回路; 图\(G_2\)中, 虽然任意两结点的度之和为\(4<n=6\), 但图中还是存在哈密尔顿回路.

推论: 设图\(G\)是有\(n(n{\geq}3)\)个结点的简单无向图, 如果\(G\)中每个结点的度均大于等于\(n/2\), 则\(G\)为哈密尔顿图.

证明: 因为\(G\)中每个结点的度均大于等于\(n/2\), 所以任意两个结点的度之和大于等于\(n\), 根据前述定理, 因此\(G\)为哈密尔顿图.

定理: \(n(n{\geq}3)\)个结点的无向完全图是哈密尔顿图.

定理: 设图\(G\)是有\(n(n{\geq}2)\)个结点的有向图, 如果所有的有向边均用无向边代替, 所得无向图含有生成子图\(K_n\), 则有向图\(G\)存在哈密尔顿通路.

中国邮递员问题 (Chinese postman problem, CPP)

邮递员带着要分发的邮件从邮局出发, 经过要分发的每个街道, 送完邮件后又返回邮局.如果他必须至少一次走过他管辖范围内的每一条街道, 如何选择投递路线, 使邮递员走尽可能少的路程.

这个问题是由我国数学家管梅谷先生(山东师范大学数学系教授)在1962年首次提出的, 因此在国际上称之为中国邮递员问题.

在社会活动中, 经常会遇到这样的问题，如: 每天在大街小巷的洒水车、网购的各种快递都需要解决一个行走的最短路程问题.

定义: 设\(G={\langle}V, E{\rangle}\)是无向图, 若对于\(G\)的每条边\(e\), 均有一个正实数\(W(e)\)与之对应, 则称\(G\)为无向赋权图或无向带权图, 简称赋权图或带权图, 称\(W(e)\)为边\(e\)的权.

规定:对\(v_i{\in}V\), 则\(W(v_i, v_i)=0\); 对\(v_i, v_j{\in}V\), 若\((v_i, v_j){\notin}E\), 则\(W(v_i, v_j)=\infty\).

赋权图记为\(G={\langle}V, E, W{\rangle}\).在赋权图中, 边的权也称为边的长度, 这时一条通路的长度是指这条通路中各边的长度之和.

结点\(v_i\)和\(v_j\)间的最短通路的长度称为\(v_i\)到\(v_j\)的距离, 记为\(d[v_i, v_j\)].

在实际应用中, 常常需要寻找某类具有最小权的子图, 也就是求给定两结点间的最短通路, 即所谓的最短通路问题.

显然两结点间的最短通路一定是简单通路.

结合图论的术语, CPP问题是在一个连通的赋权图\(G={\langle}V, E{\rangle}\)中, 要寻找一条回路, 使该回路包含\(G\)中的每条边至少一次, 且该回路的权数最小.

也就是说要从包含\(G\)的每条边的回路中找一条权数最小的回路.

如果\(G\)是欧拉图, 则很容易由弗罗莱算法求出一个欧拉回路. 但是若\(G\)不是欧拉图, 即存在奇度数的顶点, 所求回路必然要重复通过某些边, 则中国邮递员问题的解决要困难得多.

这个问题存在有效的解决方法, 其中最直观的方法之一是: 把图中的某些边复制成两条边, 然后在所求图中找一条欧拉回路, 即Edmonds-Johnson算法:

1 若\(G\)不含奇数度结点, 则任意欧拉回路就是问题解.

2 若含有\(2k(k>0)\)个奇数度结点, 则先求出其中任何两点间的最短路径, 然后再在其中找出k条路径\(p_1, p_2, {\cdots}, p_k\), 使得满足如下条件:

任何\(p_i\)和\(p_j (i{\neq}j)\) 没有相同的起点和终点;
在所有满足(1)的\(k\)条最短路径集合中, \(p_1, p_2, {\cdots}, p_k\)的总长度最短.

3 根据2中求出的\(k\)条最短路径\(p_1, p_2, {\cdots}, p_k\), 在原图\(G\)中复制所有出现在这条路径上的边, 设所得图为\(G^\prime\).

4 构造\(G^\prime\)的欧拉回路, 即得到中国邮递员问题的解.

例: 如图所示, 求中国邮递员问题的一个解.

解:

1 因\(G\)含有奇数度结点. 所以:

2 \(G\)中有\(2k=4(k=2)\)个奇数度结点\(v_1, v_2, v_3, v_5\), 这4个点间的距离: \[d[v_1, v_2]=3, d[v_1, v_3]=5, d[v_1, v_5]=4, \] \[d[v_2, v_3]=2, d[v_2, v_5]=3, d[v_3, v_5]=4.\]

各路径: \[v_1v_2(3), v_3v_5(4){\longmapsto}7\] \[v_1v_3(5), v_2v_5(3){\longmapsto}8\] \[v_1v_5(4), v_2v_3(2){\longmapsto}6\] 所以两条最短:\(p_1=v_1v_7v_5, p_2=v_2v_3\)

\[p_1=v_1v_7v_5, p_2=v_2v_3.\] 在\(G\)中添加这两条路径上的所有边, 得\(G^\prime\).

3 构造\(G^\prime\)的任一欧拉回路就是中国邮递员问题的解.

最短通路问题 (Shortest Path Problem)

在实际应用中, 常常需要寻找某类具有最小权的子图, 即所谓的最短通路问题. 1959年, 荷兰数学家、计算机科学家Dijkstra(狄克斯屈拉)给出了一个在赋权图中求任意两结点间最短通路的算法: Dijkstra算法.

Dijkstra算法:

\(L\)表示结点\(u\)到各个结点的通路的长度的当前最小值, \(S\)表示已求得最短通路的结点集合.

初始化.令\(u=v_1\), \(L(u)=0\), \(L(v_i)=\infty(i=2, 3\cdots, n)\), \(S=\phi\);
如果\(|S|=n\), 转(5);
从\(V-S\)中选取具有最小值\(L(v)\)的\(v\), 令\(S=S\cup\{v\}\);
对所有\(x{\in}V-S\), 令\(L(x)=\min\{L(x), L(v)+w(v, x)\}\), 转(2);
输出\(u\)到其他各个结点的最短通路的长度\(L(v)\).

用标号算法求v1出发到v8, 使总费用最小的旅行路线.棕色是永久标号;黑色是临时标号.

v1出发到v8总费用最小为12，旅行路线为v1, v3, v2, v5, v8.

\[ \begin{array}{ccc} 步 & 集合P & L_1 & L_2 & L_3 & L_4 & L_5 & L_6 & L_7 & L_8 & L_9\\ 0 & \phi & 0 & \infty & \infty & \infty & \infty & \infty & \infty & \infty & \infty\\ 1 & 1 & & 6 & 3 & 1 & \infty & \infty & \infty & \infty & \infty\\ 2 & 14 & & 6 & 3 & & \infty & 11 & \infty & \infty & \infty\\ 3 & 13 & & 5 & & & \infty & 11 & \infty & \infty & \infty\\ 4 & 132 & & & & & 6 & 11 & \infty & \infty & \infty\\ 5 & 1325 & & & & & & 10 & 9 & 12 & \infty\\ 6 & 13257 & & & & & & 10 & & 12 & \infty\\ 7 & 13256 & & & & & & & & 12 & \infty\\ 8 & 13258 & & & & & & & & \\ \end{array} \]

132表示{\(v1\), \(v3\), \(v2\)}, \(L_1\)表示\(L(v1)\).

二分图

二分图又称二部图(偶图), 是图论中的一种特殊模型.

定义: 给定无向图\(G={\langle}V, E{\rangle}\), 若能将结点集\(V\)划分成两个非空子集\(V_1\)和\(V_2\), 满足\(V_1{\cup}V_2=V, V_1{\cap}V_2=\phi\), 且对\(G\)中的任意一条边\((v_i, v_j)\), 有\(v_i{\in}V_1, v_j{\in}V_2\), 则称\(G\)是二分图(Bipartite graph), 常记为\(G={\langle}V_1, E, V_2{\rangle}\), \(V_1\)和\(V_2\)称为\(G\)的互补结点子集.

若\(V_1\)的每个结点与\(V_2\)的每个结点都有且仅有一条边相连结, 则称\(G\)是完全二分图, 常记为\(k_{m, n}\), 其中\(m=|V_1|\), \(n=|V_2|\).

定理: 无向图\(G={\langle}V, E{\rangle}\)是二分图, 当且仅当\(G\)至少有两个结点, 且所有回路的长度均为偶数.

例: 如图, 图\(G\)是否是二分图？

解: \(G\)是二分图, 因为图中所有回路的长度均为偶数.

\[V_1=\{v_1, v_3, v_6, v_8\}\] \[V_2=\{v_2, v_4, v_5, v_7\}\]

例: 如图所示, \(G\)是二分图吗？

解: \(G\)不是二分图, 因为图中存在长度为奇数的回路.

例: 一摆渡人欲将一只狼、一头羊、一蓝菜从河西渡过河到河东, 由于船小，一次只能带一物过河，并且狼与羊、羊与菜不能独处, 给出渡河方案.

解: 用四维0-1向量来表示人、狼、羊和菜的在西岸状态, 在西岸则对应分量取1, 否则取0.共\(2^4=16\)种状态: (0, 0, 0, 0), (0, 0, 0, 1), (0, 0, 1, 0), \({\cdots}\), (1, 1, 1, 0), (1, 1, 1, 1)

16种状态(人, 狼, 羊, 菜): (0, 0, 0, 0), (0, 0, 0, 1), (0, 0, 1, 0), \({\cdots}\), (1, 1, 1, 0), (1, 1, 1, 1).

由题设, 状态(0, 1, 1, 0), (0, 0, 1, 1), (0, 1, 1, 1)是不允许的; 相反的状态(1, 0, 0, 1), (1, 1, 0, 0), (1, 0, 0, 0)也是不允许的.

允许的状态: (1, 1, 1, 1), (1, 1, 1, 0), (1, 1, 0, 1), (1, 0, 1, 1), (1, 0, 1, 0), (0, 1, 0, 1), (0, 0, 0, 1), (0, 0, 1, 0), (0, 1, 0, 0), (0, 0, 0, 0).

问题: 如何从状态(1, 1, 1, 1)转移到(0, 0, 0, 0)？

允许状态向量:

人在西岸: (1, 1, 1, 1), (1, 1, 1, 0), (1, 1, 0, 1), (1, 0, 1, 1), (1, 0, 1, 0)

人在东岸: (0, 1, 0, 1), (0, 0, 0, 1), (0, 0, 1, 0), (0, 1, 0, 0), (0, 0, 0, 0)

将10个结点分别记为\(A_1, A_2, {\cdots}, A_{5}\)(上排从左到右)、\(A_6, A_7, {\cdots}, A_{10}\)(下排从左到右).

过河问题是否能解？即图中\(A_1\)到\(A_{10}\)是否连通？有几种不同的解法？即\(A_1\)到\(A_{10}\)有几条不同的路径？最快的解决方案是什么？即\(A_1\)到\(A_{10}\)最短路径是哪条？

方法:从\((1, 1, 1, 1)\)开始, 沿关联边到达没有到达的邻接点, 到\((0, 0, 0, 0)\)终止, 得到有向图即是.

从图中可得两条路径:

\[A_1A_6A_3A_7A_2A_8A_5A_{10}\] \[A_1A_6A_3A_9A_4A_8A_5A_{10}\]

农夫带羊过河; 农夫返回; 农夫带狼过河; 农夫带羊返回; 农夫带菜过河; 农夫返回; 农夫带羊过河.

定义: 设\(G={\langle}V_1, E, V_2{\rangle}\)是二分图, 若存在\(M{\subseteq}E\), 使得\(M\)中任意两条边均不邻接, 则称\(M\)为\(G\)的一个匹配, 并称\(G\)的所有匹配中边数最多的匹配为最大匹配.

如果\(V_1\)中每一个结点都是匹配\(M\)中边的端点, 那么称\(M\)为\(V_1\)-完全匹配. 如果\(V_2\)中每一个结点都是匹配\(M\)中边的端点, 那么称\(M\)为\(V_2\)-完全匹配.

若\(M\)既是\(V_1\)-完全匹配又是\(V_2\)-完全匹配, 称\(M\)为\(G\)的完全(美)匹配.

\(V_1\)-完全匹配、\(V_2\)-完全匹配和完全匹配都是最大匹配, 但反之不真.

最大匹配总是存在但未必唯一.

例: 在(a)中, {\((v_1, v_3)\), \((v_2, v_4)\)}是一个\(V_1\)-完全匹配, 也是最大匹配;

在(b)中, {\((v_1, v_4)\), \((v_2, v_5)\), \((v_3, v_6)\)}是一个\(V_1\)-完全匹配, 又是\(V_2\)-完全匹配, 从而也是完全匹配.

匹配不一定是唯一的: 如图, 在(a)中, {\((v_1, v_4)\), \((v_2, v_5)\)}是一个\(V_1\)-完全匹配, 也是最大匹配;

在(b)中, {\((v_1, v_5)\), \((v_2, v_4)\), \((v_3, v_6)\)}是一个\(V_1\)-完全匹配, 又是\(V_2\)-完全匹配, 从而也是完全匹配.

定理: 霍尔(婚姻)定理 设\(G={\langle}V_1, E, V_2{\rangle}\)是二分图, \(G\)有\(V_1\)-完全匹配的充要条件是: 对任意\(S{\subseteq}V_1\)有 \[|N(S)|{\geq}|S|\] 其中\(|N(S)|\)为所有与\(S\)中结点邻接的结点组成的集合.

(或:设\(G={\langle}V_1, E, V_2{\rangle}\)是二分图, \(G\)有\(V_1\)-完全匹配当且仅当\(V_1\)中的任意\(k\)个结点至少与\(V_2\)中的\(k\)个结点邻接, \(k=1, 2, 3\), \({\cdots}\), \(|V_1|\), \(|V_1|{\leq}|V_2|\).) 这一条件称为“相异性条件”.

如图, \(G_1\)不存在\(V_1\)-完全匹配, \(G_2\)存在\(V_1\)-完全匹配.

求证: 若二分图\(G={\langle}V_1, E, V_2{\rangle}\)是\(k\)-正则图, 则\(G\)中有完全匹配.

证明: 由于\(G={\langle}V_1, E, V_2{\rangle}\)是\(k\)-正则图, 因此有
\[k{\cdot}|V_1|=|E|=k{\cdot}|V_2|\] 从而得\(|V_1|=|V_2|\).

设任意\(S{\subseteq}V_1, N(S)\)为\(S\)的邻接结点集, \(E_1\)为关联\(S\)中结点的边的集合, \(E_2\)为关联\(N(S)\)中结点的边的集合, 可知\(E_1{\subseteq}E_2\), 于是 \[k{\cdot}|N(S)|=|E_2|{\geq}|E_1|=k{\cdot}|S|\] 得\(|N(S)|{\geq}|S|\), 因此\(G\)有\(V_1\)-完全匹配\(M\).

又由于\(|V_1|=|V_2|\), 显然\(M\)也是\(V_2\)-完全匹配, 故\(M\)是\(G\)的完全匹配, 即\(G\)中有完全匹配.

\(G_1\)是3-正则图, 则\(G_1\)中有完全匹配;

\(G_2\)是2-正则图, 则\(G_2\)中有完全匹配.

定理: (\(t\)条件)设\(G={\langle}V_1, E, V_2{\rangle}\)是二分图, 若存在正整数\(t\), 满足:

对于\(V_1\)中的每个结点, 至少有\(t\)条与其关联的边;
对于\(V_2\)中的每个结点, 至多有\(t\)条与其关联的边.

则\(G\)中必有\(V_1\)-完全匹配.

也即: \(V_1\)中结点度数的最小值大于等于\(V_2\)中结点度数的最大值. \(t\)条件是充分条件, 但不是必要条件.

判断以下二分图是否存在\(V_1\)-完全匹配？其中互补结点子集:

\(V_1=\{v_1, v_2, v_3\}\),

\(V_2=\{v_4, v_5, v_6, v_7, v_8, v_9, v_10, v_{11}, v_{12}\}\).

解: 取\(t=3\), 显然此二分图满足”\(t\)条件”, 故\(G\)中有\(V_1\)-完全匹配.

例: 判断如下图\(G\)是否是二分图, 是否存在\(V_1\)-完全匹配？

解: 是二分图, 互补结点子集:

\(V_1=\{v_1, v_3, v_6\}\),

\(V_2=\{v_2, v_4, v_5, v_7\}\).

虽然此二分图不满足”\(t\)条件”, 但\(G\)中有\(V_1\)-完全匹配.

例: 判断如下图是否是二分图, 是否存在完全匹配？

解: 是二分图.

例: 今派四位教师李方、郭倩、王刚和刘伟去教授离散数学、数据结构、操作系统和编译原理四门课程.

已知李方熟悉数据结构和操作系统; 郭倩熟悉离散数学和编译原理; 王刚熟悉离散数学、数据结构和操作系统; 刘伟只熟悉操作系统.

问能否拟定一种方案, 使得每人都教自己熟悉的课程, 并且每门课都有人教?

解: 以\(x_1, x_2, x_3\)和\(x_4\)分别表示四位教师李方、郭倩、王刚和刘伟, 以\(y_1, y_2, y_3\)和\(y_4\)分别表示离散数学、数据结构、操作系统和编译原理四门课程.

令\(V_1=\{x_1, x_2, x_3, x_4\}\), \(V_2=\{y_1, y_2, y_3, y_4\}\),

\(E=\{(x_i, y_j)|x_i熟悉y_j, i, j=1, 2, 3, 4\}\),

作无向图\(G={\langle}V, E{\rangle}\). 显然, 这是一个二分图, 原问题转化为在二分图\(G\)中寻找一个完全匹配.

图中存在完全匹配\(\{(x_1, y_2), (x_2, y_4), (x_3, y_1), (x_4, y_3)\}\)

按这个完全匹配可安排:

李方教数据结构, 郭倩教编译原理, 王刚教离散数学, 刘伟教操作系统.

平面图的基本概念

一个图画再平面上能否做到边不交叉的问题即图的可平面化问题, 在单面印刷电路板、集成电路布线、通讯、交通、城市建筑等方面都有广泛应用.

定义: 设\(G={\langle}V, E{\rangle}\)是无向图, 若能把\(G\)画在平面上, 且使得任何两条边除了端点外没有其他的交点, 则称\(G\)为平面图, 图的这种画法称为图的平面表示(平面嵌入). 否则称\(G\)为非平面图.

例: 如图所示, (a)是平面图, (b)是平面图.

有些图从表面上看不出是否是平面图, 但通过同构变换可以转化成平面图, 这类图是可平面化的, 称为可平面图, 也是平面图.

例: 如图(a)所示, 是可平面图, (b)是其平面嵌入.

如图(1)和(3), 它是平面图.

(2)是(1)的平面嵌入; (4)是(3)的平面嵌入.

但是有些图不是平面图, 也不能平面化.

例: 如图所示, \(K_5\)不是平面图; \(K_{3, 3}\)也不是平面图.

\(k_5\)和\(k_{3, 3}\)称为库拉托夫斯基图, 它们有一些共同点:

它们都是正则图(\(k_5\)是4-正则图, \(k_{3, 3}\)是3-正则图);
去掉一条边后它们都是平面图;
\(k_{3, 3}\)是边数最少的非平面图, \(k_5\)是结点数最少的非平面图, 它们都是最基本的非平面图.

平面图的面

定义: 设\(G\)是连通平面图, 由\(G\)的边将\(G\)所在的平面划分成若干个内部不包含有结点和边的区域, 每个区域称为\(G\)的一个面.

其中面积有限的区域称为有限面或内部面, 面积无限的区域称为无限面或外部面.

每个面的所有边围成的回路称为该面的边界, 它的长度称为面的度(次数), 一个面f的度记为\(deg(f)\). 若两个面的边界至少有一个公共边, 称这两个面为邻接面.

连通平面图常记为\(G={\langle}V, E, F{\rangle}\), 其中\(F\)是图中所有面的集合.

例: 如图所示为一平面图.

它共有3个面\(f_3, f_4, f_0\), 其中\(f_0\)为无限面, 其余有限面.

\(f_3\)的边界是\((j, h, i, j)\), 度为3;

\(f_4\)的边界是\((j, k, h, j)\), 度为3;

\(f_0\)的边界是\((j, k, h, i, j)\), 度为4.

例: 如图所示为一平面图, 它共有5个面\(f_1, f_2, f_3, f_4\)和\(f_0\), 其中\(f_0\)为无限面, 其余为有限面.

\(f_1\)的边界是\((v_1, v_2, v_3, v_2, v_4, v_1)\), 度为5;

\(f_2\)的边界是\((v_8, v_8)\), 度为1;

\(f_3\)的边界是\((v_5, v_6, v_8, v_5)\), 度为3;

\(f_4\)的边界是\((v_6, v_7, v_8, v_6)\), 度为3;

\(f_0\)的边界是\((v_1, v_2, v_4, v_5, v_6, v_7, v_8, v_8, v_5, v_4, v_1)\), 度为10.

定理: 在连通平面图\(G={\langle}V, E, F{\rangle}\)中, 所有面的度数之和等于边数的两倍, 即\(=2|E|\).

证明: 因为连通平面图的任何一条边, 或者是作为两个面的公共边在两个面的边界中各出现一次, 或者是只在一个面的边界中出现两次.

无论是两种情况的哪一种, 在计算各面的度数时均被计算两次, 故所有面的度数之和等于边数的两倍.

定义: 设简单图\(G\)是平面图, 若在\(G\)中任意两个不邻接的结点之间添加边, 所得到的图均为非平面图, 则称\(G\)是极大平面图.

极大平面图一定是连通的, 且每个面的边界都是由基本回路构成.

无向完全图\(k_3\)和\(k_4\)都是极大平面图.

定理: 对于结点数大于等于3的简单连通平面图\(G\), \(G\)为极大平面图当且仅当\(G\)中各面的度均为3.

例: 图中, 哪些是极大平面图？

只有右边的图是极大平面图, 因为只有该图每个面的度为3.

定义: 设\(G\)是非平面图, 若删除\(G\)中任意一条边, 所得到的图均为平面图, 则称\(G\)是极小非平面图.

极小非平面图一定简单图.

\(K_5\)和\(K_{3, 3}\)都是极小非平面图.

定理: (欧拉公式)设\(G\)是有\(n\)个结点、\(m\)条边和\(r\)个面的连通平面图, 则\(n-m+r=2\).

例: 图中\[n-m+r=4-5+3=2.\]

例: 设连通平面图\(G\)有20个结点, 每个结点的度都是3, 试问这个平面图的平面表示把平面分割成多少个面？

解: 设\(G={\langle}V, E{\rangle}={\langle}n, m{\rangle}\), 则\(n=20\), 因此所有结点的度之和\({\sum}d(v)=3n=3{\times}20=60\). 又由于结点的度之和\({\sum}d(v)=2m=60\), 即\(m=30\).

由欧拉公式, 有面数为: \[r=2-n+m=2-20+30=12\] 根据欧拉公式可以得到平面图的一些不等式.

定理: 设\(G\)是有\(n\)个结点和\(m\)条边连通的平面图, 若每个面的度均大于等于\(l\), 此处\(l{\geq}3\), 则: \[m{\leq}\frac{l(n-2)}{l-2}\] 证明: 设\(G\)是有r个面, 则由题设可知:

\[ 2m=\sum_f{deg(f){\geq}l{\cdot}r} \]

又根据欧拉公式\(n-m+r=2\), 有\(r=2-n+m\). 所以, \(2m{\geq}l(2-n+m)\).

再由\(l{\geq}3\), 得\(m{\leq}\frac{l(n-2)}{l-2}\).

定理: 设\(G\)是有\(n\)个结点和\(m\)条边连通的简单平面图, 若\(n{\geq}3\), 则\(m{\leq}3n-6\).

显然这是一个平面图必要条件, 但不是充分条件.

求证: \(k_5\)是非平面图.

证明: 反证法. 设\(k_5\)是平面图, 由于\(k_5\)的结点数\(n=5\), 边数\(m=10\), 因此应有\(10{\leq}3{\times}5-6=9\), 显然这是不成立的, 因此假设不成立, \(k_5\)是非平面图.

对\(k_{3, 3}\)而言, 却无法判断是否是平面图. 因为: \(k_{3, 3}\)的结点数\(n=6\), 边数\(m=9\), 有: \[m=9{\leq}3n-6=3{\times}6-6=12, \] 即满足\(m{\leq}3n-6\), 因此不能断定\(k_{3, 3}\)是否是平面图.

定理: 设\(G\)是有\(n\)个结点和\(m\)条边连通的简单平面图, 若\(n{\geq}3\)且\(G\)中没有长度为3的回路, 则: \[m{\leq}2n-4.\]

证明: 设\(G\)有\(r\)个面.

由于\(G\)中没有长度为3的回路, 因此\(G\)的每个面的度至少为4, 这样就有\(2m{\geq}4r\), 即\(r{\leq}m/2\).

由欧拉公式\(n-m+r=2\), 有: \(m-n+2=r{\leq}m/2\). 因此, \(m{\leq}2n-4\).

显然这也是必要条件, 但不是充分条件.

例: 证明\(k_{3, 3}\)是非平面图.

证明: 反证法.设\(k_{3, 3}\)是平面图.

由于\(k_{3, 3}\)的结点数\(n=6\), 边数\(m=9\), 且没有长度为3的回路, 则应有\(m{\leq}2n-4\), 即\(9{\leq}2{\times}6-4=8\), 显然这是不成立的.

因此假设不成立, 故\(k_{3, 3}\)是非平面图.

定理: 设\(G\)是简单平面图, 则\(G\)的最小度\(\delta(G){\leq}5\).

证明: 若结点数\(n{\leq}6\), 结论显然成立.

若结点数\(n{\geq}7\)时, 用反证法.

假设\(\delta(G){\geq}6\), 由握手定理可知:

\[2m=\sum_{v{\in}V}d(v){\geq}6n.\]

因而\(m{\geq}3n\), 这与\(m{\leq}3n-6\)矛盾. 所以假设不成立, 即\(G\)的最小度\(\delta(G){\leq}5\).

这个定理与图的着色理论相关.

欧拉公式推论:设平面图\(G\)有\(k(k{\geq}2)\)个连通分支, 则: \(n-m+r=k+1\). 其中, \(n, m, r\)分别是\(G\)的结点数, 边数和面数.

证明: 设第\(i\)个连通分支有\(n_i\)个结点、\(m_i\)条边和\(r_i\)个面, 对各连通分支用欧拉公式: \[n_i-m_i+r_i=2\] 求和: \((n_1+n_2+{\cdots}n_k)-(m_1+m_2+{\cdots}m_k)+(r_1+r_2+{\cdots}r_k)=2k\).

注意到 \(r=r_1+{\cdots}+r_k-(k-1)\)(外部面仅有一个), 得: \(n-m+r=k+1\).

定理: 设平面图\(G\)有\(k(k{\geq}2)\)个连通分支, 各面的度数至少为\(l(l{\geq}3)\), 则边数\(m\)与结点数\(n\)有以下关系:

\[ m{\leq}\frac{l}{l-2}(n-k-1) \]

平面图的判别

寻找判断平面图的充要条件持续了几十年, 直到1930年, 库拉托夫斯基(Kazimierz Kuratowski)率先给出了平面图的一个十分简洁的特征, 解决了这个问题.

插入或删除度为2的结点:

如图\(G\)所示, 可以看出在给定图\(G\)的边上, 插入新的度为2的结点, 使一条边分成两条边;

或者删除度为2的结点, 使两条边合成为一条边, 这些都不会影响图的平面性.

定义: 给定两个无向图\(G_1\)和\(G_2\), 若\(G_1\)和\(G_2\)是同构的, 或通过反复在一些边上插入或删除度为2的结点后变成同构的, 则称\(G_1\)和\(G_2\)同胚.

图的平面性在图的同胚意义下保持不变, 即一个平面图插入或删除任意多个2度结点得到的图还是平面图.

定理(库拉托夫斯基定理I): 一个无向图\(G\)是平面图当且仅当\(G\)中不含同胚于\(k_5\)或\(k_{3, 3}\)的子图.

定义: 在一个无向图\(G\)中,

去掉\(G\)中相邻两个结点\(u, v\)及它们所关联的边\((u, v)\),

用一个新的结点\(w\)取代, 使\(w\)邻接于\(u, v\)邻接的一切结点,

对\(G\)作一系列这种变换得新图\(G^{\prime}\), \(G^{\prime}\)称为\(G\)的基本浓缩.

定理(库拉托夫斯基定理II):

一个无向图\(G\)是平面图, 当且仅当\(G\)中没有可以浓缩到\(k_5\)或\(k_{3, 3}\)的子图.

对偶图

定义: 设\(G\)是平面图, 用如下方法构造的无向图\(G^*\)称为\(G\)的对偶图.

在\(G\)的每一个面\(f_i\)中任取一点\(v_i^*\)作为\(G^*\)的结点.
若在\(G\)中, 面\(f_i\)和\(f_j\)的边界有公共边\(e_k\), 则连接对应结点\(v_i^*\)和\(v_j^*\), 得\(G^*\)的边\(e_k^*\)与\(e_k\)相交, 且不与\(G\)的其它边相交.
若在\(G\)中, \(e_k\)只出现在一个面\(f_i\)的边界上, 从相应的结点\(v_i^*\)到\(v_i^*\)做\(G^*\)的环\(e_k^*\)与\(e_k\)相交, 且不与\(G\)的其它边相交.

定理: 每个连通平面图\(G\)都有其对偶图, 且一个连通平面图\(G\)的对偶图\(G^*\)也是连通平面图. 另外, \(G^*\)也是\(G\)的对偶图.

同构的平面图, 它们的对偶图不一定是同构的.

例如图中的两图是同构的, 它们的对偶图不同构.

因为左图的最大度是6, 右图的最大度是5.

定理: 一个连通平面图\(G\)的结点数\(n\)、边数\(m\)和面数\(r\)与其对偶图\(G^*\)的结点数\(n^*\)、边数\(m^*\)和面数\(r^*\)有如下关系: \[n=r^*, m=m^*, r=n^*\]

如图, \[n=r^*=5\] \[m=m^*=7\] \[r=n^*=4\]

定义: 若平面图\(G\)的对偶图\(G^*\)同构于\(G\), 则称\(G\)是自对偶图.

如图所示的图就是自对偶图.

定义: 由\(n\)(\(n{\geq}3\))个结点\(v_1, v_2, {\cdots}, v_n\), 以及边\((v_1, v_2), (v_2, v_3), {\cdots}, (v_{n-1}, v_n), (v_n, v_1)\)组成的图称为圈图, 记作\(C_n\).

例: 如图所示就是圈图.

图\(G\)所包含结点的个数称为图\(G\)的阶.

定义: 在圈图\(C_{n-1}\)内放置一个点, 使这个点与\(C_{n-1}\)上的所有结点均邻接, 所得\(n\)阶简单图称为n阶轮图. 记为\(W_n\).

\(n\)为奇数的轮图称为奇阶轮图; \(n\)为偶数的轮图称为偶阶轮图.

定理: 轮图都是自对偶图.

平面图的着色

一百多年前, 英国格色里(Guthrie)提出了用四种颜色即对地图着色的猜想. 1976年美国数学家阿佩尔和黑肯用电子计算机证明了四色猜想是成立的, 这就是著名的“四色定理”.

地图着色问题: 用\(m\)种颜色为地图着色, 使得地图上的每一个区域着一种颜色, 且相邻区域颜色不同, 最少需要多少种颜色？

地图的着色问题: 在一张地图上进行着色, 使得着色的颜色数最少.

显然, 可以把地图看做是一个平面图, 而地图的着色问题可以用平面图的着色来刻画.

由于平面图存在对偶图, 所以对平面图的着色问题可以转化为对其对偶图结点的着色问题.

图的着色分类:

结点着色: 用\(m\)种颜色为图的每个结点着色, 要求每个结点着一种颜色, 并使相邻两结点有着不同的颜色.

边着色: 用\(m\)种颜色为图的每条边着色, 要求每条边着一种颜色, 并使相邻两条边有着不同的颜色.

定义: 如果能用k种颜色对图\(G\)的结点进行着色, 使得任何邻接的结点都有不同的颜色, 则称\(G\)是k-可着色的.

如果\(G\)是\(k\)-可着色的, 而不是(\(k-1\))-可着色的, 则称\(G\)是k色的或\(G\)的色数为k, 记为\(x(G)\).

如图所示,

\(G_1\)的色数\(x(G_1)=2\),

\(G_2\)的色数\(x(G_2)=4\).

几种特殊图的着色:

\(G\)是零图, 着色数\(x(G)=1\)
\(G\)是\(n\)个结点的完全图, 着色数\(x(G)=n\)
\(G\)是\(n\)个结点的回路, 则着色数\(x(G)=2\)(\(n\)为偶数); 着色数\(x(G)=3\)(\(n\)为奇数).
\(G\)是非平凡树, 着色数\(x(G)=2\)
\(G\)是二分图, 着色数\(x(G)=2\)

例: 证明完全图\(K_n\)的着色数\(x(K_n)=n\).

证明: 因为完全图的每两个结点都是邻接, 因此没有两个结点可以着相同的颜色, 故\(n\)个结点的着色数不少于\(n\); 又\(n\)个结点的着色数至多为\(n\), 故\(x(K_n)=n.\)

定理: (五色定理)对于任何平面图\(G\), 有\(x(G){\leq}5\).

定理: (四色定理)对于任何平面图\(G\), 有\(x(G){\leq}4\). 四色定理只适用于平面图, 非平面图可以有任意大的着色数.

树

无向树及其性质

定义: 连通的不含基本回路的无向图称为无向树, 简称为树, 常用\(T\)表示. 若一个无向图的每个连通分支都是树, 则称该图为森林.

在树中, 度为1的结点称为树叶, 度大于1的结点称为分支点.

如图, (a)、(b)和(c)都是树, (d)是森林.

(b)称为平凡树, 它的结点度为0, 只有在平凡树中, 才有度为0的结点.

在任何其它树中, 结点的度都大于等于1.

定理: 设\(G={\langle}n, m{\rangle}\)为无向图, 则下列各命题是等价的, 都可作为无向树的定义.

\(G\)是连通的且不含基本回路.
\(G\)无基本回路且\(m=n-1\).
\(G\)是连通的且\(m=n-1\).
\(G\)无基本回路, 但在任意两个不邻接的结点间添加一条边, 则恰产生一条基本回路.
\(G\)是连通的, 但删除\(G\)中任意一条边, 所得到的图都非连通的.
\(G\)的任意两个不同结点之间恰有一条基本通路.

生成树

定义: 若无向图\(G\)的生成子图\(T\)是树, 则称\(T\)是\(G\)的生成树.

\(T\)中的边称为树枝, 图\(G\)的不在\(T\)中的边称为弦.

生成树不一定唯一, 如图\(T_1\)所示, 是\(G\)的另一棵生成树.

定理: 任一连通的无向图都至少有一棵生成树.

证明: 设\(G\)是连通的无向图. 若\(G\)中无基本回路, 则\(G\)本身就是一棵生成树.

若\(G\)中有基本回路, 则删除回路中的一条边得图\(G_1\). 若\(G_1\)中无基本回路, 则\(G_1\)就是一棵生成树.

若\(G_1\)中有基本回路, 则再删除回路中的一条边得图\(G_2\), \({\cdots}\)

如此继续下去, 直到图中不再有基本回路为止, 这时所得到的连通的无基本回路且与图\(G\)有相同结点集的图就是\(G\)的生成树.

一个连通无向图\(G\), 如果它本身就是树, 则它的生成树是唯一的, 就是\(G\)本身.

一个连通无向图\(G\)本身不是树, 它的生成树就不唯一了, 但所有的连通无向图都存在生成树.

例: 如图所示, 在(a)中相继删除边\(a, d, h\)和\(i\)得生成树(b), 相继删除边\(e, g, h\)和\(i\)得生成树(c).

定理: 设\(G={\langle}n, m{\rangle}\)是无向连通图, 则\(m{\geq}n-1\).

定理: 设\(G={\langle}n, m{\rangle}\)是无向连通图, \(T\)是\(G\)的生成树, \(T^{\prime}\)是\(T\)的余树, 则\(T^{\prime}\)中的边数为\(m-n+1\).

最小生成树

定义: 设\(G={\langle}V, E, W{\rangle}\)为连通赋权图, \(W\)为\(E\)到非负实数集的函数.

设\(T\)为\(G\)的生成树, 则\(T\)中各边权之和称为生成树\(T\)的权, 记为\(W(T)\). 权最小的生成树称为最小生成树(Minimum Spanning Tree).

例: 如图(a)为赋权图, (b)为(a)的最小生成树

例: 设\(G\)中结点表示城市, 边表示城市之间道路, 边权表示道路的长度.

如果要用通信线路把这些城市联系起来, 要求沿道路架设线路时, 所用的线路最短.

就是要求一棵生成树, 使该生成树是图\(G\)中所有生成树中边权之和最小.

最小生成树不一定是唯一的.

如图(a)为赋权图, (b)为(c)均是(a)的最小生成树.

“避圈法”(Kruskal算法)求最小生成树:

设连通赋权图\(G={\langle}n, m{\rangle}\), 构造图\(T\):

\(T\)的结点与\(G\)相同.
在\(G\)中选取权值尽可能小的边\(e_1\)添加到\(T\)中.
设已经添加边\(e_1, e_2, {\cdots}, e_k\)到\(T\)中. 在\(G\)中选取不同于\(e_1, e_2, {\cdots}, e_k\)的边\(e_{k+1}\), 使\(e_1, e_2, {\cdots}, e_k, e_{k+1}\)不形成基本回路且使\(e_{k+1}\)权值尽可能小, 将\(e_{k+1}\)添加到\(T\)中.

如此继续下去, 直到\(T\)中添加了\(n-1\)条边\(e_1, e_2, {\cdots}, e_{n-1}\)为止.

定理: 设\(G={\langle}V, E, W{\rangle}\)为连通的赋权图, 由Kruskal算法所得到的\(T\)是\(G\)的最小生成树.

根树及其应用

定义: 一个有向图, 若略去边的方向后所得到的无向图是一棵树, 则称这个有向图为有向树, 记为\(T\).

例: 图(a)和图(b)都是有向树.

定义: 只有一个结点的入度为0, 而其余结点的入度都为1的有向树称为根树.

在根树中, 入度为0的结点称为树根;

入度为1、出度为0的结点称为树叶;

入度为1、出度不为0的结点称为内点;

内点和树根统称为分支点.

例如在如图所示的根树中:

\(v_1\)是树根, \(v_2, v_3, v_4, v_7\)是内点,

\(v_5, v_6, v_8, v_9, v_10, v_{11}, v_{12}\)是树叶.

定义: 在根树中, 从树根到某一结点的通路长度称为该结点的级(或层).

结点中, 层的最大值称为树高.

例如在如图所示的根树中, \(v_1\)的级为0,

\(v_2, v_3, v_4\)的级为1,

\(v_5, v_6, v_7, v_8, v_9, v_10\)的级为2,

\(v_{11}, v_{12}\)的级为3, 整个树的树高为3.

定义: 在根树\(T\)中, 若从结点\(u\)到结点\(v\)有一条边, 则称\(v\)为\(u\)的儿子(子结点), \(u\)为\(v\)的父亲(父结点).

若从结点\(u\)到结点\(w\)有通路, 则称\(u\)是\(w\)的祖先, \(w\)是\(u\)的后代.

有相同父亲的结点称为兄弟.

任一结点\(u\)及其后代导出的子图称为以\(u\)为根的子树.

例: 如图所示, \(v_8\)为\(v_4\)的儿子,

\(v_4\)为\(v_8\)的父亲,

\(v_3\)为\(v_{12}\)的祖先,

\(v_{12}\)为\(v_3\)的后代,

\(v_5\)和\(v_6\)为兄弟.

(b)是以\(v_3\)为根的(a)的子树.

根树的图示可以是任意的, 树根可以画在根树的任意位置.

但一般习惯将树根画在上端, 树叶画在下端, 这样有向边的箭头方向就都是指向下方.

因而可以省略全部箭头, 后面均采用此种方法.

(a) 是根树的自然表示法; (b) 表示树从它的根向下生长; (c) 去掉了所有边的方向.

定义: 若在根树中规定了每一层上结点的次序, 这样的根树称为有序树.

一般地, 在画有序树时, 同一层上结点的次序为从左到右, 也可以用边的次序来代替结点的次序.

例: 以下两棵树, 作为根树他们是同构的, 但作为有序树, 它们是不同的.

例: 如图所示是编译原理中表示表达式:

\[a{\times}b-(d+e/f){\times}c\]

的根树, 这是一棵有序树.

定义: 设\(T\)是一棵根树:

若\(T\)的每个分支点至多有\(m\)个儿子, 则称\(T\)为m叉树(m叉树); 若\(T\)的每个分支点都恰有\(m\)个儿子, 则称\(T\)为正则m叉树.
若\(m\)叉树\(T\)是有序树, 则称\(T\)为m叉有序树; 若正则\(m\)叉树\(T\)是有序树, 则称\(T\)为正则m叉有序树.
若\(T\)是正则\(m\)叉树, 且所有树叶的层数均相同, 则称\(T\)为满m叉树.

定义: 在正则二叉有序树中, 对于每个分支点的两个儿子, 左边的儿子称为左儿子; 右边的儿子称为右儿子.

根处在一个分支点左儿子处的子树称为该分支点的左子树; 根处在一个分支点右儿子处的子树称为该分支点的右子树.

对一般的二叉有序树也采用这种说法, 但需要注意的是:

若二叉有序树的某个分支点只有一个儿子, 则它既可以作为左儿子也可以作为右儿子, 视情况而定.

二叉有序树有着十分重要的应用, 任何\(m\)元有序树都可以用对应的二叉有序树来表示, 即可对任一棵\(m\)元有序树作适当的变换, 使之转化为一棵二叉有序树.

一棵\(m\)元有序树转化为二叉有序树的方法是: 对于\(m\)元有序树, 每个分支点的第一个儿子作为该分支点的左儿子, 而该分支点的右侧兄弟(若存在的话)作为分支点的右儿子.

如图, (a)为4元有序树, (b)为转化的二叉有序树, (c)为按照根树的约定图示法重画的二叉有序树.

用类似的方法, 可以用二叉有序树来表示\(m\)元有序树组成的森林(称为有序森林).

从\(m\)元有序树转化为二叉有序树可以看出, 任何一棵与\(m\)元有序树对应的二叉有序树, 其树根的右子树为空.

这样可按如下的方法将有序森林转化为一棵二叉有序树:

将有序森林中的每棵\(m\)元有序树表示为二叉有序树, 将它们的树根以父子方式连接起来, 左为父右为子.

二叉树的一个重要应用: 最优二叉树.

定义: 设\(T\)是一棵二叉树, 共有\(t\)片树叶, 若对这\(t\)片树叶分别赋权\(w_1, w_2, {\cdots}, w_t\), 则称\(T\)为赋权二叉树.

定义: 设\(T\)是赋权二叉树, 赋权为\(w_1, w_2, {\cdots}, w_t\), 称 \[w(t)=\sum_{i=1}^tw_il(w_i)\] 为赋权二叉树\(T\)的权, 其中\(l(w_i)\)是赋权\(w_i\)的树叶的层.

在所有带有\(t\)个叶结点, 分别赋权\(w_1, w_2, {\cdots}, w_t\)的赋权二叉树中, 权最小的那棵称为最优二叉树或哈夫曼(Huffman)树.

定理: 设\(T\)是赋权\(w_1, w_2, {\cdots}, w_t\)的最优二叉树, 且\(w_1{\leq}w_2{\leq}{\cdots}{\leq}w_t\), 则一定可使赋权\(w_1\)和\(w_2\)的树叶为兄弟, 且它们在所有结点中层最大.

定理: 设\(T\)是赋权\[w_1+w_2, w_3, {\cdots}, w_t\]的最优二叉树, 且\(w_1{\leq}w_2{\leq}{\cdots}{\leq}w_t\). 若使赋权\(w_1+w_2\)的树叶产生两个儿子, 分别赋权\(w_1\)和\(w_2\), 则得到树\(T^{\prime}\)是赋权\(w_1, w_2, {\cdots}, w_t\)的最优二叉树.

根据上述两定理可知, 要求含\(t\)个权的最优二叉树, 可归结为求含\(t-1\)个权的最优二叉树, 进而可归结为求含\(t-2\)个权的最优二叉树, \({\cdots}\), 最后可归结为求含2个权的最优二叉树(这是唯一的).

给定权\(w_1, w_2, {\cdots}, w_t\), \(w_1{\leq}w_2{\leq}{\cdots}{\leq}w_t\), 构造一棵赋权\(w_1, w_2, {\cdots}, w_t\)的最优二叉树算法如下:

令\(S=\{w_1, w_2, {\cdots}, w_t\}\).
在\(S\)中选取两个值最小的权\(w_i\)和\(w_j\), 画结点\(v_i\)和\(v_j\), 分别赋权\(w_i\)和\(w_j\). 画\(v_i\)和\(v_j\)的父结点\(v\), 赋权为\(w_i+w_j\), 连结\(v_i\)和\(v\)及\(v_j\)和\(v\).
令\(S{\leftarrow}(S-\{w_i, w_j\}){\cup}\{w_i+w_j\}\)
若\(S\)只有一个元素, 则停止, 所构造的图就是最优二叉树. 否则转到(2).

例: 构造一棵赋权\(2, 4, 6, 8, 10, 11\)的最优二叉树\(T\), 并求\(W(T)\).

解: 赋权\(\{2, 4, 6, 8, 10, 11\}\)的最优二叉树构造过程如图所示.

(a) {6, 6, 8, 10, 11} (b) {8, 10, 11, 12} (c) {11, 12, 18}

(e) {41}. W(T)=2×4+4×4+6×3+11×2+8×2+10×2=100

最优二叉树的重要应用: 哈夫曼编码

例: 采用二进制对\(a, b, c\)和\(d\)进行等(定)长编码:

\[a{\rightarrow}00, b{\rightarrow}01, c{\rightarrow}10, d{\rightarrow}11\] 对字符序列\(aabba\)进行二进制编码: 0000010100.

在译(解)码时就对应一个字符序列\(aabba\), 还原了原字符序列.

\[ \begin{array}{ccccc} 00 & 00 & 01 & 01 & 00\\ a & a & b & b & a \\ \end{array} \]

采用二进制对\(a, b, c\)和\(d\)进行变长编码:

\[a{\rightarrow}1, \, \, b{\rightarrow}00, \, \, c{\rightarrow}01, \, \, d{\rightarrow}10\]

对字符序列\(aabba\)进行二进制编码: 1100001.

但在译码时:

\[ \begin{array}{ccccc} 1 & 1 & 00 & 00 & 1\\ a & a & b & b & a \\ \end{array} \] \[ \begin{array}{cccc} 1 & 10 & 00 & 01\\ a & d & b & c \\ \end{array} \]

可能对应两个字符序列\(aabba\)或\(adbc\), 产生了二义性, 此时字符序列在编码后可能没有办法还原. 因此必须有一种方法来确定每一个字符的编码, 使得每一个字符序列对应惟一的二进制序列, 反之亦然.

采用二进制对\(a, b, c\)和\(d\)进行变长编码:

\[a{\rightarrow}0, \, \, b{\rightarrow}10, \, \, c{\rightarrow}110, \, \, d{\rightarrow}111\]

对字符序列\(aabba\)进行二进制编码: 0010100.

译码时就只对应一个字符序列: \(aabba\).

\[ \begin{array}{ccccc} 0 & 0 & 10 & 10 & 0\\ a & a & b & b & a \\ \end{array} \]

不会产生二义性. 这种编码称为前缀码.

定义: 设\(a_1a_2{\cdots}a_{n-1}a_n\)是长度为\(n\)的二进制串, 称其子串\(a_1, a_1a_2, {\cdots}, a_1a_2{\cdots}a_{n-1}\)为该二进制串的长度为\(1, 2, {\cdots}, n-1\)的前缀.

定义: 设\(\{\alpha_1, \alpha_2, {\cdots}, \alpha_{n-1}, \alpha_n\}\)为一个二进制串的集合, 若集合中的任意一个二进制串都不是集合中其他二进制串的前缀, 则称\(\{\alpha_1, \alpha_2, {\cdots}, \alpha_{n-1}, \alpha_n\}\)为前缀码.

例如, \(\{10, 01, 001, 1100, 00011\}\)就是一个前缀码.

那么如何构造前缀码呢？前缀码可以通过正则二叉树来构造.

设\(T\)是具有\(t\)片树叶\(v_1, v_2, {\cdots}, v_t\)的正则二叉树, 则\(T\)的每个分支点有两个儿子, 将每个分支点通向其左儿子的边标记为0, 通向其右儿子的边标记为1.

设\(v_i\)是\(T\)的的任一片树叶, 将树根到树叶\(v_i\)的通路上各边的标记按顺序组成的二进制串放在\(v_i\)处, 则\(t\)片树叶处的\(t\)个二进制串组成的集合就是二元前缀码.

(a) {000, 000, 1} (b) {010, 011, 1} (c) {000, 001, 01, 1}

定理: 由一棵给定的二叉树, 可产生一个二元前缀码.

定理: 由一棵给定的正则二叉树, 可产生唯一的一个二元前缀码.

定理: 任意一个前缀码都对应一棵正则二叉树.

例: 对前缀码\(\{000, 001, 01, 10, 11\}\), 其对应的正则二叉树如下:

采用哈夫曼编码不但可以使字符序列在进行二进制编码后的位数最少, 还保证在解码时不会出现二义性, 这种编码称为最佳编码.

例: 已知字母\(A, B, C, D, E, F\)出现的频率如下:

\[A:30\%\ B:25\%\ C:20\%\ D:10\%\ E:10\%\ F:5\%\]

试设计一种编码方案, 使发送1000个按上述比例出现的字母所用二进制编码位数为最少, 并求最少的发送位数.

解:

(1)构造赋权30, 25, 20, 10, 10, 5的最优二叉树\(T\);

(2)在\(T\)上求一个前缀码(哈夫曼编码).

\[\{5, 10, 10, 20, 25, 30\}{\rightarrow}\{10, 15, 20, 25, 30\}{\rightarrow}\{20, 25, 25, 30\}{\rightarrow}\{25, 30, 45\}{\rightarrow}\{45, 55\}{\rightarrow}\{100\}\]

{A, B, C, D, E, F}对应的哈夫曼编码:{01, 10, 11, 001, 0000, 0001}

\[ \begin{array}{ccccccc} 字母 & A & B & C & D & E & F\\ 编码 & 11 & 10 & 01 & 001 & 0001 & 0000 \\ 发送量 & 300 & 250 & 200 & 100 & 100 & 50 \\ \end{array} \]

发送1000个字母所用二进制位数:

\[300{\times}2+250{\times}2+200{\times}2+100{\times}3+100{\times}4+50{\times}4=2400\] 位二进制.