离散数学及其应用
第8章 特殊图
8.1 欧拉图与哈密顿图 8.2 带权图 8.3 匹配和二分图 8.4 平面图
8.1 欧拉图与哈密顿图
哥尼斯堡七桥问题、周游世界问题
欧拉图
定义8.1.1 设G=（V，E）是无向图或有向图，若G中有一条 包含所有边（有向边）的简单回路，称该回路为欧拉回路，称 图G为欧拉图。若G中有一条包含G中所有边（有向边）的简 单通路，称它为欧拉通路，称图G为半欧拉图。
a
a
5
12 b
8
5
e4
b
85
e4
7 16
9
8
9
c 9d
c 9d
n个结点的图上，以每个结点为起点的所有的哈密顿回 路共有(n-1)! 条，需要计算(n-1)!/2条回路的权值来求出答案。 当结点较多时用这种方法解决旅行商问题是不切实际的，常 用近似算法求解旅行商问题。
8.2.2最短路径问题
– 在一个无向简单连通边带权图G=（V，E，W）中，从u到v
定理8.1.1证明
定理8.1.1 无向连通图G是欧拉图，当且仅当G的所有结点的度数都 是偶数。
证明：（必要性） 设G是欧拉图，则G有欧拉回路C。设a是图G的任一结点，欧拉回路 经过和a关联的边到结点a后又经过另一条和a关联的边离开到下一个结 点b，因此每经过一个结点a就给它的度数贡献2度。若欧拉回路k次经过 结点a，则d（a）=2k。所以，欧拉图的所有结点的度数都是偶数。 （充分性） 假设G中所有结点的度数都是偶数。从G中的任一结点v1开始，经过 任一和v1关联的边e1到另一结点v2，再经过另一和v2关联的边e2到另一结 点v3，依此类推，可以得到一条包含G的边的简单回路C1：v1 e1 v2 e2 v3 em v1。
欧拉图
半欧拉图
8.1.2 哈密顿图
环游世界问题
哈密顿图
定义8.1.3 设图G=（V，E）是无向图或有向图。若G中有一 条包含G的所有结点(仅一次)的回路，称该回路为哈密顿回路， 称图G为哈密顿图。若图G有一条包含G的所有结点的通路， 称该通路为哈密顿通路，称图G为半哈密顿图。
(1)是半哈密尔顿图
2. 修改和结点u相邻的结点的标记值：L(vi)= W(u,vi)。 3. 将具有最小L值的结点记为t，并添加到结点集S中，即S = S{t}。 4. 修改和结点t相邻且不在集合S中的结点的L值： L(vi)=min{L(vi), L(t)+W(t,vi)}。 5. 重复3和4直到结点v被添加到集合S中。
例8.1.2 在下图中，哪些是欧拉图？哪些是半欧拉图？
欧拉图
欧拉图
半欧拉图
欧拉有向图
定义8.1.2 如果连通有向图G中有一条包含G中所有有向边 的有向回路，称它为欧拉有向回路，称图G为欧拉有向图。如 果连通有向图G中有一条包含G中所有有向边的有向通路，称 它为欧拉有向通路，称图G为半欧拉有向图。
a
格雷码
要找到格雷码，可以用n立方体Qn来建模。在Qn图上找一条 哈密顿回路，按哈密顿回路上的结点顺序对应的二进制码序列
就是格雷码。例如，
10
11
110
111
010
011
00
01
100
101
000
001
8.2 带权图
设G=<V,E,W>，V={v1，v2，…，vn}是顶点集合，E是边集
合，W: VVR是赋值函数。
定义8.3.2若M是G的一个匹配，M的边和结点v关联，则称v 为M饱和点，否则称v为M非饱和点。若G=（V，E）的每个结 点都是M饱和点，则称M为G的一个完美匹配。
例题
(1). {e1, e7}是图的一个匹配，也是一个极大匹配， { e2, e4, e8} 是图的最大匹配，也是完美匹配。 (2). {e2, e6}、{e3, e5}是图的匹配，也是极大匹配，{ e1, e4, e7} 是图的一个最大匹配，也是完美匹配。 (3).{e3, e4}、{e1, e5}、{e2, e6}、{e4, e7}等都是极大匹配，也是 最大匹配，没有完美匹配。
M交错路和M可扩充路
定义8.3.3 若M是G=（V，E）的一个匹配，从G中的一个结 点到另一个结点存在一条由属于M的边和不属于M的边交替出 现组成的简单路，则称这条简单路为M交错路。若M交错路的 两端点为M非饱和点时，称这条M交错路是M可扩充路。
最大匹配的充分必要条件
在图（1）中，M={e1，e7}是图的一个匹配， { e2, e1, e4, e7, e8}是M交错路，而且是M可扩充 路。匹配M1={ e2, e4, e8}比M更大。
定理8.1.2证明
定理8.1.2 连通无向图G为半欧拉图，当且仅当G中只有两 个奇度数的结点。
证明 在连通无向图G的两个奇度数的结点之间加一条边e得 到图G，则图G的所有结点的度数都是偶数，有欧拉回路。在 G的欧拉回路中删去这条边e，则可得到一条包含G中所有边 的欧拉通路。因此图G是半欧拉图。
例题
欧拉图
半欧拉图
例题
例8.1.1 在下面的图中，哪些有欧拉回路？没有欧拉回路的图中，
哪些有欧拉通路？
a
a
a
b
cb
cb
c
d
ed
b-c-d-b-e-c-a-b
ed
e
b-d-c-e-b-a-c
欧拉图的判断
定理8.1.1 无向连通图G是欧拉图，当且仅当G的所有结点 的度数都是偶数。
定理8.1.2 连通无向图G为半欧拉图，当且仅当G中只有两 个奇度数的结点。
定理 8.2.1 设G（V，E，W）为一个连通的带权图，则使附 加边子集E1 的权数W(E1)为最小的充分必要条件是G+E1 中任 意边至多重复一次，且G+E1 中的任意回路中重复边的权值之 和不大于该回路总权值的一半。
中国邮路问题
8.3 匹配和二分图
定义8.3.1 在图G=(V，E)中, 若ME, 且M中任意两条边都不 相邻，则称M为G的一个匹配。若在M中再加入任意其它的边e， M{e}有相邻的边，则称M为G的极大匹配。若G中不存在匹 配M1，使得|M1| >| M|，则称M为G的最大匹配。
旅行商问题(TSP) – 完全无向图的每个结点表示一个城市，用两个城市之间
的距离作为边的权，可以得到一个边带权的完全无向图。 旅行商问题是在这样的图中寻找一条旅行总距离最短的 经过每个城市一次且仅一次，又回到出发城市的旅行线 路的问题。这个问题等价于求带权完全图中总权值最小 的哈密顿回路。
8.2.1 旅行商问题
用格雷码表示的最大数与最小数之间也仅一位数不同，即 “首尾相连”，因此这种编码又称循环码。在数字系统中，常要 求代码按一定顺序变化。例如，按自然数递增计数，若采用 8421码，则数0111变到1000时四位均要变化，而在实际电路中， 4位的变化不可能绝对同时发生，则计数中可能出现短暂的其 它代码（如0110、1111等）。在特定情况下可能导致电路状态 错误或输入输出错误。使用格雷码，变化到下一状态时只有1 位不同，可以避免这种错误。
– 用图论的述语，在一个连通的带权图G=（V，E，W）中，要 寻找一条回路，使该回路包含G中的每条边至少一次，且该回 路的总权值最小，也就是说要从包含G的每条边的回路中找一 条总权值最小的回路。
中国邮路问题
如果G是欧拉图，只要求出图G的一条欧拉回路即可。 因此问题就转化为：在有奇度数结点的连通带权图中，在 包含G中每条边至少一次的回路中找一条总权值最小的回路。
(2)为哈密尔顿图
(3)没有哈密顿通路，也没有哈 密顿回路
哈密顿图的必要条件
定理8.1.5 设无向图G=（V，E）是哈密顿图，则对于结点
集V的每一个真子集S均有：W(G-S)|S|, 其中，W(G-S)是G-S的
导出子图的连通分支数。
例如：彼德森图中对于结点集V的每一个真子集S均有：
W(G-S)|S|。但彼德森图不是哈密顿图。
d
a
d
a
d
b
Hale Waihona Puke cb欧拉有向图
c
b
c
半欧拉有向图
欧拉有向图的判断
定理8.1.3 连通有向图G是欧拉图，当且仅当G中每个结点v 的入度等于它的出度。
定理8.1.4 连通有向图G是半欧拉图，当且仅当G中有且仅 有两个奇度数结点，其中一个结点的入度比出度大1，另一个 结点的入度比出度小1。
例题
例8.1.3 在图中，哪些是欧拉图？哪些是半欧拉图？
图G的一条哈密顿回路是ABDFGECA，按这条哈密顿回路安排就坐成一圈, 每个 人都能与两旁的人交谈。
应用2-格雷码
例8.1.6 在一组数的编码中，若任意两个相邻的代码只有一 位二进制数不同，则称这种编码为格雷码。表8.1.1是2位格雷 码，表示数0~3，表8.1.2是3位格雷码，表示数0~7。
格雷码
中国邮路问题
首先注意到，若图G有奇数度结点，则G的奇数度结点必是偶数个． 把奇数度结点配为若干对，每对结点之间在G中有相应的最短路，将这 些最短路画在一起构成一个附加的边子集E1．令G1 =G+E1，即把附加边子 集E1 叠加在原图G上形成一个多重图G1，这时G1中没有奇度数结点．显然 G1是一个欧拉图，因而可以求出G1的欧拉回路．该欧拉回路不仅通过原图 G中每条边，同时还通过E1 中的每条边，且均仅一次． 邮递员问题的难点在于当G的奇数度节点较多时，可能有很多种配对方 法，应怎样选择配对，能使相应的附加边子集E1 的权数W(E1)为最小。
1
27
5
8
6
2
7
5
8
6
9 10
3
4
3
4
1
7
8
6
3
4
例题
例8.1.4 说明下图 所示的无向图G不是哈密顿图。 解 在图中删去结点集S={v2，v4，v6，v8}，W(G−S)=5，不 满足W(G-S)|S|。所以G不是哈密顿图。