第19讲 平面图的有关内容, 二部图及其匹配 主要内容: 1.平面图. 2.平面图的面着色. 3.二部图及其匹配.

8.5 平面图 本节仅讨论无向图. 对于一个无向图来说，怎样将其图形画出来本身是无关紧要的，只要与原来的图同构皆可. 但有些实际问题要求把图画在一个平面上，同时使得图的边仅仅在节点处才相交. 例如单层印刷电路版、集成电路的布线等问题就需要满足上面的要求. 虽然在现实生活中出现了交通立交桥、多层电路版，但平面图问题仍然是一个基本问题. 例如在上章7.1节提到的“3户3井问题”就是判定一个图是否是平面的问题. 平面图与地图着色问题密切相关.

1.平面图的有关概念 Def 设G是无向图,若可将G画在一个平面上,同时使得任意两条边仅仅在节点处才相交,则称G是可平面图(planar graph)或简称G为平面图(plane graph). 设G是平面图,则可在一个平面上将图G画出来且使得其任意两条边仅仅在节点处才相交,这样画出的图称为平面图G的平面嵌入(embedding)或平面表示. 由于一个平面图与其平面表示是同构的, 因此平面图通常是指其平面表示.

两个重要的非平面图的例子: (1)K5. (2) K3,3.

极大平面图? K5-{e}(True); K3, 3-{e}(False). 极小非平面图? K5; K3, 3.

Def 8-19 设G是平面图,由G的若干条边所围成的连通区域称为图G的面(face),围成面的(回路所在的)边称为面的边界(boundary). 一个区域是连通的,是指其内部不包含该图的任何边. Figure 8-38(b)?

特别注意,任何平面图都有一个由若干条边往外围成的一个面,它是唯一的一个无限面. 求一个平面图的面可以这样做,在一张较大的纸上将平面图画上,然后用剪刀将图的所有边剪破,这张纸被分成的每一部分就是一个面. 平面图的两个面相邻是指这两个面有公共的边界.

2.Euler公式 Euler在1750年研究多面体时发现,多面体的面数等于多面体的棱数减去顶点数加2,后来发现连通平面图的面数与其节点数、边数之间也有同样的关系. Theorem (Euler公式)任意(n, m)连通平面图的面数r = m – n +2. Proof 对面数r归纳. r = 1. r  2  回路C. 去掉C上的一条边e. G – {e}.

Remark 在Euler公式中, “连通”的条件是必不可少的. Corollary 1 任意(n, m)简单平面图, 若n  3, 则m  3n - 6. n  3(?): 例8-16 证明: K5不是平面图. Hint 反证.

Corollary 2 任意(n, m)简单平面图, 若G不含K3子图且n  3, 则m  2n - 4. Hint 反证. 下面的定理是证明“五色定理”的关键. Theorem 8-11(P244) 任何简单平面图必存在一个度数 5 的节点. Proof 不妨设n  3. 假设vV, deg(v)  6.

3.Kuratowski定理 先介绍同胚的定义. Def 若两个图是同构的, 或者通过反复进行以下操作(见图8-42)使得它们同构, 则称这两个图同胚(homeomorphism):

Theorem (Kuratowski, 1930) 无向图G是平面图的充要条件是G无同胚于K5和K3,3的子图. 例8-18 证明: Petersen图不是平面图.

4.平面图的对偶图 对平面图G的面的研究可以转换为对其对偶图G*的节点的研究.

根据定义知, 任意平面图的对偶图是平面图且是连通的. 设G是(n, m)平面图,有r个面,则G*是(r, m)平面图,有n个面. 对于连通平面图G, 其对偶图为G*, 这时G*的对偶图G**为本身. 对于非连通平面图G, 可能G与G*不同构.

8.6 平面图的面着色 “四色猜想”(4CC, Four Color Conjecture). 8.6 平面图的面着色 “四色猜想”(4CC, Four Color Conjecture). 1879年伦敦数学会会员A. B. Kemple给出了四色猜想的第一个证明,10年后P. J. Heawood指出了Kemple证明过程中存在一个不可克服的漏洞,并沿用Kemple的方法证明了五色定理,即五种颜色足够.

4CC成了会下金蛋的鹅. 在1976年,美国的Kenneth Appel和Wolfgang Haken与John Koch合作, 用了1260个小时证明了“四色猜想”,它开启了定理机器证明的新篇章,四色猜想变成四色定理了. 1999年又给出了一些改进,缩短了计算机的运行时间. 至今为止还没有发现4CC的纯数学证明. 本节主要内容是平面图的面着色问题,顺便介绍任意无向图的节点着色以及边着色等有关内容.

1.平面图的面着色 Def 设G是平面图, 若对G的每个面涂上一种颜色且相邻的面出现不同的颜色, 则称对该平面图的面着色(face coloring), 所需颜色的最少种数称为面着色数(region chromatic number). 例子? Figure 8-47(see below)

2.图的节点着色 (1)任意图的节点着色 Def 设G是任意无向图,若对G的每个节点涂上一种颜色且相邻的节点出现不同的颜色,则称对该图的节点着色(vertex coloring), 简称着色(coloring),所需颜色的最少种数称为节点着色数, 简称着色数(chromatic number),记为

Theorem 8-13 G无loop, 则 可以利用韦尔奇鲍威尔(Welch Powell)算法对图的节点着色,进而求出的上界. Step 1 将节点按度数从大到小的顺序排列. Step 2 用第一种颜色对第一个节点着色,并且按照其余未着色节点顺序,对不邻接的每一个节点着上同样的颜色. Step 3 用第二种颜色对尚未着色的节点重复Step 2, 继续下去, 直到所有的点都着色为之. 例子?

(2)平面图的节点着色 平面图的节点着色与一般无向图的节点着色是相同的. 值得注意的是,平面图的面着色,可以转换为其对偶图(也是平面图)的节点着色. 于是,五色定理为 Theorem 8-14 设G是简单平面图,则 Hint 对G的节点个数n归纳.

3.任意图的边着色 Def 设G是任意无向图, 若对G的每条边涂上一种颜色且相邻的边出现不同的颜色, 则称对该图的边着色(edge coloring), 所需颜色的最少种数称为边着色数(edge-chromatic number). 图中的两条边相邻是指它们有公共的节点.

对图的边着色问题不做更深入讨论,最后对与Ramsey理论密切相关的图的边“涂色”的问题进行简单说明. Ramsey问题(Ramsey problem) 任给一群人,其中有p个人彼此认识或有q个人彼此不认识,这种人群至少多少人? Ramsey问题中的答案记为R(p, q). 例8-20(P250) 证明: 任意6个人中,有3个人彼此认识或有3个人彼此不认识.

R(3, 3) = 6(1930), 其他Ramsey数?

8.7 二部图及其匹配 在诸如人员分配、资源分配等问题的讨论中,经常涉及到二部图及其匹配. 本节仅对简单无向图进行讨论. 1. 二部图 8.7 二部图及其匹配 在诸如人员分配、资源分配等问题的讨论中,经常涉及到二部图及其匹配. 本节仅对简单无向图进行讨论. 1. 二部图 Definition V划分为V1和V2, 任意边关联的两个节点中一个在V1中, 一个在V2中.

Remark 互补节点集合不是唯一的.

下面的定理给出了简单无向图是二部图的充要条件. Theorem 8-15 设G为阶数 2的简单无向图,则G是二部图的充要条件是G中任意圈的长度为偶数. Proof () ()取v  V, 令V1 = {u|u  V, d(u, v)是偶数}, V2 = V - V1. 显然, 任意无向树是二部图.

2.匹配 Def 设G = (V, E)是任意简单无向图. 若  M  E且中任何两条边都不相邻,则称M为G的一个匹配(matching)或边独立集(independent set of edges). (a)边数最多的匹配称为最大匹配(maximum matching),其中的边数称为匹配数. (b)所有节点都与中的某边关联的匹配称为完美匹配(perfect matching).

(c)在二部图G = (V, E)中, V1和V2为互补节点集 (c)在二部图G = (V, E)中, V1和V2为互补节点集. 若M为G的一个最大匹配且 |M| = min{| V1 |, | V2|}, 则称M为G的一个完备匹配(complete matching). 当| V1 |  | V2|}, M也称为G的一个从V1到V2的完备匹配. 1935年Hall给出了判定二部图是否存在完备匹配的充要条件—“相异性条件”.

Theorem (Hall, 1935) 设G = (V, E)是二部图, V1和V2为互补节点集, 则G中存在从V1到V2的完备匹配的充要条件是V1中的任意k(k = 1, 2, …,| V1 |)个节点至少与V2中的k个节点邻接. 利用匈牙利(Hungarian)算法(J. Edmonds, 1965)可用于求从到的完备匹配.

根据Hall定理可得 Theorem 8-17(P252) 设G = (V, E)是二部图, V1和V2为互补节点集,若存在t使得如下“t条件”成立: (1) V1中的每个节点至少关联t条边； (2) V2中的每个节点至多关联t条边， 则G中存在从V1到V2的完备匹配.

下述定理给出了任意简单无向图存在完美匹配的充要条件. Theorem 8-18(Tutte) 图G = (V, E)有完美匹配的充要条件是对于任意W  V均有O(G - W)  |W|, 其中O(G - W)表示含奇数个节点的连通分支数.