离 散 数 学 计算机科学与工程学院 示 范 性 软 件 学 院 电子科技大学 2017年3月21日星期二.

Presentation on theme: "离 散 数 学 计算机科学与工程学院 示 范 性 软 件 学 院 电子科技大学 2017年3月21日星期二."— Presentation transcript:

1 离 散 数 学 计算机科学与工程学院 示 范 性 软 件 学 院 电子科技大学 2017年3月21日星期二

2 第11章 特殊图 欧拉图 1 集合的表示方法 2 哈密顿图 偶图 3 平面图 4 2017/3/21

3 11.0 内容提要 几个特殊图的概念：欧拉图、哈密顿图、偶图、平面图； 欧拉图、哈密顿图、偶图、平面图的判定； 偶图的匹配、图的着色；
欧拉图、哈密顿图、偶图、平面图的应用 2017/3/21

4 10.1 本章学习要求 重点掌握 一般掌握 了解 1 1 各个特殊图相关基本概念 2 各个特殊图的性质 3 各个特殊图的判定方法 2
1 哈密顿图、平面图的判断 2 证明方法 3 1 各个特殊图的应用 2 图的着色 2017/3/21

5 11.2 欧拉图 11.2.1 欧拉图的引入与定义 A B C D b5 b2 b1 b3 b4 b7 b6 B C A D b6 b2
2017/3/21

6 定义11.2.1 设G是无孤立结点的图，若存在一条通路(回路)，经过图中每边一次且仅一次，则称此通路(回路)为该图的一条欧拉通路(回路)(Eulerian Entry/Circuit)。具有欧拉回路的图称为欧拉图(Eulerian Graph)。 规定：平凡图为欧拉图。 以上定义既适合无向图，又适合有向图。 2017/3/21

7 欧拉通路和欧拉回路的特征 欧拉通路是经过图中所有边的通路中长度最短的通路，即为通过图中所有边的简单通路；
欧拉回路是经过图中所有边的回路中长度最短的回路，即为通过图中所有边的简单回路。 如果仅用边来描述，欧拉通路和欧拉回路就是图中所有边的一种全排列。 2017/3/21

8 例11.2.1 欧拉图 判断下面的6个图中，是否是欧拉图？是否存在欧拉通路？ 不存在欧拉通路 不是欧拉图，但存在欧拉通路 不存在欧拉通路
v3 v1 v2 v4 (c) (a) (b) (f) (d) (e) 不存在欧拉通路 欧拉图 不是欧拉图，但存在欧拉通路 2017/3/21

9 欧拉图的判定 定理 无向图G = <V, E>具有一条欧拉通路，当且仅当G是连通的，且仅有零个或两个奇度数结点。 分析 只要找到了，就是存在的。我们具体找一条欧拉通路。对于结点的度数，我们在通路中去计算。 证明 若G为平凡图，则定理显然成立。故我们下面讨论的均为非平凡图。 2017/3/21

10 必要性： 设G具有一条欧拉通路L = ，则L经过G中的每条边，由于G中无孤立结点，因而L经过G的所有结点，所以G是连通的。
对欧拉通路L的任意非端点的结点 ，在L中每出现 一次，都关联两条边 和 ，而当 重复出现时，它又关联另外的两条边，由于在通路L中边不可能重复出现，因而每出现一次都将使获得2度。若在L中重复出现p次，则deg( )= 2p。 2017/3/21

11 deg( )= 2p1+1，deg( ) = 2p2+1 deg( )= 1+2p3+1 = 2(p3+1)
2017/3/21

12 充分性：构造性证明。 我们从两个奇度数结点之一开始(若无奇度数结点，可从任一结点开始)构造一条欧拉通路，以每条边最多经过一次的方式通过图中的边。对于度数为偶数的结点，通过一条边进入这个结点，总可以通过一条未经过的边离开这个结点，因此，这样的构造过程一定以到达另一个奇度数结点而告终(若无奇度数结点，则以回到原出发点而告终)。如果图中所有的边已用这种方式经过了，显然这就是所求的欧拉通路。如果图中不是所有的边都经过了，我们去掉已经过的边，得到一个由剩余的边组成的子图，这个子图的所有结点的度数均为偶数。 2017/3/21

13 由定理11.2.1的证明知：若连通的无向图有两个奇度数结点，则它们是G中每条欧拉通路的端点。
因为原来的图是连通的，因此，这个子图必与我们已经过的通路在一个或多个结点相接。从这些结点中的一个开始，我们再通过边构造通路，因为结点的度数全是偶数，因此，这条通路一定最终回到起点。我们将这条回路加到已构造好的通路中间组合成一条通路。如有必要，这一过程重复下去，直到我们得到一条通过图中所有边的通路，即欧拉通路。 由定理11.2.1的证明知：若连通的无向图有两个奇度数结点，则它们是G中每条欧拉通路的端点。 2017/3/21

14

15 活着真好！ 珍爱生命，热爱生活 好好学习，天天向上

16 复习 欧拉图的判定 定理 无向图G = <V, E>具有一条欧拉通路，当且仅当G是连通的，且仅有零个或两个奇度数结点。 推论 无向图G = <V, E>具有一条欧拉回路，当且仅当G是连通的，并且所有结点的度数均为偶数。 2017/3/21

17 结论 定理 有向图G具有一条欧拉通路，当且仅当G是连通的，且除了两个结点以外，其余结点的入度等于出度，而这两个例外的结点中，一个结点的入度比出度大1，另一个结点的出度比入度大1。 推论 有向图G具有一条欧拉回路，当且仅当G是连通的，且所有结点的入度等于出度。 2017/3/21

18 欧拉通路与欧拉回路判别准则 对任意给定的无向连通图，只需通过对图中各结点度数的计算，就可知它是否存在欧拉通路及欧拉回路，从而知道它是否为欧拉图；对任意给定的有向连通图，只需通过对图中各结点出度与入度的计算，就可知它是否存在欧拉通路及欧拉回路，从而知道它是否为欧拉图。 利用这项准则，很容易判断出哥尼斯堡七桥问题是无解的，因为它所对应的图中所有4个结点的度数均为奇数；也很容易得到例11.2.1的结论。 2017/3/21

19 定义11.2.2 设G = <V, E>，e∈E，如果 p(G-e)＞p(G)
称e为G的桥(Bridge)或割边(Cut edge)。 显然，所有的悬挂边都是桥。 桥 v1 e7 v2 e1 v6 e6 e9 v3 e2 e5 e3 v7 v4 e4 v5 2017/3/21

20 Fleury算法 算法11.2.1 求欧拉图G = <V, E>的欧拉回路的Fleury算法：
（1）任取v0∈V，令P0 = v0，i = 0； （2）按下面的方法从E-{e1, e2, …, ei}中选取ei+1： a. ei+1与vi相关联； b. 除非无别的边可选取，否则ei+1不应该为G’ = G-{e1, e2, …, ei}中的桥； （3）将边ei+1加入通路P0中，令P0 = v0e1v1e2…eiviei+1vi+1，i = i+1； （4）如果i = |E|，结束，否则转(2)。 2017/3/21

21 P12 = v1e1v2e2v3e3v4e4v5e5v6e6v7e7v8e9v2e10v4e11v6e12v8e8v1
例11.2.2 用Fleury算法求欧拉图的一条欧拉回路。 v1 e1 v2 e2 v3 v1 e1 v2 e2 v3 e8 e3 e8 e3 e9 e10 e9 e10 v8 v4 v8 v4 e12 e11 e12 e11 e7 e4 e7 e4 v7 e6 v6 e5 v5 v7 e6 v6 e5 v5 解 从v1出发的一条欧拉回路为： P12 = v1e1v2e2v3e3v4e4v5e5v6e6v7e7v8e9v2e10v4e11v6e12v8e8v1 2017/3/21

22 11.2.4 欧拉图的应用 1、一笔画问题 所谓“一笔画问题”就是画一个图形，笔不离纸，每条边只画一次而不许重复，画完该图。
“一笔画问题”本质上就是一个无向图是否存在欧拉通路(回路)的问题。如果该图为欧拉图，则能够一笔画完该图，并且笔又回到出发点；如果该图只存在欧拉通路，则能够一笔画完该图，但笔回不到出发点；如果该图中不存在欧拉通路，则不能一笔画完该图。 2017/3/21

23 例11.2.3 图中的三个图能否一笔画？为什么？ v1 v2 v3 v4 v5 (b) (c) (a) 解 因为图(a)和(b)中分别有0个和2个奇度数结点，所以它们分别是欧拉图和存在欧拉通路，因此能够一笔画，并且在(a)中笔能回到出发点，而(b)中笔不能回到出发点。图c中有4个度数为3的结点，所以不存在欧拉通路，因此不能一笔画。 2017/3/21

24 2、蚂蚁比赛问题 例 甲、乙两只蚂蚁分别位于图的结点A、B处，并设图中的边长度相等。甲、乙进行比赛：从它们所在的结点出发，走过图中所有边最后到达结点C处。如果它们的速度相同，问谁先到达目的地？ A(甲) B (乙) C 解 图中仅有两个度数为奇数的结点B、C，因而存在从B到C的欧拉通路，蚂蚁乙走到C只要走一条欧拉通路，边数为9条，而蚂蚁甲要想走完所有的边到达C，至少要先走一条边到达B，再走一条欧拉通路，因而它至少要走10条边才能到达C，所以乙必胜。 2017/3/21

25 11.3 哈密顿图 哈密顿的引入与定义 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 2017/3/21

26 哈密顿图 定义 经过图中每个结点一次且仅一次的通路(回路)称为哈密顿通路(回路)(Hamiltonian Entry/circuit)。存在哈密顿回路的图称为哈密顿图(Hamiltonian Graph)。 规定：平凡图为哈密顿图。 以上定义既适合无向图，又适合有向图。 2017/3/21

27 例11.3.1 判断下面的6个图中，是否是哈密顿图？是否存在哈密顿通路？ 不存在哈密顿通路 不是哈密顿图，但存在哈密顿通路
v3 v1 v2 v4 (a) (d) (b) v5 v6 v7 (c) (e) (f) 不存在哈密顿通路 不是哈密顿图，但存在哈密顿通路 不是哈密顿图，但存在哈密顿通路 不存在哈密顿通路 哈密 顿图 哈密 顿图 2017/3/21

28 11.3.2 哈密顿图的判定 定理11.3.1 设无向图G = <V, E>是哈密顿图，V1是V的任意非空子集，则
p(G-V1) ≤ |V1| 其中p(G-V1)是从G中删除V1后所得到图的连通分支数。 分析 考察G的一条哈密顿回路C，显然C是G的生成子图，从而C-V1也是G-V1的生成子图，且有p(G-V1) ≤ p(C-V1)，故只需要证明p(C-V1) ≤ |V1|即可。 2017/3/21

29 证明 设C是G中的一条哈密顿回路，V1是V的任意非空子集。下面分两种情况讨论：
（1）V1中结点在C中均相邻，删除C上V1中各结点及关联的边后，C-V1仍是连通的，但已非回路，因此p(C-V1) = 1 ≤ |V1|。 （2）V1中结点在C上存在r(2 ≤ r ≤ |V1|)个互不相邻，删除C上V1中各结点及关联的边后，将C分为互不相连的r段，即 p(C-V1) = r ≤ |V1|。 一般情况下，V1中的结点在C中既有相邻的，又有不相邻的，因此总有p(C-V1) ≤ |V1|。 又因C是G的生成子图，从而C-V1也是G-V1的生成子图，故有 p(G-V1) ≤ p(C-V1) ≤ |V1| 2017/3/21

30 推论11.3.1 设无向图G = <V, E>中存在哈密顿通路，则对V的任意非空子集V1，都有
p(G-V1) ≤ |V1| + 1 v2 v4 v1 v5 v3 定理11.3.1在应用中它本身用处不大，但它的逆否命题却非常有用。我们经常利用定理11.3.1的逆否命题来判断某些图不是哈密顿图，即：若存在V的某个非空子集V1使得p(G-V1)＞|V1|，则G不是哈密顿图。 注意： 定理11.3.1给出的是哈密顿图的必要条件，而不是充分条件。 v3 v1 v2 v4 v5 v6 v7 2017/3/21

31 例11.3.2 证明图中不存在哈密顿回路。 证明 在图中，删除结点子集｛d, e, f｝，得新图，它的连通分支为4个，由定理11.3.1知，该图不是哈密顿图，因而不会存在哈密顿回路。 分析 利用定理11.3.1的逆否命题，寻找V的某个非空子集V1使得p(G-V1)＞|V1|，则G不是哈密顿图。找到V1 = ｛d, e, f｝满足要求。 d f e a b c g i h a b c g i h 2017/3/21

32 定理11.3.2 设G = <V, E>是具有n个结点的简单无向图。如果对任意两个不相邻的结点u, v∈V，均有
deg(u)+deg(v)≥n-1 则G中存在哈密顿通路。 证明 首先证明满足上述条件的G是连通图。用反证法：假设G有两个或更多连通分支。设一个连通分支有n1个结点，另一个连通分支有n2个结点。这二个连通分支中分别有两个结点v1、v2。显然，deg(v1)≤n1-1，deg(v2)≤n2-1。从而deg(v1)+deg(v2)≤n1+n2-2 ≤n-2与已知矛盾，故G是连通的。 2017/3/21

33 证明(续1) 其次，证明G中存在哈密顿通路。
设P = v1v2…vk为G中用“延长通路法”得到的“极大基本通路”，即P的始点v1与终点vk不与P外的结点相邻，显然k ≤ n。 （1）若k = n，则P为G中经过所有结点的通路，即为哈密顿通路。 （2）若k＜n，说明G中还有在P外的结点，但此时可以证明存在仅经过P上所有结点的基本回路，证明如下： （a）若在P上v1与vk相邻，则v1v2…vkv1为仅经过P上所有结点的基本回路。 2017/3/21

34 证明(续2) （b）若在P上v1与vk不相邻，假设v1在P上与vi1= v2,vi2,vi3,…,vij相邻(j必定大于等于2，否则deg(v1)+deg(vk)≤1+k-2＜n-1)，此时vk必与vi2,vi3,…,vij相邻的结点vi2-1,vi3-1,…,vij-1至少之一相邻(否则deg(v1) + deg(vk) ≤ j+k-2-(j-1) = k-1＜n-1)。设vk与vir-1(2≤r≤j)相邻，如图所示。在P中添加边(v1,vir)、(vk,vir-1)，删除边(vir-1,vir)得基本回路C=v1v2…vir-1vkvk-1…virv1。 v1 vir-1 vir vk (a) (b) vk+1 vt 2017/3/21

35 证明(续3) （3）证明存在比P更长的通路。 因为k＜n，所以V中还有一些结点不在C中，由G的连通性知，存在C外的结点与C上的结点相邻，不妨设vk+1∈V-V(C)且与C上结点vt相邻，在C中删除边(vt-1,vt)而添加边(vt,vk+1)得到通路P’= vt-1…v1 vir…vkvir-1…vtvk+1。显然，P’比P长1，且P’上有k+1个不同的结点。 对P’重复(1)～(3)，得到G中的哈密顿通路或比P’更长的基本通路，由于G中结点数目有限，故在有限步内一定得到G中的一条哈密顿通路。 2017/3/21

36 推论 推论11.3.2 设G = <V, E>是具有n个结点的简单无向图。如果对任意两个不相邻的结点u, v∈V，均有
deg(u)+deg(v)≥n 则G中存在哈密顿回路。 推论 设G = <V, E>是具有n个结点的简单 无向图，n≥3。如果对任意v∈V，均有deg(v)≥ n/2，则G是哈密顿图。 需要注意，定理11.3.2给出的是哈密顿图的充分条件，而不是必要条件。在六边形中，任两个不相邻的结点的度数之和都是4＜6，但六边形是哈密顿图。 2017/3/21

37 例11.3.3 某地有5个风景点，若每个风景点均有2条道路与其他点相通。问游人可否经过每个风景点恰好一次而游完这5处？
解 将5个风景点看成是有5个结点的无向图，两风景点间的道路看成是无向图的边，因为每处均有两条道路与其他结点相通，故每个结点的度数均为2，从而任意两个不相邻的结点的度数之和等于4，正好为总结点数减1。故此图中存在一条哈密顿通路，因此游人可以经过每个风景点恰好一次而游完这5处。 2017/3/21

38 例11.3.4 5 e 4 1 a 2 b 3 c d f g h i j k m n o p 判断下图是否存在哈密顿回路。 5 e 4 1 a 2 b 3 c d f g h i j k m n o p 5 4 1 2 3 f g h i j k m n o p 方法二：若图中存在哈密顿回路，则该回路组成的图中任何结点的度数均为2。因而结点1、2、3、4、5所关联的边均在回路中，于是在结点a、b、c、d、e处均应将不与1、2、3、4、5关联的边删除，而要删除与结点a、b、c、d、e关联的其它边，得到右上图，它不是连通图，因而图中不存在哈密顿回路。 解 方法一：在图中，删除结点子集{a, b, c, d, e}，得到的图有7个连通分支，由定理11.2.1知，该图不是哈密顿图，因而不会存在哈密顿回路。 2017/3/21

39 例11.3.5 证明下图没有哈密顿通路。 证明 任取一结点如1用A标记，所有与它邻接的结点用B标记。继续不断地用A标记所有邻接于B的结点，用B标记所有邻接于A的结点，直到所有结点都标记完毕。 如果图中有一条哈密顿通路，那么它必交替通过结点A和B，故而标记A的结点与标记B的结点数目或者相同，或者相差1个。然而图中有3个结点标记为A，5个结点标记为B，它们相差两个，所以该图不存在哈密顿通路。 1(A) 2(B) 8(B) 3(A) 4(B) 5(B) 6(B) 7(A) 2017/3/21

40 定理11.3.3 设G = <V, E>是有n(n≥2)个结点的一些简单有向图。如果忽略G中边的方向所得的无向图中含生成子图Kn，则有向图G中存在哈密顿通路。 在右图中，它所对应的无向图中含完全图K5，由定理11.3.3知，图中含有哈密顿通路。事实上，通路v3v5v4v2v1为一条哈密顿通路。 v2 v3 v1 v4 v5 2017/3/21

41 11.4 偶图 偶图的定义 定义 若无向图G = <V, E>的结点集V能够划分为两个子集V1, V2，满足V1∩V2 = ，且V1∪V2 = V，使得G中任意一条边的两个端点，一个属于V1，另一个属于V2，则称G为偶图(Bipartite Graph)或二分图(Bigraph)。V1和V2称为互补结点子集，偶图通常记为G=<V1,E,V2>。 偶图没有自回路。 平凡图和零图可看成特殊的偶图。 2017/3/21

42 定义11.4.2 在偶图G = <V1, E, V2>中，若V1中的每个结点与V2中的每个结点都有且仅有一条边相关联，则称偶图G为完全偶图(Complete Bipartite Graph)或完全二分图(Complete Bigraph)，记为Ki,j，其中，i = |V1|，j = |V2|。 2017/3/21

43 例11.4.1 判断图中的几个图，那些是偶图？那些是完全偶图？ 偶图 偶图 偶图 偶图 完全偶图K2,3 完全偶图K3,3 完全偶图K3,3
v1 v2 v3 v4 v5 v6 v7 (a) (d) (b) (c) (e) 偶图 完全偶图K2,3 偶图 完全偶图K3,3 偶图 完全偶图K3,3 偶图 不是偶图 2017/3/21

44 11.4.2 偶图的判定 定理11.4.1 无向图G = <V, E>为偶图的充分必要条件是G的所有回路的长度均为偶数。
证明 必要性：设图G是偶图G = <V1,E,V2>，令C = v0v1v2…vkv0是G的一条回路，其长度为k+1。 不失一般性，假设v0∈V1，由偶图的定义知，v1∈V2，v2∈V1。由此可知，v2i∈V1且v2i+1∈V2。 又因为v0∈V1，所以vk∈V2，因而k为奇数，故C的长度为偶数。 2017/3/21

45 充分性： 设G中每条回路的长度均为偶数，若G是连通图，任选v0∈V，定义V的两个子集如下：
V1 = {vi | d(v0, vi)为偶数}， V2 = V-V1。 现证明V1中任两结点间无边存在。 假若存在一条边(vi, vj)∈E，其中vi, vj∈V1，则由v0到vi间的短程线(长度为偶数)以及边(vi, vj)，再加上vj到v0间的短程线(长度为偶数)所组成的回路的长度为奇数，与假设矛盾。 2017/3/21

46 充分性： 同理可证V2中任两结点间无边存在。
故G中每条边(vi, vj)，必有vi∈V1，vj∈V2或vi∈V2，vj∈V1，因此G是具有互补结点子集V1和V2的偶图。 若G中每条回路的长度均为偶数，但G不是连通图，则可对G的每个连通分支重复上述论证，并可得到同样的结论。 2017/3/21

47 定理11.4.1的用途 在实际应用中，定理11.4.1本身使用不多，我们常使用它的逆否命题来判断一个图不是偶图：
无向图G 不是偶图的充分必要条件是G中存在长度为奇数的回路。 例如下图中存在长度为3的回路v1v2v4v1，所以它不是偶图。 v1 v4 v2 v3 2017/3/21

48 匹配 定义 在偶图G = <V1, E, V2>中，V1 = {v1, v2, …, vq}，若存在E的子集E’ = {(v1, v1’)，(v2, v2’)，…，(vq, vq’)，其中v1’, v2’, …, vq’ 是V2中的q个不同的结点}，则称G的子图G’ = <V1, E’, V2>为从V1到V2的一个完全匹配(Complete Matching)，简称匹配。 2017/3/21

49 必要条件 在偶图G = <V1, E, V2>中，若存在V1到V2的单射f，使得对任意v∈V1，都有(v, f(v))∈E，则存在V1到V2的匹配。 由单射的性质知，不是所有的偶图都有匹配，存在匹配的必要条件是|V1| ≤ |V2|。 然而，这个条件并不是充分条件。 2017/3/21

50 例11.4.2 下面的3个偶图哪些存在V1到V2匹配？对存在匹配的偶图给出一个匹配。 不存在匹配 不存在匹配 存在匹配 v1 v2 v3
(a) v4 V1 V2 v1 v2 v3 v5 v6 v7 v8 v4 v9 V1 V2 (b) v1 v2 v3 v4 v5 v6 V1 V2 v1 v2 v3 v5 v6 v7 v8 (c) v4 v9 V1 V2 不存在匹配 不存在匹配 存在匹配 2017/3/21

51 霍尔定理 定理 (霍尔定理) 偶图G = <V1, E, V2>中存在从V1到V2的匹配的充分必要条件是V1中任意k个结点至少与V2中的k个结点相邻，k = 1, 2, …, |V1|。 定理11.4.2中的条件通常称为相异性条件(Diversity Condition)。 2017/3/21

52 例 不满足相异性条件，故没有匹配。 满足相异性条件，故存在匹配 (b) v1 v2 v3 v4 v5 v6 V1 V2 v1 v2 v3
(c) v4 v9 V1 V2 不满足相异性条件，故没有匹配。 满足相异性条件，故存在匹配 2017/3/21

53 定理11.4.3中的条件通常称为t条件(t-Condition)。
设G = <V1,E,V2>是一个偶图。如果满足条件 （1）V1中每个结点至少关联t条边； （2）V2中每个结点至多关联t条边； 则G中存在从V1到V2的匹配。其中t为正整数。 证明 由条件(1)知，V1中k个结点至少关联tk条边(1≤k≤|V1|)，由条件(2)知，这tk条边至少与V2中k个结点相关联，于是V1中的k个结点至少与V2中的k个结点相邻接，因而满足相异性条件，所以G中存在从V1到V2的匹配。 定理11.4.3中的条件通常称为t条件(t-Condition)。 判断t条件非常简单，只需要计算V1中结点的最小度数和V2中结点的最大度数即可。 2017/3/21

54 偶图的应用 例 有n台计算机和n个磁盘驱动器。每台计算机与m＞0个磁盘驱动器兼容，每个磁盘驱动器与m台计算机兼容。能否为每台计算机配置一台与它兼容的磁盘驱动器？ 解 用V1表示n台计算机的集合，V2表示n台磁盘驱动器的集合。以V1，V2为互补结点子集，以E = {(vi, vj) | vi∈V1, vj∈V2且vi与vj兼容}为边集，构造偶图。它显然满足t条件(t = m)，所以存在匹配，故能够为每台计算机配置一台与它兼容的磁盘驱动器。 2017/3/21

55 例11.4.4 现有三个课外小组：物理组，化学组和生物组，有五个学生s1,s2,s3,s4,s5。
（1）已知s1,s2为物理组成员；s1,s3,s4为化学组成员；s3,s4,s5为生物组成员。 （2）已知s1为物理组成员；s2,s3,s4为化学组成员；s2,s3,s4,s5为生物组成员。 （3）已知s1即为物理组成员，又为化学组成员；s2,s3,s4,s5为生物组成员。 在以上三种情况的每一种情况下，在s1,s2,s3,s4, s5中选三位组长，不兼职，问能否办到？ 2017/3/21

56 解 用c1,c2,c3分别表示物理组、化学组和生物组。 V1={c1,c2,c3}， V2={s1,s2,s3,s4,s5}
以V1，V2为互补结点子集，以E={(ci,sj)|ci∈V1, sj∈V2且ci中有成员sj}为边集，构造偶图。 (1) c1 c2 c3 s1 s2 s3 s4 s5 V1 V2 (1) c1 c2 c3 s1 s2 s3 s4 s5 V1 V2 (2) c1 c2 c3 s1 s2 s3 s4 s5 V1 V2 (2) c1 c2 c3 s1 s2 s3 s4 s5 V1 V2 (3) c1 c2 c3 s1 s2 s3 s4 s5 V1 V2 不存在匹配 2017/3/21

57 11.5 平面图 平面图的定义 在一张纸上画几何模型时常常会发现，不仅需要允许各边在结点处相交，而且还应该允许各边在某些非结点处相交，这样的点称为交叉点(Cross Point)；而相交的边，称为交叉边(Cross Edge)。 v1 v2 v3 v4 v5 2017/3/21

58 应当注意，有些图从表面上看它的某些边是相交叉的，但是不能就此肯定它不是平面图。
定义11.5.1 如果能把一个无向图G的所有结点和边画在平面上，使得任何两边除公共结点外没有其他交叉点，则称G为平面图(Plane Graph)，否则称G为非平面图(Nonplanar Graph)。 当且仅当一个图的每个连通分支都是平面图时，这个图是平面图。 v1 v2 v3 v4 v5 v1 v2 v3 v4 v5 平面图的平面表示 应当注意，有些图从表面上看它的某些边是相交叉的，但是不能就此肯定它不是平面图。 2017/3/21

59 非平面图 有些图形不论如何改画，除去结点外，总有边相交叉。 即不管怎样改画，至少有一条边与其他边相交叉，故它是非平面图。 v1 v2 v3
2017/3/21

60 11.5.2 观察法 观察法 设G是画于平面上的图，并设 C = v1…v2…v3…v4…v1
是G中的任何基本回路。此外，设P1 = v1…v3和P2 = v2…v4是G中的任意两条无公共结点的基本通路。 v1 v3 v4 v2 P2 P1 观察法 2017/3/21

61 例11.5.1 用观察法来判定图K3,3为非平面图。 v1 v5 v4 v2 v3 v6 v1 v2 v3 v4 v5 v6
2017/3/21

62 11.5.3 欧拉公式 定义11.5.2 在平面图G的一个平面表示中，
由边所包围的其内部不包含图的结点和边的区域，称为G的一个面(Surface)， 包围该面的诸边所构成的回路称为这个面的边界(Bound)， 面r的边界的长度称为该面的次数(Degree)，记为D(r)。 区域面积有限的面称为有限面(Finite Surface)，区域面积无限的面称为无限面(Infinite Surface)。 平面图有且仅有一个无限面。 2017/3/21

63 面的形象描述： 假设我们把一个平面图的平面表示画在平面上，然后用一把小刀，沿着图的边切开，那么平面就被切成许多块，每一块就是图的一个面。
更确切地说，平面图的一个面就是平面的一块，它用边作边界线，且不能再分成子块。 2017/3/21

64 注意：对于平面图的不同平面表示，虽然面的数目相同，但各面的边界和次数会不同。
例11.5.2 考察下图所示平面图的面、边界和次数。 解 平面图把平面分成4个面： r0，边界为abdeheca，D(r0)=7 r1，边界为abca，D(r1)=3 r2，边界为becb，D(r2)=9 r3，边界为bdeb，D(r3)=3 r1、r2和r3是有限面，r0是无限面。 i j a b d e c h k r0 r1 r2 r3 a b d e c h i j k r0 r1 r2 r3 注意：对于平面图的不同平面表示，虽然面的数目相同，但各面的边界和次数会不同。 2017/3/21

65 定理11.5.1 平面图中所有面的次数之和等于边数的二倍。
证明 因任何一条边，或者是两个面边界的公共边，或者是在一个面中作为边界被重复计算两次，故平面图所有面的次数之和等于其边数的二倍。 1750年，欧拉发现，任何一个凸多面体，若有n个顶点、m条棱和r个面，则有n-m+r = 2。这个公式可以推广到平面图上来，称之为欧拉公式。 2017/3/21

66 欧拉公式 定理11.5.2 设G = <V, E>是连通平面图，若它有n个结点、m条边和r个面，则有 n-m+r = 2
证明 我们对G的边数m进行归纳。 若m = 0，由于G是连通图，故必有n = 1，这时只有一个无限面，即r = 1。所以 n-m+r = = 2 定理成立。 2017/3/21

67 证明 若m=1，这时有两种情况： （1）该边是自回路，则有n=1，r=2，这时 n-m+r=1-1+2=2
假设对少于m条边的所有连通平面图，欧拉公式成立。现考虑m条边的连通平面图，设它有n个结点。分以下两种情况： 2017/3/21

68 证明(续) （1）若G是树，那么m=n-1，这时r=1。所以 n-m+r=n-(n-1)+1=2
（2）若G不是树，则G中必有回路，因此有基本回路，设e是某基本回路的一条边，则G’=<V,E-{e}>仍是连通平面图，它有n个结点，m-1条边和r-1个面，按归纳假设知 n-(m-1)+(r-1)=2 整理得 n-m+r=2 所以对m条边时，欧拉公式也成立。 2017/3/21

69 推论11.5.1 设G是一个(n,m)简单连通平面图，若m＞1，则有 m≤3n-6
证明 设G有k个面，因为G是简单图，所以G的每个面至少由3条边围成，所以G所有面的次数之和 代入欧拉公式有 2＝n-m+k≤n-m+2m/3 即 2≤n-m/3 整理得 m≤3n-6 由定理11.5.1知，2m≥3k，即k≤2m/3， 2017/3/21

70 说明 推论11.5.1本身可能用处不大，但它的逆否命题却非常有用，可以用它来判定某些图是非平面图。即
一个简单连通图，若不满足m≤3n-6，则一定是非平面图。 但需要注意，满足不等式m≤3n-6的简单连通图未必是平面图。 2017/3/21

71 例11.5.3 证明5个结点的完全图K5是非平面图。 分析 因为K5是简单连通图，我们可以验证m≤ 3n-6不成立，因此它不是平面图。
证明 因为K5是简单连通图，n=5，m=10，因此m＞ 3n-6=3×5-6=9，故不满足m≤3n-6，因此它不是平 面图。 再看图K3,3，n=6，m=9，满足不等式m≤3n-6， 但是我们已用观察法证明了它是一个非平面图。 2017/3/21

72 推论11.5.2 设G是一个(n, m)简单连通平面图，若每个面的次数至少为k(k≥3)，则有 证明 设G共有r个面，各面的次数之和为T，
由条件可知 T≥k×r 又由定理11.5.1知 T = 2×m 利用欧拉公式解出面数 r = 2-n+m 由此得出下式成立 2×m≥k×(2-n+m) 从而有 (k-2)×m ≤ k×(n-2) 由于k≥3，因而结论成立 2017/3/21

73 说明 推论11.5.2本身可能用处不大，但它的逆否命题却非常有用，可以用它来判定某些图是非平面图。即
一个简单连通图，若每个面的次数至少为k(k≥3)，若不满足 ，则一定是非平面图。 2017/3/21

74 例11.5.4 不使用观察法证明图K3,3是一个非平面图。 证明 利用推论11.5.2可以判断。事实上，假设K3,3是一个平面图，那么它的每个面的次数均不能小于等于3，即每个面的次数均大于等于k(k≥4)，由推论11.5.2，有 注意到 在k=4时取最大值2，因而9≤8，这是矛盾的。 2017/3/21

75 库拉托夫斯基定理 定理11.5.3(库拉托夫斯基定理) 一个图是平面图 的充分必要条件是它的任何子图都不可能收缩为K5 或K3,3。 推论 一个图是非平面图的充分必要条件是 它存在一个能收缩为K5或K3,3的子图。 我们将K5和K3,3称为库拉托夫斯基图 (Kuratowski Graph)。 2017/3/21

76 例11.5.5 下图所示的彼得森图是一个非平面图。 方法二：找到子图，
v1 v2 v3 v4 v5 u1 u2 u3 u4 u5 v1 v2 v3 v4 v5 u1 u2 u3 u4 u5 w4 w1 w2 w3 w5 v1 w2 w3 w4 w5 u1 方法二：找到子图， 收缩边(vi,ui)，用wi代替，i=2,3,4,5，得到图即为K3,3。 证明 方法一：收缩边(vi, ui)，用wi代替，i = 1, 2, 3, 4, 5，得到图即为K5。 2017/3/21

77 P333-P335 （a） 28 2017/3/21

78 Thank You !