离散数学--第七章-图论---习题课PPT参考课件.ppt

《离散数学--第七章-图论---习题课PPT参考课件.ppt》由会员分享，可在线阅读，更多相关《离散数学--第七章-图论---习题课PPT参考课件.ppt（48页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第第7章章图图论论习题课习题课离离 散散 数数 学学河南工业大学信息科学与工程学院信息科学与工程学院1复复习习时时注注意意n准确掌握每个概念准确掌握每个概念n灵活应用所学定理灵活应用所学定理n注意解题思路清晰注意解题思路清晰n证明问题时，先用反向思维证明问题时，先用反向思维(从结论入手从结论入手)分析问分析问题，再按正向思维写出证明过程。题，再按正向思维写出证明过程。2 图图 通路与回路通路与回路 图的连通性图的连通性 欧拉图欧拉图 汉密尔顿图汉密尔顿图 无向树及其性质无向树及其性质 平面图的基本性质平面图的基本性质 欧拉公式欧拉公式 平面图的对偶图平面图的对偶图 地图着色与平地图着色与平面图

2、着色面图着色 平面图的判断平面图的判断 图的矩阵表示图的矩阵表示 无向树及其性质无向树及其性质 根树及其应用根树及其应用 无向树及其性质无向树及其性质图论的结构图34一、无向图与有向图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短程线，距

4、离短程线，距离n有向图连通的分类，有向图连通的分类，强连通，单侧连通，弱连强连通，单侧连通，弱连通，通，强分图，单侧分图，弱分图强分图，单侧分图，弱分图2、运用、运用n(1)判断有向图或无向图中通路判断有向图或无向图中通路(回路回路)的类型。的类型。n(2)求短程线和距离。求短程线和距离。n(3)判断有向图连通的类型。判断有向图连通的类型。6三、图的矩阵表示n1、基本概念。、基本概念。n无向图的无向图的邻接矩阵邻接矩阵An根据邻接矩阵判断根据邻接矩阵判断:各结点的度各结点的度,有向图结点有向图结点出出,入度。入度。n由由Ak可以求一个结点到另一个结点长度为可以求一个结点到另一个结点长度为k的路

5、条数的路条数.n有向图的有向图的可达矩阵可达矩阵Pn用用P可以判定可以判定:各结点的度各结点的度.有向图的强分图。有向图的强分图。n关联矩阵关联矩阵M:是结点与边的关联关系矩阵是结点与边的关联关系矩阵.用用M判定判定:各结点的度各结点的度7重要定理：重要定理：握手定理及其推论握手定理及其推论n推论推论：任何图任何图(无向的或有向的无向的或有向的)中，奇度结点的中，奇度结点的个数是偶数。个数是偶数。无向图：无向图：有向图：有向图：且且8(1)(2)(3)多重图不是典型题典型题设图设图G=，其中，其中V=a,b,c,d,e，E分别由下面给分别由下面给出。判断哪些是简单图，哪些是多重图？出。判断哪些

6、是简单图，哪些是多重图？简单图9下列各序列中，可以构成无向简单图的度数序列的下列各序列中，可以构成无向简单图的度数序列的有哪些？有哪些？(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对割边、边割集的概念理解到位。对割边、边割集的概念

7、理解到位。n定义定义设无向图设无向图G=为连通图，若有边集为连通图，若有边集E1 E，使图，使图G删除了删除了E1的所有边后，所得的子图是不连的所有边后，所得的子图是不连通图，而删除了通图，而删除了E1的任何真子集后，所得的子图是的任何真子集后，所得的子图是连通图，则称连通图，则称E1是是G的一个边割集若某个边构成的一个边割集若某个边构成一个边割集，则称该边为割边（或桥）一个边割集，则称该边为割边（或桥）n如果答案如果答案A正确，即删除边正确，即删除边(a,d)后，得到的图是不后，得到的图是不连通图，但事实上它还是连通的。因此连通图，但事实上它还是连通的。因此答案答案A是错是错误的。误的。11

8、设给定图设给定图G(如由图所示如由图所示)，则图，则图G的点割集是的点割集是应该填写：应该填写：f，c，e。n定义定义设无向图设无向图G=为连通图，若有点集为连通图，若有点集V1 V，使图，使图G删除了删除了V1的所有结点后，所得的子的所有结点后，所得的子图是不连通图，而删除了图是不连通图，而删除了V1的任何真子集后，所的任何真子集后，所得的子图是连通图，则称得的子图是连通图，则称V1是是G的一个点割集的一个点割集若某个结点构成一个点割集，则称该结点为割点。若某个结点构成一个点割集，则称该结点为割点。nf，c是不满定义的，因为是不满定义的，因为f是是f，c的真子集，的真子集，而删除而删除f后，

9、图是不连通的。后，图是不连通的。12单向连通单向连通强连通强连通强连通强连通下图所示的六个图中，强连通，单向连通，弱连通下图所示的六个图中，强连通，单向连通，弱连通的分别有哪些？的分别有哪些？强连通强连通单向连通单向连通弱连通弱连通13设图设图G的邻接矩阵为的邻接矩阵为则则G的边数为的边数为()A5B6C3D4n正确答案是：正确答案是：D。n当给定的简单图是无向图时，当给定的简单图是无向图时，邻接矩阵为对称的即当结邻接矩阵为对称的即当结点点vi与与vj相邻时，结点相邻时，结点vj与与vi也也相邻，所以连接结点相邻，所以连接结点vi与与vj的的一条边在邻接矩阵的第一条边在邻接矩阵的第i行第行第j

10、列处和第列处和第j行第行第i列处各有一个列处各有一个1，题中给出的邻接矩阵中共，题中给出的邻接矩阵中共有有8个个1，故有，故有8 2=4条边。度条边。度数之和等于数之和等于2倍的边数。倍的边数。14n(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的可达矩阵。的可达矩阵。有向

11、图有向图D如图所示，回答下列问题：如图所示，回答下列问题：15有向图有向图D如图所示，回答下列诸问：如图所示，回答下列诸问：n(1)D是哪类连通图是哪类连通图?nD是强连通图。是强连通图。n解答为解解答为解(2)(6)，只需先求，只需先求D的邻的邻接矩阵的前接矩阵的前4次幂。次幂。16n(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的通路的通路(不含回路不含回路

12、)为为33条条.n(4)D中长度为中长度为4的回路有多少条？的回路有多少条？n答：答：长度为长度为4的回路为的回路为11条。条。n(5)D中长度中长度 4的通路有多少条？其中有几条是回路的通路有多少条？其中有几条是回路？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中至少有两个结点

13、的度中至少有两个结点的度数相同。数相同。n否则否则，G中有孤立点，不妨设中有孤立点，不妨设vk,vn为全部孤立点为全部孤立点,则则v1,vk-1的度只取的度只取k-2个可能值个可能值:1,2,k-2，从而，从而此此k-1个结点中至少有两个同度数点。个结点中至少有两个同度数点。18握手定理及其推论的应用握手定理及其推论的应用n设无向图设无向图G有有10条边，条边，3度与度与4度结点各度结点各2个，其余个，其余结点的度数均小于结点的度数均小于3，问，问G中至少有几个结点？在中至少有几个结点？在最少结点的情况下，写出最少结点的情况下，写出G的度数列的度数列(G)、(G)。n设设G的阶数为的阶数为n，

14、4个结点的度数分别为个结点的度数分别为3，3，4，4,其余其余n-4个结点的度数均小于或等于个结点的度数均小于或等于2，由握手定理，由握手定理可得可得n2(3+4)+(n-4)2=14+2n-8deg(vi)=2m=20n解此不等式可得解此不等式可得n7，即，即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)证明中关键步骤是握手定理：证明中关键

15、步骤是握手定理：2m=deg(vi)(G)deg(vi)(G)，于是得，于是得nn(G)2mn(G)(G)2m/n(G)n易知易知2m/n为为G的平均度数，因而它大于或等于的平均度数，因而它大于或等于最小度最小度(G)，小于或等于最大度，小于或等于最大度(G)。n(2)n阶非连通的简单图的边数最多可为阶非连通的简单图的边数最多可为n-1阶连通图阶连通图加上一个孤立点，所以边数为加上一个孤立点，所以边数为(n-1)(n-2)/2，最少为，最少为0。20 一个图如果同构于它的补图，则该图称为自补图。一个图如果同构于它的补图，则该图称为自补图。1)一个图是自补图，其对应的完全图的边数必为偶数一个图是

16、自补图，其对应的完全图的边数必为偶数2)证明：若证明：若n阶无向简单图是自补图，则阶无向简单图是自补图，则n=4k或或n=4k+1（k为正整数）。为正整数）。解：解：n1)设图设图G是自补图，是自补图，G有有e条边，条边，G对应的完全图的对应的完全图的边数为边数为A。G的补图的补图G的边数应为的边数应为A一一e。因为。因为GG，故边数相等，故边数相等，e=A一一e，A2e，因此，因此G对应对应的完全图的边数的完全图的边数A为偶数。为偶数。n2)由由1)可知，自补图对应的完全图的边数为偶数。可知，自补图对应的完全图的边数为偶数。n个结点的完全图个结点的完全图Kn的边数为的边数为n(n-1)/2，

17、所以所以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个结点的简单图，要么它包含个结点的简单图，要么它包含一个三角形，要么它的补图包含一个三角形。一个三角形，要么它的补图包含一个三角形。解：解：n设设6个结点的简单图为个结点的简单图为G。考察。考察G中的任意一个结点中的任意一个结点a，那么，另外那么，另外6个结点中的任何一个结点，要么在个结点中的任何一个结点，要么在G中与中与a邻接，要么在邻接，要么在G的补图的补图G中与中

18、与a邻接。这样，邻接。这样，就可把就可把5个结点分成两类，将那些在个结点分成两类，将那些在G中与中与a邻接的邻接的结点归成一类，而将那些在结点归成一类，而将那些在G中与中与a邻接的结点归在邻接的结点归在另一类。于是必有一类至少含有三个结点，不妨假另一类。于是必有一类至少含有三个结点，不妨假设其中的三个结点为设其中的三个结点为b，c，d，如图所示。若边，如图所示。若边(b，c)，(c，d)，(b，d)中有一条在中有一条在G中，那么这条边所中，那么这条边所关联的两个结点都与关联的两个结点都与a邻接形成一个三角形；若边邻接形成一个三角形；若边(b，c)，(c，d)，(b,d)都不在都不在G中，则中，

19、则(b，c)，(c，d)，(b,d)形成一个三角形。形成一个三角形。22abcdbcdbcdbcd推论推论:任何任何6人的人群中，或者有人的人群中，或者有3人互相认识，或者有人互相认识，或者有3人彼此陌生。人彼此陌生。(当二人当二人x,y互相认识，边互相认识，边(x,y)着红色，着红色，否则着兰色。则否则着兰色。则6人认识情况对应于人认识情况对应于K6边有红边有红K3或者或者有兰有兰K3。)aaa23证明简单图的最大度小于结点数。证明简单图的最大度小于结点数。证明：证明：n设简单图设简单图G有有n个结点。对任一结点个结点。对任一结点u，由于，由于G没有没有环和平行边，环和平行边，u至多与其余至

20、多与其余n-1个结点中每一个有个结点中每一个有一条边相连接，即一条边相连接，即deg(u)n-1，因此，因此，(G)maxdeg(u)n-1。24设设G是一个是一个n阶无向简单图，阶无向简单图，n是大于等于是大于等于3的的奇数。证明图奇数。证明图G与它的补图中度数为奇数的结与它的补图中度数为奇数的结点个数相等。点个数相等。证明：证明：n因为因为G是是n阶无向简单图，且阶无向简单图，且n是大于等于是大于等于3的奇数，的奇数，故无向图的结点数为奇数，则所对应的故无向图的结点数为奇数，则所对应的n阶完全图阶完全图中每个结点的度数为中每个结点的度数为n-1即为偶数，即为偶数，n利用奇数利用奇数+奇数奇

21、数=偶数，偶数偶数，偶数+偶数偶数=偶数，所以，偶数，所以，在在G中结点度数为奇数的结点，在其补图中的度中结点度数为奇数的结点，在其补图中的度数也应为奇数，故数也应为奇数，故G和其补图的奇数结点个数也和其补图的奇数结点个数也是相同的。是相同的。25P2861、在无向图、在无向图G中，从结点中，从结点u到结点到结点v有一条长度为有一条长度为偶数的通路，从结点偶数的通路，从结点u到结点到结点v又有一条长度为奇又有一条长度为奇数的通路，则在数的通路，则在G中必有一条长度为奇数的回路。中必有一条长度为奇数的回路。证明证明：n设从结点设从结点u到结点到结点v长度为偶数的通路是长度为偶数的通路是ue1u1

22、e2u2e2kv，n长度为奇数的通路是长度为奇数的通路是ue11u11e12u12e12h-1v，n那么路那么路ue1u1e2u2e2kve12h-1u12e12u11e11u就是一条回就是一条回路，它的边数路，它的边数2k+(2h-1)2(h+k)-1，是奇数，故这，是奇数，故这条回路的长度是奇数。条回路的长度是奇数。26P2862、无向图、无向图G恰有的恰有的2个奇数度数的结点可个奇数度数的结点可达。达。解解1：令令u,w为为G恰有的恰有的2个奇度结点。考察个奇度结点。考察u所在的连通所在的连通分支分支G。因图。因图G的奇度点为偶数，故的奇度点为偶数，故G至少还有另至少还有另一奇度点一奇度

23、点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的连通的连通分支，由于分支，由于G中恰有两个奇度结点，因而当作为独中恰有两个奇度结点，因而当作为独立的图时，均有一个奇度结点，这与握手定理的推立的图时，均有一个奇度

24、结点，这与握手定理的推论相矛盾。论相矛盾。273、若图、若图G是不连通的，则是不连通的，则G的补图的补图G是连通的。是连通的。证明：证明：n若图若图G是不连通的，可设图是不连通的，可设图G的连通分支是的连通分支是G(V1)，G(V2)，G(Vm)(m2)。由于任意两个连通。由于任意两个连通分支分支G(Vi)与与G(Vj)(ij)之间不连通，因此两个结点子之间不连通，因此两个结点子集集Vi与与Vj之间的所有连线都在图之间的所有连线都在图G的补图的补图G中。任取中。任取两个结点两个结点u和和v，有两种情形：，有两种情形：na)u和和v分别属于两个不同结点子集分别属于两个不同结点子集Vi与与Vj。由

25、上可。由上可知知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必是连通图。必是连通图。28在具有在具有n个结点的个结点的无向简单图无向简单图G中中，若任意若任意2个个不同结点的度数之和大于等于不

26、同结点的度数之和大于等于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与题设矛盾，故图与题设矛盾，故图G是连通图。是连通图。29证明证明n个结点个结点k条边的简单图条边的简单图G，若，若k(n-1)(n-

27、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是连通图。是连通图。30n（渡渡河河问问题题）一一个个摆摆渡渡人人，要要把把一一只只狼狼、一一只只羊羊和和一一捆捆干干草草运运过过河河去去，河河上上有有一一只只木木船船，每每次次除除了了人人以以外外，只只能能带带一一样样东东西西。另另外外，如如果

28、果人人不不在在旁旁时时，狼狼就就要要吃吃羊羊，羊羊就就要要吃干草。吃干草。问这人怎样才能把它们运过河去？问这人怎样才能把它们运过河去？解解:用用F表示摆渡人，表示摆渡人，W表示狼，表示狼，S表示羊，表示羊，H表示干草。表示干草。n若若用用FWSH表表示示人人和和其其它它3样样东东西西在在河河的的左左岸岸的的状状态态。这这样样在左岸全部可能出现的状态为以下在左岸全部可能出现的状态为以下16种：种：nFWSH FWS FWH FSHnWSH FW FS FHnWS WH SH Fn W S H n这这里里表表示示左左岸岸是是空空集集，即即人人、狼狼、羊羊、干干草草都都已已运运到到右右岸去了。岸去了

29、。利用通路的概念解决一个古老的著名问题。利用通路的概念解决一个古老的著名问题。31n根据题意检查一下就可以知道，根据题意检查一下就可以知道，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表表示示人人和和干干草草在在左左岸岸，而而狼狼和和羊羊在在右右岸岸，这这当当然是不行的。然是不行的。因此，因此，允许出现的情况只有允许出现的情况只有10种。种。n我我们们构构造造一一个个图图，它它的的结结点点就就是是这这10

30、种种状状态态。若若一一种种状状态态可可以以转转移移到到另另一一种种状状态态，就就在在表表示示它它们们的的两两结结点点间间连连一一条条边边，这这样样就就画画出出图图。本本题题就就转转化化为为找找结结点点FWSH到到结结点点的的通通路路。从从图图中中得得到到两两条条这这样样的通路，的通路，即有两种渡河方案。即有两种渡河方案。FWSH WHFWHHWFSHFSWSFS32欧拉路，欧拉回路，欧拉图。欧拉路，欧拉回路，欧拉图。判定判定:n有欧拉路的充要条件：有欧拉路的充要条件：无或有两个奇数度的结无或有两个奇数度的结点。点。n有欧拉回路的充要条件：有欧拉回路的充要条件：所有结点度数均为偶所有结点度数均为

31、偶数。数。汉密尔顿路，汉密尔顿回路，汉密尔顿图汉密尔顿路，汉密尔顿回路，汉密尔顿图汉密尔顿图的判定汉密尔顿图的判定:n必要条件：必要条件：设无向图设无向图G=是是汉密尔顿汉密尔顿图，则图，则对于任意对于任意非空子集非空子集S，有，有W(G-S)|S|。n推论推论设无向图设无向图G=是半是半汉密尔顿汉密尔顿图，则对图，则对于任意于任意非空子集非空子集S，有，有W(G-S)|S|+1。n充分条件：若简单图充分条件：若简单图G中每对结点的度数和中每对结点的度数和|V|=n，则，则G是汉密尔顿图。是汉密尔顿图。n半汉密尔顿图，若简单图半汉密尔顿图，若简单图G中每对结点的度数和中每对结点的度数和|V|-

32、1，则，则G是半汉密尔顿图。是半汉密尔顿图。四、欧拉图与汉密尔顿图四、欧拉图与汉密尔顿图(会判定会判定)33P3112试构造一个欧拉图，其结点数试构造一个欧拉图，其结点数v和边数和边数e满足下满足下述条件述条件(1)v和和e的奇偶性相同；的奇偶性相同；(2)v和和e的奇偶性相反。的奇偶性相反。n解：解：(1)(2)说明：欧拉图中，结点数和边数的奇偶性说明：欧拉图中，结点数和边数的奇偶性既可以相同也可以相反。既可以相同也可以相反。34 nn个结点的有向完全图，哪些是有向欧拉图，为什么？个结点的有向完全图，哪些是有向欧拉图，为什么？解：解：nn个结点的有向完全图是有向欧拉图，对于个结点的有向完全图

33、是有向欧拉图，对于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为奇数，

34、为奇数，对应的有对应的有n/2对奇数度结点，因此可以对奇数度结点，因此可以n/2笔画出。笔画出。35n删除删除A和和B后，形成后，形成3个连通分支，个连通分支，n即即W(G-S)=3|S|=2因此，图因此，图G不是汉密尔顿图。不是汉密尔顿图。图图G是否是汉密尔顿图。是否是汉密尔顿图。AB367位客人入席，位客人入席，A只会讲英语，只会讲英语，B会讲英，汉语，会讲英，汉语，C会讲英，意大利，俄语，会讲英，意大利，俄语，D会讲日，汉语，会讲日，汉语，E会讲德，意大利语，会讲德，意大利语，F会讲法，日，俄语，会讲法，日，俄语，G会讲法，德语。能否安排圆桌席位使每位客人与会讲法，德语。能否安排圆桌席位

35、使每位客人与其左右邻不用翻译便可交谈其左右邻不用翻译便可交谈?解：解：建立无向图模型建立无向图模型:结点为客人；结点为客人；会共同语言的会共同语言的2结点相邻接。结点相邻接。则问题则问题归结为归结为求此图的一条求此图的一条汉密尔顿回路汉密尔顿回路。不难验证，此图有一条汉密尔顿不难验证，此图有一条汉密尔顿回路是回路是:(A,B,D,F,G,E,C,A)。按此回路安排席位可按此回路安排席位可以以使得每个人都可以和它两边的人直接交谈使得每个人都可以和它两边的人直接交谈。汉密尔顿图汉密尔顿图的应用的应用BCDEFGA英英英英法法德德俄俄意意日日汉汉37某地有某地有5个风景点，若每个风景点均有个风景点，

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

37、以经，因此游人可以经过每个风景点恰好一次而游完这过每个风景点恰好一次而游完这5处。处。38设图设图G有有n个结点，个结点，e条边，证明：若条边，证明：若，则则G为汉密尔顿图。为汉密尔顿图。证明：证明：反证法反证法n假设假设G不是汉密尔顿图，则根据汉密尔顿图的判定不是汉密尔顿图，则根据汉密尔顿图的判定定理，知至少存在两个结点的度数之和小于定理，知至少存在两个结点的度数之和小于n，则该，则该两个结点所关联的边的数目两个结点所关联的边的数目m1小于小于n，即，即m1n-1，而当其余而当其余n-2个结点构成完全图时，其所关联的边个结点构成完全图时，其所关联的边数目数目m2为最大值，即为最大值，即m2(

38、n-2)(n-3)/2。nG的总的边数为的总的边数为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由

39、已知条件可知，对于任意的由已知条件可知，对于任意的viV,deg(vi)n/2，因此因此deg(vi)+deg(vj)n，由定理可知，由定理可知G是汉密尔顿是汉密尔顿图，图，n因而因而G中存在汉密尔顿回路，不妨设中存在汉密尔顿回路，不妨设C=vi1vi2vi3vi4vi5vi6vi1为其中一条，在这种回路上相为其中一条，在这种回路上相邻两个结点代表的二人能相互合作。邻两个结点代表的二人能相互合作。40某工厂生产由某工厂生产由6种不同颜色的纱织成的双色布，已知在种不同颜色的纱织成的双色布，已知在品种中，每种颜色至少分别和其他品种中，每种颜色至少分别和其他5种颜色中的种颜色中的3种颜种颜色搭配，证

40、明可以挑出色搭配，证明可以挑出3种双色布，它们恰有种双色布，它们恰有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为其中一条，在这种回路上每个结为其中一条，在这种回路上每个结点代表的颜色都能与它相邻结点代表的颜色相搭点代表的颜色都能与它相邻结点代表的颜色相搭配，于是让配，于

41、是让v1与与v2,v3与与v4,v5与与v6搭配，织成搭配，织成3种种双色布，包含了双色布，包含了6种颜色。种颜色。41 n下列命题中下列命题中()是正确的是正确的.n1.欧拉图的子图一定是欧拉图欧拉图的子图一定是欧拉图n2.汉密尔顿图的子图一定是汉密尔顿图汉密尔顿图的子图一定是汉密尔顿图42反证法在图论中的应用反证法在图论中的应用n图论这门学科理论性强，与其它数学分支学科不图论这门学科理论性强，与其它数学分支学科不同的是，在它的理论证明之中反证法使用的特别同的是，在它的理论证明之中反证法使用的特别多。反证法最大的优点是无形中多了一个或几个多。反证法最大的优点是无形中多了一个或几个条件，因此在

42、图论中证明有些命题时，若感到条条件，因此在图论中证明有些命题时，若感到条件件“不足不足”或无从下手，不妨考虑使用反证法。或无从下手，不妨考虑使用反证法。用反证法证明图论命题有时能起到其它方法所办用反证法证明图论命题有时能起到其它方法所办不到的功效，下面从几个不同类型出发，结合适不到的功效，下面从几个不同类型出发，结合适当的实例介绍反证法在图论中的应用。当的实例介绍反证法在图论中的应用。43有关有关“存在性存在性”问题问题n在简单图在简单图G 中，若中，若v(G)2，则在，则在G 中必存在度数中必存在度数相等的两个结点。相等的两个结点。证：证：设图设图G 中各点的度均不相等，那么必有最大度中各点

43、的度均不相等，那么必有最大度nv 1。若。若=v 1，必有，必有1，从而，从而，-+1v 1，又与，又与G是简单图矛盾。是简单图矛盾。44有关涉及“至少”的问题n若若G 是是k 的树，试证的树，试证G 至少有至少有k 个结点度为个结点度为1。n证：若证：若G 中度为中度为1的结点个数的结点个数s 小于小于k，由度和定理，由度和定理得，但对树得，但对树G 却有，两者矛盾。却有，两者矛盾。45有些以否定判断为结论的命题有些以否定判断为结论的命题若若G 中每个结点的度均为偶数，试证中每个结点的度均为偶数，试证G 中的任何一中的任何一条边都不是割边。条边都不是割边。证：证：n假设假设G 中存在割边中存

44、在割边e，取，取G e 中含中含e 的一个端点的一个端点u 的连通分支为的连通分支为G 1，则，则G 1中除中除u 的度为奇数外，的度为奇数外，其余结点的度均为偶数，这与定理其余结点的度均为偶数，这与定理“在任何图中在任何图中度为奇数的结点有偶数个度为奇数的结点有偶数个”相矛盾，故相矛盾，故G 中的任中的任何一条边都不是割边。何一条边都不是割边。46有些已知条件较少，或仅从已知条件出发能够得出的信息知之甚少的问题若一个连通图若一个连通图G 的每条边都是割边，则的每条边都是割边，则G 是树。是树。n证：假设证：假设G 是连通图但不是树，则包含一个圈是连通图但不是树，则包含一个圈C。由于割边不应该

45、包含在任何一个圈中，故导致矛由于割边不应该包含在任何一个圈中，故导致矛盾。盾。477.采用直接证明的方法不够多，或者用采用直接证明的方法不够多，或者用直接证法较困难的命题直接证法较困难的命题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