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

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

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

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

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

4、V=a,b,c,d,e，E分别由下面给 出。判断哪些是简单图，哪些是多重图？ 简单图 下列各序列中，可以构成无向简单图的度数序列的 有哪些？ (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)是边割集 n正确答案是：C。 n对割边、边割集的概念理解到位。 n定义 设无向图G=为连通图，若有边集E1E ，使图G删除了E1

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

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

7、D中长度为4的通路（不含回路）有 多少条？ n(4)D中长度为4的回路有多少条？ n(5) D中长度4的通路有多少条？其中 有几条是回路？ n(6) 写出D的可达矩阵。 有向图D如图所示，回答下列问题： 有向图D如图所示，回答下列诸问： n(1) D是哪类连通图? nD是强连通图。 n解答为解(2)(6)，只需先求D的邻 接矩阵的前4次幂。 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的回路

8、有多少条？ n答： 长度为4的回路为11条。 n(5) D中长度4的通路有多少条？其中有几条是回路 ？ n答：长度4的通路88条，其中22条为回路。 n(6) 写出D的可达矩阵。 n44的全1矩阵。 简单无向图 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个结点中至少有两个同度数点。 握手定理及其推论的应用 n设无向图G有1

9、0条边，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-8 deg(vi) = 2m=20 n解此不等式可得n7，即G中至少有7个结点，7 个结点时，其度数列为2,2,2,3,3,4,4，=4,=2。 (1)设n阶图G中有m条边，证明：(G)2m/n(G) (2)n阶非连通的简单图的边数最多可为多少？最少呢？ n(1)证明中关键步骤是握手定理： 2m=deg(vi)

10、(G)deg(vi)(G)，于是得 n n(G)2mn(G) (G)2m/n(G) n易知2m/n为G的平均度数，因而它大于或等于 最小度(G)，小于或等于最大度(G)。 n(2) n阶非连通的简单图的边数最多可为n-1阶连通图 加上一个孤立点，所以边数为(n-1)(n-2)/2，最少为0 。 一个图如果同构于它的补图，则该图称为自补图。 1)一个图是自补图，其对应的完全图的边数必为偶数 2)证明：若n阶无向简单图是自补图，则n=4k或n=4k+1 （k为正整数）。 解： n1)设图G 是自补图，G 有 e 条边，G 对应的完全图的 边数为 A。G 的补图 G的边数应为 A 一 e。因为 G

11、G， 故边数相等，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 (mod 4)。 对于任何一个具有6个结点的简单图，要么它包含 一个三角形，要么它的补图包含一个三角形。 解： n设6个结点的简单图为G。考察G中的任意一个结点a ， 那么，另外6个结点中的任何一个结点，要么在G 中与a邻接，要么在G的补图G中与a邻接。这样

12、， 就可把5个结点分成两类，将那些在G中与a邻接的 结点归成一类，而将那些在G中与a邻接的结点归在 另一类。于是必有一类至少含有三个结点，不妨假 设其中的三个结点为b，c，d，如图所示。若边(b， c)，(c，d)，(b，d)中有一条在G中，那么这条边所 关联的两个结点都与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人认识情况对

13、应于K6边有红K3或者 有兰K3。) a aa 证明简单图的最大度小于结点数。 证明： n设简单图G有n个结点。对任一结点u，由于G没 有环和平行边，u至多与其余n-1个结点中每一个 有一条边相连接，即deg(u)n-1，因此， (G) maxdeg(u)n-1。 设G是一个n阶无向简单图，n是大于等于3的 奇数。证明图G与它的补图中度数为奇数的结 点个数相等。 证明： n因为G是n阶无向简单图，且n是大于等于3的奇数 ，故无向图的结点数为奇数，则所对应的n阶完全 图中每个结点的度数为n-1即为偶数， n利用奇数+奇数=偶数，偶数+偶数=偶数，所以， 在G中结点度数为奇数的结点，在其补图中的度

14、 数也应为奇数，故G和其补图的奇数结点个数也 是相同的。 P286 1、在无向图G中，从结点u到结点v有一条长度为 偶数的通路，从结点u到结点v又有一条长度为奇 数的通路，则在G中必有一条长度为奇数的回路 。 证明 ： n设从结点u到结点v长度为偶数的通路是 ue1u1e2u2e2kv， n长度为奇数的通路是ue11u11e12u12e12h-1v， n那么路ue1u1e2u2e2kve12h-1u12e12u11e11u就是一条回 路，它的边数2k+(2h-1)2(h+k)-1，是奇数，故这 条回路的长度是奇数。 P286 2、无向图 G恰有的2个奇数度数的结点可 达。 解1：令u,w为G恰

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