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

(5) D中长度4的通路有多少条？其中有几条是回路？ 答：长度4的通路88条，其中22条为回路。
(6) 写出D的可达矩阵。 44的全1矩阵。
简单无向图 G 必有2结点同度数。
证: 令 G={v1,…,vn}，
若 G 中没有孤立点,则 G 中 n个结点的度只取 n-1 个 可能值：1,2,…,n-1，从而 G 中至少有两个结点的度 数相同。
重要定理：握手定理及其推论
无向图：
有向图：
且
推论 ： 任何图(无向的或有向的)中，奇度结点的 个数是偶数。
典型题
设图G=<V,E>，其中V={a,b,c,d,e}，E分别由下面给 出。判断哪些是简单图，哪些是多重图？
(1) E (a,b),(b,c),(c, d),(a,e)
简单图
(2) E (a,b),(b,e),(e,b),(a,e),(d,e) 多重图
设给定图G(如由图所示)，则图G的点割集
是
．
应该填写：{f}，{c，e}。
定义 设无向图G=<V, E>为连通图，若有点集
V1V，使图G删除了V1的所有结点后，所得的子
图是不连通图，而删除了V1的任何真子集后，所
得的子图是连通图，则称V1是G的一个点割
集．若某个结点构成一个点割集，则称该结点为
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中，v在G2中， G1与 G2是G的连 通分支，由于G中恰有两个奇度结点，因而当作为 独立的图时，均有一个奇度结点，这与握手定理 的推论相矛盾。
零图与平凡图；简单图与多重图； 完全图；子图，生成子图，补图；图的同构。 2、运用。 (1) 灵活运用握手定理及其推论， (2) 判断两个图是否同构， (3) 画出满足某些条件的子图，补图等。
二、通路、回路、图的连通性
1、基本概念 路，回路，迹， 通路，圈
无向图和有向图中结点之间的可达关系；连通 图，连通分支，连通分支数W(G)
少条？
(3) D中长度为4的通路（不含回路）有 多少条？
(4)D中长度为4的回路有多少条？ (5) D中长度≤4的通路有多少条？其中
有几条是回路？
(6) 写出D的可达矩阵。
有向图D如图所示，回答下列诸问：
(1) D是哪类连通图? D是强连通图。
解答为解(2)—(6)，只需先求D的邻 接矩阵的前4次幂。
3、若图G是不连通的，则G的补图G是连通的。
证明：
若图G＝<V，E>是不连通的，可设图G的连通分支是 G(V1)，G(V2)，…，G(Vm)(m≥2)。由于任意两个连通 分支G(Vi)与G(Vj)(i≠j)之间不连通，因此两个结点子 集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'中也是连通的。
割点。
{f，c}是不满定义的，因为{f}是{f，c}的真子集， 而删除{f}后，图是不连通的。
下图所示的六个图中，强连通，单向连通，弱连通 的分别有哪些？
强连通
单向连通
弱连通
单向连通
强连通
强连通
设图G的邻接矩阵为 则G的边数为( )． A．5 B．6 C．3 正确答案是：D。
D．4
当给定的简单图是无向图时，
设G的阶数为n，4个结点的度数分别为3，3，4，4, 其余n-4个结点的度数均小于或等于2，由握手定理 可得
2×(3+4)+(n-4)×2=14+2n-8
≥ ∑deg(vi) = 2m=20 解此不等式可得n≥7，即G中至少有7个结点，7
个结点时，其度数列为2,2,2,3,3,4,4，△=4,δ=2。
a c
a c
b
d
b
d
a c
a c
b
d，或者有3人互相认识，或者有 3人彼此陌生。(当二人x,y互相认识，边(x,y)着红色， 否则着兰色。则6人认识情况对应于K6边有红K3或者 有兰K3。)
证明简单图的最大度小于结点数。
证明： 设简单图G有n个结点。对任一结点u，由于G没
有环和平行边，u至多与其余n-1个结点中每一个 有一条边相连接，即deg(u)≤n-1，因此，⊿ (G) ＝maxdeg(u)≤n-1。
设G是一个n阶无向简单图，n是大于等于3的 奇数。证明图G与它的补图中度数为奇数的结 点个数相等。
证明：
因为G是n阶无向简单图，且n是大于等于3的奇数， 故无向图的结点数为奇数，则所对应的n阶完全图 中每个结点的度数为n-1即为偶数，
正确答案是：C。 对割边、边割集的概念理解到位。
定义 设无向图G=<V, E>为连通图，若有边集E1E， 使图G删除了E1的所有边后，所得的子图是不连通 图，而删除了E1的任何真子集后，所得的子图是连 通图，则称E1是G的一个边割集．若某个边构成一 个边割集，则称该边为割边（或桥）
如果答案A正确，即删除边(a, d)后，得到的图是不 连通图，但事实上它还是连通的。因此答案A是错 误的。
证明 ：
设从结点u到结点v长度为偶数的通路是 ue1u1e2u2…e2kv，
长度为奇数的通路是ue11u11e12u12…e12h-1v， 那么路ue1u1e2u2…e2kve12h-1…u12e12u11e11u就是一条回
路，它的边数＝2k+(2h-1)＝2(h+k)-1，是奇数，故 这条回路的长度是奇数。
否则，G中有孤立点，不妨设 vk,…,vn为全部孤立点, 则 v1,…,vk-1的度只取 k-2个可能值: 1,2,…,k-2，从而 此 k-1个结点中至少有两个同度数点。
握手定理及其推论的应用
设无向图G有10条边，3度与4度结点各2个，其余 结点的度数均小于3，问G中至少有几个结点？在 最少结点的情况下，写出G的度数列△(G)、δ(G)。
点割集，割点，点连通度k(G) 边割集，割边(桥)，边连通度λ(G) 短程线，距离
有向图连通的分类，强连通，单侧连通，弱连 通， 强分图，单侧分图，弱分图
2、运用 (1) 判断有向图或无向图中通路(回路)的类型。 (2) 求短程线和距离。 (3) 判断有向图连通的类型。
三、图的矩阵表示
平面图的判断 欧拉公式
平面图的对偶图
无向树及其性质 根树及其应用
地图着色与平 面图着色
一、无向图与有向图
1、基本概念。
有向图与无向图的定义；有向边,无向边,平行边, 环, 孤立结点
关联与邻接(相邻)； 结点的度数；结点的度, 结点的出度, 结点的入
度, 图的最大度Δ(G),最小度δ(G),
（k为正整数）。 解：
1)设图G 是自补图，G 有 e 条边，G 对应的完全图的 边数为 A。G 的补图 G’的边数应为 A 一 e。因为 G～G’， 故边数相等，e=A 一 e，A＝2e，因此 G 对 应的完全图的边数 A 为偶数。
2)由 1)可知，自补图对应的完全图的边数为偶数。n 个结点的完全图 Kn 的边数为n(n-1)/2 ， 所以 n(n-1)/2=2m ，即n(n-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’中，那么这条边所 关联的两个结点都与a邻接形成一个三角形；若边(b， c)，(c，d)，(b, d)都不在G’中，则(b，c)，(c，d)， (b, d)形成一个三角形。
邻接矩阵为对称的．即当结 点vi与vj相邻时，结点vj与vi也 相邻，所以连接结点vi与vj的 一条边在邻接矩阵的第i行第j 列处和第j行第i列处各有一个 1，题中给出的邻接矩阵中共 有8个1，故有82=4条边。度 数之和等于2倍的边数。
有向图D如图所示，回答下列问题：
(1) D是哪类连通图? (2) D中v1到v4长度为1,2,3,4的通路各多
离散数学
河南工业大学 信息科学与工程学院
第7章 图 论 习题课
复习时注意
准确掌握每个概念 灵活应用所学定理 注意解题思路清晰 证明问题时，先用反向思维(从结论入手)分析问
题，再按正向思维写出证明过程。
图 图论的结构图
通路与回路 图的连通性
图的矩阵表示 欧拉图 汉密尔顿图
平面图的基本性质
1 2 0 0 A 0 0 1 0
1 0 0 1 0 0 1 0
3 2 2 2 A3 1 2 1 0