1、第第7章章图图论论习题课习题课离离 散散 数数 学学河南工业大学信息科学与工程学院信息科学与工程学院第1页复复习习时时注注意意n准确掌握每个概念准确掌握每个概念n灵活应用所学定理灵活应用所学定理n注意解题思绪清楚注意解题思绪清楚n证实问题时，先用反向思维证实问题时，先用反向思维(从结论入手从结论入手)分析问分析问题，再按正向思维写出证实过程。题，再按正向思维写出证实过程。第2页 图图 通路与回路通路与回路 图连通性图连通性 欧拉图欧拉图 汉密尔顿图汉密尔顿图 无向树及其性质无向树及其性质 平面图基本性质平面图基本性质 欧拉公式欧拉公式 平面图对偶图平面图对偶图 地图着色与平地图着色与平面图着色
2、面图着色 平面图判断平面图判断 图矩阵表示图矩阵表示 无向树及其性质无向树及其性质 根树及其应用根树及其应用 无向树及其性质无向树及其性质图论结构图第3页第4页一、无向图与有向图n1、基本概念。、基本概念。n有向图与无向图定义；有向图与无向图定义；有向边有向边,无向边无向边,平行边平行边,环环,孤立结点孤立结点n关联与邻接关联与邻接(相邻相邻)；n结点度数；结点度数；结点度结点度,结点出度结点出度,结点入度结点入度,图最图最大度大度(G),最小度最小度(G),n零图与平凡图；简单图与多重图；零图与平凡图；简单图与多重图；n完全图；子图，完全图；子图，生成子图，生成子图，补图；图同构。补图；图同
3、构。n2、利用。、利用。n(1)灵活利用握手定理及其推论，灵活利用握手定理及其推论，n(2)判断两个图是否同构，判断两个图是否同构，n(3)画出满足一些条件子图，补图等。画出满足一些条件子图，补图等。第5页二、通路、回路、图连通性n1、基本概念、基本概念n路，回路，迹，路，回路，迹，通路，圈通路，圈n无向图和有向图中结点之间可达关系；无向图和有向图中结点之间可达关系；连通图，连通图，连通分支，连通分支数连通分支，连通分支数W(G)n点割集，割点，点连通度点割集，割点，点连通度k(G)n边割集，割边边割集，割边(桥桥)，边连通度，边连通度(G)n短程线，距离短程线，距离n有向图连通分类，有向图连
4、通分类，强连通，单侧连通，弱连通，强连通，单侧连通，弱连通，强分图，单侧分图，弱分图强分图，单侧分图，弱分图2、利用、利用n(1)判断有向图或无向图中通路判断有向图或无向图中通路(回路回路)类型。类型。n(2)求短程线和距离。求短程线和距离。n(3)判断有向图连通类型。判断有向图连通类型。第6页三、图矩阵表示n1、基本概念。、基本概念。n无向图无向图邻接矩阵邻接矩阵An依据邻接矩阵判断依据邻接矩阵判断:各结点度各结点度,有向图结点出有向图结点出,入度。入度。n由由Ak能够求一个结点到另一个结点长度为能够求一个结点到另一个结点长度为k路条数路条数.n有向图有向图可达矩阵可达矩阵Pn用用P能够判定
5、能够判定:各结点度各结点度.有向图强分图。有向图强分图。n关联矩阵关联矩阵M:是结点与边关联关系矩阵是结点与边关联关系矩阵.用用M判定判定:各结点度各结点度第7页主要定理：主要定理：握手定理及其推论握手定理及其推论n推论推论：任何图任何图(无向或有向无向或有向)中，奇度结点个数中，奇度结点个数是偶数。是偶数。无向图：无向图：有向图：有向图：且且第8页(1)(2)(3)多重图不是经典题经典题设图设图G=，其中，其中V=a,b,c,d,e，E分别由下面给分别由下面给出。判断哪些是简单图，哪些是多重图？出。判断哪些是简单图，哪些是多重图？简单图第9页以下各序列中，能够组成无向简单图度数序列以下各序列
6、中，能够组成无向简单图度数序列有哪些？有哪些？(1)(2,2,2,2,2)能够能够(2)(1,1,2,2,3)不能够不能够(3)(1,1,2,2,2)能够能够(4)(0,1,3,3,3)不能够不能够(5)(1,3,4,4,5)不能够不能够第10页图图G如右图所表示，以下说法正确是如右图所表示，以下说法正确是()A(a,d)是割边是割边B(a,d)是边割集是边割集C(d,e)是边割集是边割集D(a,d),(a,c)是边割集是边割集n正确答案是：正确答案是：C。n对割边、边割集概念了解到位。对割边、边割集概念了解到位。n定义定义设无向图设无向图G=为连通图，若有边集为连通图，若有边集E1 E，使图
7、，使图G删除了删除了E1全部边后，所得子图是不连通图，全部边后，所得子图是不连通图，而删除了而删除了E1任何真子集后，所得子图是连通图，则任何真子集后，所得子图是连通图，则称称E1是是G一个边割集若某个边组成一个边割集，一个边割集若某个边组成一个边割集，则称该边为割边（或桥）则称该边为割边（或桥）n假如答案假如答案A正确，即删除边正确，即删除边(a,d)后，得到图是不连后，得到图是不连通图，但实际上它还是连通。所以通图，但实际上它还是连通。所以答案答案A是错误。是错误。第11页设给定图设给定图G(如由图所表示如由图所表示)，则图，则图G点割集是点割集是应该填写：应该填写：f，c，e。n定义定义
8、设无向图设无向图G=为连通图，若有点集为连通图，若有点集V1 V，使图，使图G删除了删除了V1全部结点后，所得子图是全部结点后，所得子图是不连通图，而删除了不连通图，而删除了V1任何真子集后，所得子图任何真子集后，所得子图是连通图，则称是连通图，则称V1是是G一个点割集若某个结点一个点割集若某个结点组成一个点割集，则称该结点为割点。组成一个点割集，则称该结点为割点。nf，c是不满定义，因为是不满定义，因为f是是f，c真子集，而真子集，而删除删除f后，图是不连通。后，图是不连通。第12页单向连通单向连通强连通强连通强连通强连通下列图所表示六个图中，强连通，单向连通，弱连下列图所表示六个图中，强连
9、通，单向连通，弱连通通分别有哪些？分别有哪些？强连通强连通单向连通单向连通弱连通弱连通第13页设图设图G邻接矩阵为邻接矩阵为则则G边数为边数为()A5B6C3D4n正确答案是：正确答案是：D。n当给定简单图是无向图时，邻当给定简单图是无向图时，邻接矩阵为对称即当结点接矩阵为对称即当结点vi与与vj相邻时，结点相邻时，结点vj与与vi也相邻，也相邻，所以连接结点所以连接结点vi与与vj一条边在一条边在邻接矩阵第邻接矩阵第i行第行第j列处和第列处和第j行行第第i列处各有一个列处各有一个1，题中给出，题中给出邻接矩阵中共有邻接矩阵中共有8个个1，故有，故有8 2=4条边。度数之和等于条边。度数之和等
10、于2倍边数。倍边数。第14页n(1)D是哪类连通图是哪类连通图?n(2)D中中v1到到v4长度为长度为1,2,3,4通路各多少通路各多少条？条？n(3)D中长度为中长度为4通路（不含回路）有多通路（不含回路）有多少条？少条？n(4)D中长度为中长度为4回路有多少条？回路有多少条？n(5)D中长度中长度4通路有多少条？其中有通路有多少条？其中有几条是回路？几条是回路？n(6)写出写出D可达矩阵。可达矩阵。有向图有向图D如图所表示，回答以下问题：如图所表示，回答以下问题：第15页有向图有向图D如图所表示，回答以下诸问：如图所表示，回答以下诸问：n(1)D是哪类连通图是哪类连通图?nD是强连通图。是
11、强连通图。n解答为解解答为解(2)(6)，只需先求，只需先求D邻邻接矩阵前接矩阵前4次幂。次幂。第16页n(2)D中中v1到到v1长度为长度为1,2,3,4回路各多少条？回路各多少条？n答：答：v1到到v1长度为长度为1,2,3,4回路数分别为回路数分别为1,1,3,5。n(3)D中长度为中长度为4通路（不含回路）有多少条？通路（不含回路）有多少条？n答：长度为答：长度为4通路通路(不含回路不含回路)为为33条条.n(4)D中长度为中长度为4回路有多少条？回路有多少条？n答：答：长度为长度为4回路为回路为11条。条。n(5)D中长度中长度 4通路有多少条？其中有几条是回路？通路有多少条？其中有
12、几条是回路？n答：长度答：长度 4通路通路88条，其中条，其中22条为回路。条为回路。n(6)写出写出D可达矩阵。可达矩阵。n4 4全全1矩阵。矩阵。第17页简单无向图简单无向图G必有必有2结点同度数。结点同度数。证证:令令G=v1,vn，n若若G中中没有孤立点没有孤立点,则则G中中n个结点度只取个结点度只取n-1个可个可能值：能值：1,2,n-1，从而，从而G中最少有两个结点度数相中最少有两个结点度数相同。同。n不然不然，G中有孤立点，不妨设中有孤立点，不妨设vk,vn为全部孤立点为全部孤立点,则则v1,vk-1度只取度只取k-2个可能值个可能值:1,2,k-2，从而此，从而此k-1个结点中
13、最少有两个同度数点。个结点中最少有两个同度数点。第18页握手定理及其推论应用握手定理及其推论应用n设无向图设无向图G有有10条边，条边，3度与度与4度结点各度结点各2个，其余个，其余结点度数均小于结点度数均小于3，问，问G中最少有几个结点？在最中最少有几个结点？在最少结点情况下，写出少结点情况下，写出G度数列度数列(G)、(G)。n设设G阶数为阶数为n，4个结点度数分别为个结点度数分别为3，3，4，4,其余其余n-4个结点度数均小于或等于个结点度数均小于或等于2，由握手定理可得，由握手定理可得n2(3+4)+(n-4)2=14+2n-8deg(vi)=2m=20n解此不等式可得解此不等式可得n
14、7，即，即G中最少有中最少有7个结点，个结点，7个结点时，其度数列为个结点时，其度数列为2,2,2,3,3,4,4，=4,=2。第19页(1)设设n阶图阶图G中有中有m条边，证实：条边，证实：(G)2m/n(G)(2)n阶非连通简单图边数最多可为多少？最少呢？阶非连通简单图边数最多可为多少？最少呢？n(1)证实中关键步骤是握手定理：证实中关键步骤是握手定理：2m=deg(vi)(G)deg(vi)(G)，于是得，于是得nn(G)2mn(G)(G)2m/n(G)n易知易知2m/n为为G平均度数，因而它大于或等于最平均度数，因而它大于或等于最小度小度(G)，小于或等于最大度，小于或等于最大度(G)
15、。n(2)n阶非连通简单图边数最多可为阶非连通简单图边数最多可为n-1阶连通图加上阶连通图加上一个孤立点，所以边数为一个孤立点，所以边数为(n-1)(n-2)/2，最少为，最少为0。第20页 一个图假如同构于它补图，则该图称为自补图。一个图假如同构于它补图，则该图称为自补图。1)一个图是自补图，其对应完全图边数必为偶数一个图是自补图，其对应完全图边数必为偶数2)证实：若证实：若n阶无向简单图是自补图，则阶无向简单图是自补图，则n=4k或或n=4k+1（k为正整数）。为正整数）。解：解：n1)设图设图G是自补图，是自补图，G有有e条边，条边，G对应完全图边数对应完全图边数为为A。G补图补图G边数
16、应为边数应为A一一e。因为。因为GG，故故边数相等，边数相等，e=A一一e，A2e，所以，所以G对应完全图边对应完全图边数数A为偶数。为偶数。n2)由由1)可知，自补图对应完全图边数为偶数。可知，自补图对应完全图边数为偶数。n个结个结点完全图点完全图Kn边数为边数为n(n-1)/2，所以所以n(n-1)/2=2m，即，即n(n-1)=4m，因而，因而nn为为4倍数，即倍数，即n=4k，n或或n-1为为4倍数，即倍数，即n=4k+1，n即即n=0,1(mod4)。第21页对于任何一个含有对于任何一个含有6个结点简单图，要么它包含一个结点简单图，要么它包含一个三角形，要么它补图包含一个三角形。个三
17、角形，要么它补图包含一个三角形。解：解：n设设6个结点简单图为个结点简单图为G。考查。考查G中任意一个结点中任意一个结点a，那么，另外那么，另外6个结点中任何一个结点，要么在个结点中任何一个结点，要么在G中与中与a邻接，要么在邻接，要么在G补图补图G中与中与a邻接。这么，就可把邻接。这么，就可把5个结点分成两类，将那些在个结点分成两类，将那些在G中与中与a邻接结点归成一邻接结点归成一类，而将那些在类，而将那些在G中与中与a邻接结点归在另一类。于是邻接结点归在另一类。于是必有一类最少含有三个结点，不妨假设其中三个结必有一类最少含有三个结点，不妨假设其中三个结点为点为b，c，d，如图所表示。若边，
18、如图所表示。若边(b，c)，(c，d)，(b，d)中有一条在中有一条在G中，那么这条边所关联两个结中，那么这条边所关联两个结点都与点都与a邻接形成一个三角形；若边邻接形成一个三角形；若边(b，c)，(c，d)，(b,d)都不在都不在G中，则中，则(b，c)，(c，d)，(b,d)形形成一个三角形。成一个三角形。第22页abcdbcdbcdbcd推论推论:任何任何6人人群中，或者有人人群中，或者有3人相互认识，或者有人相互认识，或者有3人彼此陌生。人彼此陌生。(当二人当二人x,y相互认识，边相互认识，边(x,y)着红色，着红色，不然着兰色。则不然着兰色。则6人认识情况对应于人认识情况对应于K6边
19、有红边有红K3或者或者有兰有兰K3。)aaa第23页证实简单图最大度小于结点数。证实简单图最大度小于结点数。证实：证实：n设简单图设简单图G有有n个结点。对任一结点个结点。对任一结点u，因为，因为G没有没有环和平行边，环和平行边，u至多与其余至多与其余n-1个结点中每一个有个结点中每一个有一条边相连接，即一条边相连接，即deg(u)n-1，所以，所以，(G)maxdeg(u)n-1。第24页设设G是一个是一个n阶无向简单图，阶无向简单图，n是大于等于是大于等于3奇奇数。证实图数。证实图G与它补图中度数为奇数结点个数与它补图中度数为奇数结点个数相等。相等。证实：证实：n因为因为G是是n阶无向简单
20、图，且阶无向简单图，且n是大于等于是大于等于3奇数，奇数，故无向图结点数为奇数，则所对应故无向图结点数为奇数，则所对应n阶完全图中每阶完全图中每个结点度数为个结点度数为n-1即为偶数，即为偶数，n利用奇数利用奇数+奇数奇数=偶数，偶数偶数，偶数+偶数偶数=偶数，所以，偶数，所以，在在G中结点度数为奇数结点，在其补图中度数也中结点度数为奇数结点，在其补图中度数也应为奇数，故应为奇数，故G和其补图奇数结点个数也是相同。和其补图奇数结点个数也是相同。第25页P2861、在无向图、在无向图G中，从结点中，从结点u到结点到结点v有一条长度为有一条长度为偶数通路，从结点偶数通路，从结点u到结点到结点v又有
21、一条长度为奇数又有一条长度为奇数通路，则在通路，则在G中必有一条长度为奇数回路。中必有一条长度为奇数回路。证实证实：n设从结点设从结点u到结点到结点v长度为偶数通路是长度为偶数通路是ue1u1e2u2e2kv，n长度为奇数通路是长度为奇数通路是ue11u11e12u12e12h-1v，n那么路那么路ue1u1e2u2e2kve12h-1u12e12u11e11u就是一条回就是一条回路，它边数路，它边数2k+(2h-1)2(h+k)-1，是奇数，故这条，是奇数，故这条回路长度是奇数。回路长度是奇数。第26页P2862、无向图、无向图G恰有恰有2个奇数度数结点可达。个奇数度数结点可达。解解1：令令
22、u,w为为G恰有恰有2个奇度结点。考查个奇度结点。考查u所在连通分支所在连通分支G。因图。因图G奇度点为偶数，故奇度点为偶数，故G最少还有另一奇度最少还有另一奇度点点w，但，但v在在G和和G中有相同度，所以中有相同度，所以G恰有恰有2个奇度个奇度点而且就是点而且就是u和和w。再由。再由G连通性推出连通性推出u到到w可达。可达。解解2：反证法反证法n设设G中两个奇度结点为中两个奇度结点为u与与v，若，若u与与v不连通，即它不连通，即它们之间无路，因而们之间无路，因而u与与v处于处于G中恰有不一样连通分中恰有不一样连通分支中，设支中，设u在在G1中，中，v在在G2中，中，G1与与G2是是G连通分连
23、通分支，因为支，因为G中恰有两个奇度结点，因而看成为独立中恰有两个奇度结点，因而看成为独立图时，都有一个奇度结点，这与握手定理推论相矛图时，都有一个奇度结点，这与握手定理推论相矛盾。盾。第27页3、若图、若图G是不连通，则是不连通，则G补图补图G是连通。是连通。证实：证实：n若图若图G是不连通，可设图是不连通，可设图G连通分支是连通分支是G(V1)，G(V2)，G(Vm)(m2)。因为任意两个连。因为任意两个连通分支通分支G(Vi)与与G(Vj)(ij)之间不连通，所以两个结之间不连通，所以两个结点子集点子集Vi与与Vj之间全部连线都在图之间全部连线都在图G补图补图G中。任取中。任取两个结点两
24、个结点u和和v，有两种情形：，有两种情形：na)u和和v分别属于两个不一样结点子集分别属于两个不一样结点子集Vi与与Vj。由上。由上可知可知G包含边包含边(u，v)，故，故u和和v在在G中是连通。中是连通。nb)u和和v属于同属于同个结点子集个结点子集Vi。可在另一个结点子。可在另一个结点子集集Vj中取一个结点中取一个结点w，由上可知边，由上可知边(u,w)及边及边(v,w)均在均在G中，故邻接边中，故邻接边(u,w)和和(w,v)组成路连接结点组成路连接结点u和和v，即，即u和和v在在G中也是连通。中也是连通。n由此可知，当图由此可知，当图G不是连通图时，不是连通图时，G必是连通图。必是连通
25、图。第28页在含有在含有n个结点个结点无向简单图无向简单图G中中，若任意若任意2个不个不一样结点度数之和大于等于一样结点度数之和大于等于n-1，则图，则图G是连是连通图。通图。证实：证实：反证法反证法n设图设图G不是连通图，不妨设图不是连通图，不妨设图G有有2个连通分支个连通分支G1和和G2，其中，其中G1有有k(k1)个结点，个结点，G2有有n-k个结个结点。在点。在G1中任取一点中任取一点vi，G2中任取一点中任取一点vj，则，则:ndeg(vi)k-1ndeg(vj)(n-k)-1n由此可得由此可得:ndeg(vi)+deg(vj)(k-1)+(n-k)-1=n-2与题设矛盾，故图与题设
26、矛盾，故图G是连通图。是连通图。第29页证实证实n个结点个结点k条边简单图条边简单图G，若，若k(n-1)(n-2)/2，则图，则图G是连通图。是连通图。证实：证实：反证法反证法设设G补图为补图为G，边数记为，边数记为kG，则则kG+kG=n(n-1)/2，假设假设G不连通，则不连通，则G补图是连通，补图是连通，kGn-1kG+kGkG+n-1，利用利用kG+kG=n(n-1)/2；推出推出kG(n-1)(n-2)/2，和题设矛盾；和题设矛盾；故图故图G是连通图。是连通图。第30页n（渡渡河河问问题题）一一个个摆摆渡渡人人，要要把把一一只只狼狼、一一只只羊羊和和一一捆捆干干草草运运过过河河去去
27、，河河上上有有一一只只木木船船，每每次次除除了了人人以以外外，只只能能带带一一样样东东西西。另另外外，假假如如人人不不在在旁旁时时，狼狼就就要要吃吃羊羊，羊羊就就要要吃干草。吃干草。问这人怎样才能把它们运过河去？问这人怎样才能把它们运过河去？解解:用用F表示摆渡人，表示摆渡人，W表示狼，表示狼，S表示羊，表示羊，H表示干草。表示干草。n若若用用FWSH表表示示人人和和其其它它3样样东东西西在在河河左左岸岸状状态态。这这么么在在左左岸全部可能出现状态为以下岸全部可能出现状态为以下16种：种：nFWSH FWS FWH FSHnWSH FW FS FHnWS WH SH Fn W S H n这这里
28、里表表示示左左岸岸是是空空集集，即即人人、狼狼、羊羊、干干草草都都已已运运到到右右岸去了。岸去了。利用通路概念处理一个古老著名问题。利用通路概念处理一个古老著名问题。第31页n依据题意检验一下就能够知道，依据题意检验一下就能够知道，nFWSH FWS FWH FSH WSH FW n FS FH WS WH SH F W S H n这这16种情况中有种情况中有6种情况是不允许出现。种情况是不允许出现。n它它们们是是：WSH、FW、FH、WS、SH、F。如如FH表表示示人人和和干干草草在在左左岸岸，而而狼狼和和羊羊在在右右岸岸，这这当当然是不行。然是不行。所以，所以，允许出现情况只有允许出现情况
29、只有10种。种。n我我们们结结构构一一个个图图，它它结结点点就就是是这这10种种状状态态。若若一一个个状状态态能能够够转转移移到到另另一一个个状状态态，就就在在表表示示它它们们两两结结点点间间连连一一条条边边，这这么么就就画画出出图图。本本题题就就转转化化为为找找结结点点FWSH到到结结点点通通路路。从从图图中中得得到到两两条条这这么么通通路路，即有两种渡河方案。即有两种渡河方案。FWSH WHFWHHWFSHFSWSFS第32页欧拉路，欧拉回路，欧拉图。欧拉路，欧拉回路，欧拉图。判定判定:n有欧拉路充要条件：有欧拉路充要条件：无或有两个奇数度结点。无或有两个奇数度结点。n有欧拉回路充要条件：
30、有欧拉回路充要条件：全部结点度数均为偶数。全部结点度数均为偶数。汉密尔顿路，汉密尔顿回路，汉密尔顿图汉密尔顿路，汉密尔顿回路，汉密尔顿图汉密尔顿图判定汉密尔顿图判定:n必要条件：必要条件：设无向图设无向图G=是是汉密尔顿汉密尔顿图，则图，则对于任意对于任意非空子集非空子集S，有，有W(G-S)|S|。n推论推论设无向图设无向图G=是半是半汉密尔顿汉密尔顿图，则对图，则对于任意于任意非空子集非空子集S，有，有W(G-S)|S|+1。n充分条件：若简单图充分条件：若简单图G中每对结点度数和中每对结点度数和|V|=n，则，则G是汉密尔顿图。是汉密尔顿图。n半汉密尔顿图，若简单图半汉密尔顿图，若简单图
31、G中每对结点度数和中每对结点度数和|V|-1，则，则G是半汉密尔顿图。是半汉密尔顿图。四、欧拉图与汉密尔顿图四、欧拉图与汉密尔顿图(会判定会判定)第33页P3112试结构一个欧拉图，其结点数试结构一个欧拉图，其结点数v和边数和边数e满足下满足下述条件述条件(1)v和和e奇偶性相同；奇偶性相同；(2)v和和e奇偶性相反。奇偶性相反。n解：解：(1)(2)说明：欧拉图中，结点数和边数奇偶性既说明：欧拉图中，结点数和边数奇偶性既能够相同也能够相反。能够相同也能够相反。第34页 nn个结点有向完全图，哪些是有向欧拉图，为何？个结点有向完全图，哪些是有向欧拉图，为何？解：解：nn个结点有向完全图是有向欧
32、拉图，对于个结点有向完全图是有向欧拉图，对于n个结点有个结点有向完全图，每个结点度数均相等，都是偶数向完全图，每个结点度数均相等，都是偶数2(n-1)，且每个结点入度且每个结点入度=出度，所以出度，所以n个结点有向完全图是个结点有向完全图是有向欧拉图。有向欧拉图。n无向完全图无向完全图Kn是几笔画图？为何？是几笔画图？为何？n(1)当当n=1时，时，Kn为平凡图；为平凡图；n(2)当当n=奇数时，奇数时，Kn中每个结点度数中每个结点度数=n-1为偶数，为偶数，所以所以Kn为欧拉图，能够一笔画出；为欧拉图，能够一笔画出；n(3)当当n=偶数时，偶数时，Kn中每个结点度数中每个结点度数=n-1为奇
33、数，为奇数，对应有对应有n/2对奇数度结点，所以能够对奇数度结点，所以能够n/2笔画出。笔画出。第35页n删除删除A和和B后，形成后，形成3个连通分支，个连通分支，n即即W(G-S)=3|S|=2所以，图所以，图G不是汉密尔顿图。不是汉密尔顿图。图图G是否是汉密尔顿图。是否是汉密尔顿图。AB第36页7位客人入席，位客人入席，A只会讲英语，只会讲英语，B会讲英，汉语，会讲英，汉语，C会讲英，意大利，俄语，会讲英，意大利，俄语，D会讲日，汉语，会讲日，汉语，E会讲德，意大利语，会讲德，意大利语，F会讲法，日，俄语，会讲法，日，俄语，G会讲法，德语。能否安排圆桌席位使每位客人与会讲法，德语。能否安排
34、圆桌席位使每位客人与其左右邻不用翻译便可交谈其左右邻不用翻译便可交谈?解：解：建立无向图模型建立无向图模型:结点为客人；结点为客人；会共同语言会共同语言2结点相邻接。结点相邻接。则问题则问题归结为归结为求此图一条求此图一条汉密尔顿回路汉密尔顿回路。不难验证，此图有一条汉密尔顿不难验证，此图有一条汉密尔顿回路是回路是:(A,B,D,F,G,E,C,A)。按此回路安排席位可按此回路安排席位可以以使得每个人都能够和它两边人直接交谈。使得每个人都能够和它两边人直接交谈。汉密尔顿图汉密尔顿图应用应用BCDEFGA英英英英法法德德俄俄意意日日汉汉第37页某地有某地有5个风景点，若每个风景点都有个风景点，若
35、每个风景点都有2条道路与其条道路与其它点相通。问游人可否经过每个风景点恰好一次而它点相通。问游人可否经过每个风景点恰好一次而游完这游完这5处？处？解：解：n将将5个风景点看成是有个风景点看成是有5个结点无向图，两风景点个结点无向图，两风景点间道路看成是无向图边间道路看成是无向图边，n因为每处都有两条道路与其它结点相通，故每个因为每处都有两条道路与其它结点相通，故每个结点度数均为结点度数均为2，n从而任意两个不相邻结点度数之和等于从而任意两个不相邻结点度数之和等于4，恰好为，恰好为总结点数减总结点数减1。n故此图中存在一条故此图中存在一条汉密尔顿路汉密尔顿路，所以游人能够经，所以游人能够经过每个
36、风景点恰好一次而游完这过每个风景点恰好一次而游完这5处。处。第38页设图设图G有有n个结点，个结点，e条边，证实：若条边，证实：若，则则G为汉密尔顿图。为汉密尔顿图。证实：证实：反证法反证法n假设假设G不是汉密尔顿图，则依据汉密尔顿图判定定不是汉密尔顿图，则依据汉密尔顿图判定定理，知最少存在两个结点度数之和小于理，知最少存在两个结点度数之和小于n，则该两个，则该两个结点所关联边数目结点所关联边数目m1小于小于n，即，即m1n-1，而当其余，而当其余n-2个结点组成完全图时，其所关联边数目个结点组成完全图时，其所关联边数目m2为最为最大值，即大值，即m2(n-2)(n-3)/2。nG总边数为总边
37、数为m1+m2，从而，从而n与题设与题设矛盾。矛盾。n所以，图所以，图G为汉密尔顿图。为汉密尔顿图。第39页将将6个人分成个人分成3组（每组组（每组2个人）去完成个人）去完成3项任务。已项任务。已知每个人最少与其余知每个人最少与其余5个人中个人中3个人能相互合作。问：个人能相互合作。问：能否使得每组能否使得每组2个人都能相互合作？请说明理由。个人都能相互合作？请说明理由。解：解：n用用v1,v2,v6代表代表6个人，若个人，若vi,vj能相互合作，能相互合作，就在就在vi与与vj之间连无向边，得无向图之间连无向边，得无向图G=(V,E)。n由已知条件可知，对于任意由已知条件可知，对于任意viV
38、,deg(vi)n/2，所以所以deg(vi)+deg(vj)n，由定理可知，由定理可知G是汉密尔是汉密尔顿图，顿图，n因而因而G中存在汉密尔顿回路，不妨设中存在汉密尔顿回路，不妨设C=vi1vi2vi3vi4vi5vi6vi1为其中一条，在这种回路上相为其中一条，在这种回路上相邻两个结点代表二人能相互合作。邻两个结点代表二人能相互合作。第40页某工厂生产由某工厂生产由6种不一样颜色纱织成双色布，已知在品种不一样颜色纱织成双色布，已知在品种中，每种颜色最少分别和其它种中，每种颜色最少分别和其它5种颜色中种颜色中3种颜色搭种颜色搭配，证实能够挑出配，证实能够挑出3种双色布，它们恰有种双色布，它们
39、恰有6种不一样颜种不一样颜色。色。解：解：n用用vi表示颜色表示颜色(i=1,26)，作无向图，作无向图G(V,E)，其，其中中V=v1,v2,v6，E=(u,v)|u,vV且且uv而且而且u与与v搭配搭配nu,vV,deg(u)+deg(v)6,所以所以G是汉密尔顿图，是汉密尔顿图，因而因而G中存在汉密尔顿回路，不妨设中存在汉密尔顿回路，不妨设v1v2v3v4v5v6v1为其中一条，在这种回路上每个结为其中一条，在这种回路上每个结点代表颜色都能与它相邻结点代表颜色相搭配，点代表颜色都能与它相邻结点代表颜色相搭配，于是让于是让v1与与v2,v3与与v4,v5与与v6搭配，织成搭配，织成3种双色
40、种双色布，包含了布，包含了6种颜色。种颜色。第41页 n以下命题中以下命题中()是正确是正确.n1.欧拉图子图一定是欧拉图欧拉图子图一定是欧拉图n2.汉密尔顿图子图一定是汉密尔顿图汉密尔顿图子图一定是汉密尔顿图第42页反证法在图论中应用反证法在图论中应用n图论这门学科理论性强，与其它数学分支学科不图论这门学科理论性强，与其它数学分支学科不一样是，在它理论证实之中反证法使用尤其多。一样是，在它理论证实之中反证法使用尤其多。反证法最大优点是无形中多了一个或几个条件，反证法最大优点是无形中多了一个或几个条件，所以在图论中证实有些命题时，若感到条件所以在图论中证实有些命题时，若感到条件“不不足足”或无
41、从下手，不妨考虑使用反证法。用反证或无从下手，不妨考虑使用反证法。用反证法证实图论命题有时能起到其它方法所办不到功法证实图论命题有时能起到其它方法所办不到功效，下面从几个不一样类型出发，结适当当实例效，下面从几个不一样类型出发，结适当当实例介绍反证法在图论中应用。介绍反证法在图论中应用。第43页相关相关“存在性存在性”问题问题n在简单图在简单图G 中，若中，若v(G)2，则在，则在G 中必存在度数中必存在度数相等两个结点。相等两个结点。证：证：设图设图G 中各点度均不相等，那么必有最大度中各点度均不相等，那么必有最大度nv 1。若。若=v 1，必有，必有1，从而，从而，-+1v 1，又与，又与
42、G是简单图矛盾。是简单图矛盾。第44页相关包括“最少”问题n若若G 是是k 树，试证树，试证G 最少有最少有k 个结点度为个结点度为1。n证：若证：若G 中度为中度为1结点个数结点个数s 小于小于k，由度和定理得，由度和定理得，但对树但对树G 却有，二者矛盾。却有，二者矛盾。第45页有些以否定判断为结论命题有些以否定判断为结论命题若若G 中每个结点度均为偶数，试证中每个结点度均为偶数，试证G 中任何一中任何一条边都不是割边。条边都不是割边。证：证：n假设假设G 中存在割边中存在割边e，取，取G e 中含中含e 一个端点一个端点u 连连通分支为通分支为G 1，则，则G 1中除中除u 度为奇数外，
43、其余结度为奇数外，其余结点度均为偶数，这与定理点度均为偶数，这与定理“在任何图中度为奇数在任何图中度为奇数结点有偶数个结点有偶数个”相矛盾，故相矛盾，故G 中任何一条边都不中任何一条边都不是割边。是割边。第46页有些已知条件较少，或仅从已知条件出发能够得出信息知之甚少问题若一个连通图若一个连通图G 每条边都是割边，则每条边都是割边，则G 是树。是树。n证：假设证：假设G 是连通图但不是树，则包含一个圈是连通图但不是树，则包含一个圈C。因为割边不应该包含在任何一个圈中，故造成矛因为割边不应该包含在任何一个圈中，故造成矛盾。盾。第47页7.采取直接证实方法不够多，或者用直采取直接证实方法不够多，或者用直接证法较困难命题接证法较困难命题n例例7：若：若e 不包含在不包含在G一个圈中，试证一个圈中，试证e 是是G割边。割边。n证：证：假设假设e=xy 不是不是G 割边，割边，则。因为在则。因为在G 中存中存在一条在一条(x,y)路（即路（即xy），所以），所以x 和和y 都在都在G 同一同一个分支中。由此推知个分支中。由此推知x 和和y 在在G e 同一个分支中，同一个分支中，从而在从而在G-e中存在一条中存在一条(x,y)路路p，于是，于是e就位于就位于G圈中，造成矛盾。圈中，造成矛盾。第48页
