离散数学 第七章 图论 习题课

《离散数学 第七章 图论 习题课》由会员分享，可在线阅读，更多相关《离散数学 第七章 图论 习题课（48页珍藏版）》请在金锄头文库上搜索。

1、第7章 图 论 习题课,离 散 数 学,河南工业大学,信息科学与工程学院,复 习 时 注 意 准确掌握每个概念 灵活应用所学定理 注意解题思路清晰 证明问题时，先用反向思维(从结论入手)分析问题，再按正向思维写出证明过程。,图,通路与回路,图的连通性,欧拉图,汉密尔顿图,无向树及其性质,平面图的基本性质,欧拉公式,平面图的对偶图,地图着色与平面图着色,平面图的判断,图的矩阵表示,无向树及其性质,根树及其应用,无向树及其性质,图论的结构图,一、无向图与有向图,1、基本概念。 有向图与无向图的定义；有向边,无向边,平行边,环, 孤立结点 关联与邻接(相邻)； 结点的度数；结点的度, 结点的出度,

2、结点的入度, 图的最大度(G),最小度(G), 零图与平凡图；简单图与多重图； 完全图；子图，生成子图，补图；图的同构。 2、运用。 (1) 灵活运用握手定理及其推论， (2) 判断两个图是否同构， (3) 画出满足某些条件的子图，补图等。,二、通路、回路、图的连通性,1、基本概念 路，回路，迹， 通路，圈 无向图和有向图中结点之间的可达关系；连通图，连通分支，连通分支数W(G) 点割集，割点，点连通度k(G) 边割集，割边(桥)，边连通度(G) 短程线，距离 有向图连通的分类，强连通，单侧连通，弱连通， 强分图，单侧分图，弱分图 2、运用 (1) 判断有向图或无向图中通路(回路)的类型。 (

3、2) 求短程线和距离。 (3) 判断有向图连通的类型。,三、图的矩阵表示,1、基本概念。 无向图的邻接矩阵A 根据邻接矩阵判断:各结点的度, 有向图结点出,入度。 由Ak可以求一个结点到另一个结点长度为k的路条数. 有向图的可达矩阵P 用P可以判定:各结点的度. 有向图的强分图。 关联矩阵M:是结点与边的关联关系矩阵. 用M判定:各结点的度,重要定理：握手定理及其推论,推论 ： 任何图(无向的或有向的)中，奇度结点的个数是偶数。,无向图：,有向图：,且,(1),(2),(3),多重图,不是,典型题,设图G=，其中V=a,b,c,d,e，E分别由下面给 出。判断哪些是简单图，哪些是多重图？,简单

4、图,下列各序列中，可以构成无向简单图的度数序列的 有哪些？ (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) 不可以,图G如右图所示，以下说法正确的是 ( ) A(a, d)是割边 B(a, d)是边割集 C(d, e)是边割集 D(a, d) ,(a, c)是边割集,正确答案是：C。 对割边、边割集的概念理解到位。 定义 设无向图G=为连通图，若有边集E1E，使图G删除了E1的所有边后，所得的子图是不连通图，而删除了E1的任何真子集后，所得的子图是连通图，则称E1

5、是G的一个边割集若某个边构成一个边割集，则称该边为割边（或桥） 如果答案A正确，即删除边(a, d)后，得到的图是不连通图，但事实上它还是连通的。因此答案A是错误的。,设给定图G(如由图所示)，则图G的点割集是 应该填写：f，c，e。,定义 设无向图G=为连通图，若有点集V1V，使图G删除了V1的所有结点后，所得的子图是不连通图，而删除了V1的任何真子集后，所得的子图是连通图，则称V1是G的一个点割集若某个结点构成一个点割集，则称该结点为割点。 f，c是不满定义的，因为f是f，c的真子集，而删除f后，图是不连通的。,单向连通,强连通,强连通,下图所示的六个图中，强连通，单向连通，弱连通 的分别

6、有哪些？,强连通,单向连通,弱连通,设图G的邻接矩阵为 则G的边数为( ) A5 B6 C3 D4,正确答案是：D。 当给定的简单图是无向图时，邻接矩阵为对称的即当结点vi与vj相邻时，结点vj与vi也相邻，所以连接结点vi与vj的一条边在邻接矩阵的第i行第j列处和第j行第i列处各有一个1，题中给出的邻接矩阵中共有8个1，故有82=4条边。度数之和等于2倍的边数。,(1) D是哪类连通图? (2) D中v1到v4长度为1,2,3,4的通路各多少条？ (3) D中长度为4的通路（不含回路）有多少条？ (4)D中长度为4的回路有多少条？ (5) D中长度4的通路有多少条？其中有几条是回路？ (6)

7、 写出D的可达矩阵。,有向图D如图所示，回答下列问题：,有向图D如图所示，回答下列诸问：,(1) D是哪类连通图? D是强连通图。 解答为解(2)(6)，只需先求D的邻接矩阵的前4次幂。,(2) D中v1到v1长度为1,2,3,4的回路各多少条？ 答： v1到v1长度为1,2,3,4的回路数分别为1,1,3,5。 (3) D中长度为4的通路（不含回路）有多少条？ 答：长度为4的通路(不含回路)为33条. (4) D中长度为4的回路有多少条？ 答： 长度为4的回路为11条。 (5) D中长度4的通路有多少条？其中有几条是回路？ 答：长度4的通路88条，其中22条为回路。 (6) 写出D的可达矩阵

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

9、结点的度数均小于或等于2，由握手定理可得 2(3+4)+(n-4)2=14+2n-8 deg(vi) = 2m=20 解此不等式可得n7，即G中至少有7个结点，7个结点时，其度数列为2,2,2,3,3,4,4，=4,=2。,(1)设n阶图G中有m条边，证明：(G)2m/n(G) (2)n阶非连通的简单图的边数最多可为多少？最少呢？ (1)证明中关键步骤是握手定理： 2m=deg(vi) (G)deg(vi)(G)，于是得 n(G)2mn(G) (G)2m/n(G) 易知2m/n为G的平均度数，因而它大于或等于最小度(G)，小于或等于最大度(G)。 (2) n阶非连通的简单图的边数最多可为n-1

10、阶连通图加上一个孤立点，所以边数为(n-1)(n-2)/2，最少为0。,一个图如果同构于它的补图，则该图称为自补图。 1)一个图是自补图，其对应的完全图的边数必为偶数 2)证明：若n阶无向简单图是自补图，则n=4k或n=4k+1（k为正整数）。 解： 1)设图G 是自补图，G 有 e 条边，G 对应的完全图的边数为 A。G 的补图 G的边数应为 A 一 e。因为 GG， 故边数相等，e=A 一 e，A2e，因此 G 对应的完全图的边数 A 为偶数。 2)由 1)可知，自补图对应的完全图的边数为偶数。n 个结点的完全图 Kn 的边数为n(n-1)/2 ， 所以 n(n-1)/2=2m ，即n(n

11、-1)=4m，因而 n为4的倍数，即n=4k， 或n-1为4的倍数，即n=4k+1， 即n=0,1 (mod 4)。,对于任何一个具有6个结点的简单图，要么它包含一个三角形，要么它的补图包含一个三角形。,解： 设6个结点的简单图为G。考察G中的任意一个结点a， 那么，另外6个结点中的任何一个结点，要么在G中与a邻接，要么在G的补图G中与a邻接。这样，就可把5个结点分成两类，将那些在G中与a邻接的结点归成一类，而将那些在G中与a邻接的结点归在另一类。于是必有一类至少含有三个结点，不妨假设其中的三个结点为b，c，d，如图所示。若边(b，c)，(c，d)，(b，d)中有一条在G中，那么这条边所关联的

12、两个结点都与a邻接形成一个三角形；若边(b，c)，(c，d)，(b, d)都不在G中，则(b，c)，(c，d)，(b, d)形成一个三角形。,a,b,c,d,b,c,d,b,c,d,b,c,d,推论:任何6人的人群中，或者有3人互相认识，或者有3人彼此陌生。(当二人x,y互相认识，边(x,y)着红色，否则着兰色。则6人认识情况对应于K6边有红K3或者有兰K3。),a,a,a,证明简单图的最大度小于结点数。,证明： 设简单图G有n个结点。对任一结点u，由于G没有环和平行边，u至多与其余n-1个结点中每一个有一条边相连接，即deg(u)n-1，因此， (G) maxdeg(u)n-1。,设G是一个

13、n阶无向简单图，n是大于等于3的奇数。证明图G与它的补图中度数为奇数的结点个数相等。,证明： 因为G是n阶无向简单图，且n是大于等于3的奇数，故无向图的结点数为奇数，则所对应的n阶完全图中每个结点的度数为n-1即为偶数， 利用奇数+奇数=偶数，偶数+偶数=偶数，所以，在G中结点度数为奇数的结点，在其补图中的度数也应为奇数，故G和其补图的奇数结点个数也是相同的。,P286 1、在无向图G中，从结点u到结点v有一条长度为偶数的通路，从结点u到结点v又有一条长度为奇数的通路，则在G中必有一条长度为奇数的回路。,证明 ： 设从结点u到结点v长度为偶数的通路是ue1u1e2u2e2kv， 长度为奇数的通

14、路是ue11u11e12u12e12h-1v， 那么路ue1u1e2u2e2kve12h-1u12e12u11e11u就是一条回路，它的边数2k+(2h-1)2(h+k)-1，是奇数，故这条回路的长度是奇数。,P286 2、无向图 G恰有的2个奇数度数的结点可达。,解1：令u,w为G恰有的2个奇度结点。考察u所在的连通分支G。因图G的奇度点为偶数，故G至少还有另一奇度点w，但v在G和G中有相同的度，所以G恰有2个奇度点而且就是u和w。再由G的连通性推出u到w可达。 解2：反证法 设G中的两个奇度结点为u与v，若u与v不连通，即它们之间无路，因而u与v处于G中恰有不同连通分支中，设u在 G1中，

15、v在G2中， G1与 G2是G的连通分支，由于G中恰有两个奇度结点，因而当作为独立的图时，均有一个奇度结点，这与握手定理的推论相矛盾。,3、若图G是不连通的，则G的补图G是连通的。,证明： 若图G是不连通的，可设图G的连通分支是G(V1)，G(V2)，G(Vm)(m2)。由于任意两个连通分支G(Vi)与G(Vj)(ij)之间不连通，因此两个结点子集Vi与Vj之间的所有连线都在图G的补图G中。任取两个结点u和v，有两种情形： a)u和v分别属于两个不同结点子集Vi与Vj。由上可知G 包含边(u，v)，故u和v在G中是连通的。 b)u和v属于同个结点子集Vi。可在另一个结点子集Vj中取一个结点w，由上可知边(u,w)及边(v,w)均在G 中，故邻接边(u,w)和(w,v)组成的路连接结点u和v，即u和v在G中也是连通的。 由此可知，当图G不是连通图时，G必是连通图。,在具有n个结点的无向简单图G中，若任意2 个不同结点的度数之和大于等于n - 1 ，则图G是连通图。,证明：反证法 设图G不是连通图，不妨设图G有2 个连通分支G1 和G2，其中G1有k ( k 1) 个结点，G2有n - k个结点。在G1中任取一点vi，G2中任取一点vj