离散数学图论习题课共48页文档
- 格式：ppt
- 大小：4.57 MB
- 文档页数：48
下载文档原格式
合集下载
(优选)离散数学图论版
(3)G1与G2的差,定义为图G3＝〈V3,E3〉,记为G3=G1-G2。 其中E3=E1-E2,V3=(V1-V2)∪{E3中边所关联的顶点}。 (4)G1与G2的环和,定义为图G3＝〈V3,E3〉,
G3=(G1∪G2)-(G1∩G2),记为G3=G1 G2。
除以上4种运算外,还有以下两种操作:
E={e1,e2}={(v1,v2),(ห้องสมุดไป่ตู้2,v3)};
f(v1)=5,f(v2)=8,f(v3)=11;
g(e1)=4.6,g(e2)=7.5
8.1.2 结点的次数
定义8.1―4在有向图中,对于任何结点v,以v为始点的 边的条数称为结点v的引出次数(或出度),记为deg+(v); 以v为终点的边的条数称为结点v的引入次数(或入度), 记为deg-(v);结点v的引出次数和引入次数之和称为 结点v的次数(或度数),记作deg(v)。在无向图中,结点 v的次数是与结点v相关联的边的条数,也记为deg(v)。
i 1
i 1
定理8.1―2在图中,次数为奇数的结点必为偶数个。
证 设次数为偶数的结点有n1个,记为(i=1,2,…,n1)。 次数为奇数的结点有n2个,记为(i=1,2,…,n2)。
由上一定理得
n
n1
n2
2m deg(i ) deg(Ei ) deg(Oi )
i 1
i 1
i 1
因为次数为偶数的各结点次数之和为偶数。所以
孤立结点的次数为零。
定理8.1―1 设G是一个(n,m)图,它的结点集合为
V={v1,v2,…,vn},则 n
deg(i ) 2m
i 1
证 因为每一条边提供两个次数,而所有各结点次数
之和为m条边所提供,所以上式成立。
G3=(G1∪G2)-(G1∩G2),记为G3=G1 G2。
除以上4种运算外,还有以下两种操作:
E={e1,e2}={(v1,v2),(ห้องสมุดไป่ตู้2,v3)};
f(v1)=5,f(v2)=8,f(v3)=11;
g(e1)=4.6,g(e2)=7.5
8.1.2 结点的次数
定义8.1―4在有向图中,对于任何结点v,以v为始点的 边的条数称为结点v的引出次数(或出度),记为deg+(v); 以v为终点的边的条数称为结点v的引入次数(或入度), 记为deg-(v);结点v的引出次数和引入次数之和称为 结点v的次数(或度数),记作deg(v)。在无向图中,结点 v的次数是与结点v相关联的边的条数,也记为deg(v)。
i 1
i 1
定理8.1―2在图中,次数为奇数的结点必为偶数个。
证 设次数为偶数的结点有n1个,记为(i=1,2,…,n1)。 次数为奇数的结点有n2个,记为(i=1,2,…,n2)。
由上一定理得
n
n1
n2
2m deg(i ) deg(Ei ) deg(Oi )
i 1
i 1
i 1
因为次数为偶数的各结点次数之和为偶数。所以
孤立结点的次数为零。
定理8.1―1 设G是一个(n,m)图,它的结点集合为
V={v1,v2,…,vn},则 n
deg(i ) 2m
i 1
证 因为每一条边提供两个次数,而所有各结点次数
之和为m条边所提供,所以上式成立。
离散数学习题课图论
2021/6/28
6 of 220
练习2(续)
D的邻接矩阵的前4次幂.
1 2 0 0
A 0
0
1
0
1 0 0 1
0
0
1
0
1 2 2 0
A 2 1
0
0
1
1 2 1 0
1
0
0
1
3 2 2 2
A3
1
2
1
0
2 2 2 1
1
2
1
0
Hale Waihona Puke 5 6 4 2A4
2
2
2
1
4 4 3 2
2
2
2
1
2021/6/28
8 of 220
练习2(续)
(5) v1到v1长度为1,2,3,4的回路数分别为 1,1,3,5. 其中长度为1的是初级的(环)；长度 为2的是复杂的；长度为3的中有1条是复杂 的，2条是初级的；长度为4的有1条是复杂 的，有4条是非初级的简单回路. (6) 长度为4的通路(不含回路)为33条. (7) 长度为4的回路为11条. (8) 长度4的通路88条，其中22条为回路. (9) 44的全1矩阵.
9阶无向图G中，每个顶点的度数不是5就 是6. 证明G中至少有5个6度顶点或至少有 6个5度顶点.
方法一：穷举法
设G中有x个5度顶点，则必有(9x)个6度顶点， 由握手定理推论可知，(x,9x)只有5种可能： (0,9), (2,7), (4,5), (6,3), (8,1）它们都满足要求.
方法二：反证法
〔1 n 6〕 熟练掌握求最优树的方法
2021/6/28
12 of 220
习题1
离散数学图论
握手定理应用
无向图G有16条边，3个4度顶点，4个3度顶点，其余顶 点度数均小于3，问G的阶数n为几？ 解 设除3度与4度顶点外，还有x个顶点v1, v2, …, vx， 则 d(vi) 2，i =1, 2, …, x， 应用握手定理,得不等式 32=2m= Σd(vi)3*4+4*3+2x 得 x 4, 阶数 n 4+3+4=11.
14
1
实例
有向图D如图所示，求D的邻接矩阵 A与 A2, A3, A4. 问D 中长度 为1, 2, 3, 4的通路各有多少条？其中回路分别有多少条？
2
实例求解
1 2 A 1 1 1 4 3 3 0 0 0 0 0 0 0 0 0 1 0 1 0 1 0 1 0 0 1 0 0 0 1 0 A
8
例题
已知无向树T中有1个3度顶点，2个2度顶点，其余顶点全是树 叶，试求树叶数. 解 设有x片树叶，于是 n = 1+2+x = 3+x, 先依树的性质m=n1， 再根据握手定理： 2m = 2(n1) = 2(2+x) = 13+22+x， 解出x = 3，故T有3片树叶.
9
例题
已知无向树T有5片树叶，2度与3度顶点各1个，其余顶 点的度数均为4，求T的阶数n. 解 设T的阶数为n, 则边数为n1，4度顶点的个数为n7. 由握手定理得 2m = 2(n1) = 51+21+31+4(n7) 解出n = 8，4度顶点为1个.
2
1 3 2 2
0 0 0 0 0 0 0 0
0 0 1 0 0 0 1
A
3
1 5 4 A 4 4
无向图G有16条边，3个4度顶点，4个3度顶点，其余顶 点度数均小于3，问G的阶数n为几？ 解 设除3度与4度顶点外，还有x个顶点v1, v2, …, vx， 则 d(vi) 2，i =1, 2, …, x， 应用握手定理,得不等式 32=2m= Σd(vi)3*4+4*3+2x 得 x 4, 阶数 n 4+3+4=11.
14
1
实例
有向图D如图所示，求D的邻接矩阵 A与 A2, A3, A4. 问D 中长度 为1, 2, 3, 4的通路各有多少条？其中回路分别有多少条？
2
实例求解
1 2 A 1 1 1 4 3 3 0 0 0 0 0 0 0 0 0 1 0 1 0 1 0 1 0 0 1 0 0 0 1 0 A
8
例题
已知无向树T中有1个3度顶点，2个2度顶点，其余顶点全是树 叶，试求树叶数. 解 设有x片树叶，于是 n = 1+2+x = 3+x, 先依树的性质m=n1， 再根据握手定理： 2m = 2(n1) = 2(2+x) = 13+22+x， 解出x = 3，故T有3片树叶.
9
例题
已知无向树T有5片树叶，2度与3度顶点各1个，其余顶 点的度数均为4，求T的阶数n. 解 设T的阶数为n, 则边数为n1，4度顶点的个数为n7. 由握手定理得 2m = 2(n1) = 51+21+31+4(n7) 解出n = 8，4度顶点为1个.
2
1 3 2 2
0 0 0 0 0 0 0 0
0 0 1 0 0 0 1
A
3
1 5 4 A 4 4
离散数学——图论部分习题课
之和为24,而图G中其余点的度数小于3,即图G中其余点的
度数只可能是2或1(由于图G是连通图,所以无零度点). 由此可知,图G中至少有11个顶点: 3个4度点,4个3度点和 4个2度点; 至多有15个顶点: 3个4度点,4个3度点和8个1
度点.
7. 设G1,G2,G3,G4均是4阶3条边的无向简单图，
n ( n 1) 2
即m=n(n-1)/4, 而m为正整数,所以要么n=4k或n=4k+1, 所以不存在3个顶点和6个顶点的自补图.
9. 设有向简单D的度数列为2，2，3，3，入度列为 0，0，2，3，试求D的出度列。 解：设有向简单图D的度数列为2，2，3，3， 对应的顶点分别为v1,v2,v3,v4,
（1）1，1，2，3，5 （3）1，3，1，3，2 答案（2） （2）1，2，3，4，5 （4）1，2，3，4，6
Байду номын сангаас
）
则它们之间至少有几个是同构的？ 解： 4阶3条边非同构的无向简单图共有3个，因此 G1,G2,G3,G4中至少有2个是同构的。
8. 是否存在3个顶点和6个顶点的自补图？ 解: 由于顶点为n的无向完全图的边数为
n ( n 1) 2
.
设G的自补图为G’,则G与G’的边数相等. 设它们的边数各为m,于是有m+m=
本章重点
一、掌握有关图的基本概念：
邻接 关联 有向图
平行边 多重图
无向图
n阶图
底图
连通图
自回路（环） 简单图
二、掌握图中顶点的度数，握手定理及其推论 定理：设图G是具有n个顶点、m条边的无向图， 其中点集V={v1， v2，… vn }, 则
deg(
i 1
离散数学习题解答第6部分(图论)
离散数学习题解答 习题六 （第六章 图论）1．从日常生活中列举出三个例子，并由这些例子自然地导出两个无向图及一个向图。
[解] ①用V 代表全国城市的集合，E 代表各城市间的铁路线的集合，则所成之图G=（V ，E ）是全国铁路交通图。
是一个无向图。
②V 用代表中国象棋盘中的格子点集，E 代表任两个相邻小方格的对角线的集合，则所成之图G=（V ，E ）是中国象棋中“马”所能走的路线图。
是一个无向图。
③用V 代表FORTRAN 程序的块集合，E 代表任两个程序块之间的调用关系，则所成之图G+（V ，E ）是FORTRAN 程序的调用关系图。
是一个有向图。
2．画出下左图的补图。
[解] 左图的补图如右图所示。
3．证明下面两图同构。
a v 2 v 3 v 4图G图G ′[证] 存在双射函数ϕ:V →V ′及双射函数ψ : E →E ′ϕ (v 1)=v 1′ ϕ (v 1，v 2)=(v 1′，v 2′) ϕ (v 2)=v 2′ ϕ (v 2，v 3)=(v 2′，v 3′) ϕ (v 3)=v 3′ ϕ (v 3，v 4)=(v 3′，v 4′) ϕ (v 4)=v 4′ ϕ (v 4，v 5)=(v 4′，v 5) ϕ (v 5)=v 5′ ϕ (v 5，v 6)=(v 5′，v 6′) ϕ (v 6)=v 6′ϕ (v 6，v 1)=(v 6′，v 1′) ϕ (v 1，v 4)=(v 1′，v 4′) ϕ (v 2，v 5)=(v 2′，v 5′) ϕ (v 3，v 6)=(v 3′，v 6′)显然使下式成立：ψ (v i ，v j )=(v i ,v j ′)⇒ ϕ (v i )=v i ′∧ϕ (v j )=v j ′ (1≤i ·j ≤6) 于是图G 与图G ′同构。
4．证明（a ），（b ）中的两个图都是不同构的。
图G 中有一个长度为4的圈v 1v 2v 6v 5v 1，其各顶点的度均为3点，而在图G ′中却没有这样的圈，因为它中的四个度为3的顶点v 1'，v 5'，v 7'，v 3'不成长度的4的圈。
第7章 图论 [离散数学离散数学(第四版)清华出版社]
![第7章 图论 [离散数学离散数学(第四版)清华出版社]](https://img.taocdn.com/s1/m/58b7923143323968011c9244.png)
6/27/2013 6:02 PM
第四部分：图论（授课教师：向胜军）
21
例：
a j i h c g d
1(a)
无 向 图
b
f
e
2(b)
7(j) 8(g) 9(d) 10(i)
6(e)
3(c) 4(h)
5(f)
6/27/2013 6:02 PM
第四部分：图论（授课教师：向胜军）
22
例：
1(b)
有向图
第四部分：图论（授课教师：向胜军）
6
[定义] 相邻和关联
在无向图G中，若e=(a, b)∈E，则称a与 b彼此相邻(adjacent)，或边e关联 (incident) 或联结(connect) a, b。a, b称为边e的端点或 结束顶点(endpoint)。 在有向图D中，若e=<a, b>∈E，即箭头 由a到b，称a邻接到b，或a关联或联结b。a 称为e的始点(initial vertex)，b称为e的终点 (terminal/end vertex)。
证明思路：将图中顶点的度分类，再利用定理1。
6/27/2013 6:02 PM 第四部分：图论（授课教师：向胜军） 9
[定理3] 设有向图D=<V, E>有n个顶点，m 条边，则G中所有顶点的入度之和等于所 有顶点的出度之和，也等于m。
即：
d ( v i ) d ( v i ) m.
i 1 i 1
n
n
证明思路：利用数学归纳法。
6/27/2013 6:02 PM
第四部分：图论（授课教师：向胜军）
10
一些特殊的简单图：
(1) 无向完全图Kn(Complete Graphs)
离散数学图论
例：把下面的m叉树改写为二叉树。
14
第七章 图论
信 息 科 学 与 工 程 学 院
练习：把下面的有序树改写为二叉树。
。 。 。。 。 。。 。 。 。 知识点提示：
。 。。
。 。 。
。
课下自学
此方法可推广至有序森林到二叉树的转换。 此方法具有可逆性。
15
第七章 图论
信 息 科 学 与 工 程 学 院
给定一棵2叉树T，设它有t片树叶。设v为T的一个分枝点， 则v至少有一个儿子，最多有两个儿子。若v有两个儿 子，在由v引出的两条边上，左边的标上0，右边的标 上1；若v有一个儿子，在由v引出的边上可标上0，也
可标上1。设vi为T的任一片树叶，从树根到vi的通路
上各边的标号组成的0，1串组成的符号串放在vi处，t 片树叶处的t个符号串组成的集合为一个二元前缀码。
定义7-8.5
在根树中， 科 一个结点的通路长度为从树根到此结点的通路中的边 学 数。 与 分枝点的通路长度称为内部通路长度。 树叶的通路长度称为外部通路长度。
工 程 学 院
。 。 。 。。 A 。 。 。。
18
第七章 图论
信 息 科
定理7-8.2
若完全二叉树有n个分枝点，且内部通路长度总和为L，外 部通路长度总和为E，则 E=L+2n。 证明：
学 与 工 程 学 院
对分枝点数目n进行归纳证明。
。
当n=1时，如右图所示，
L=0， E=2，
。
。
显然， E=L+2n成立。
19
第七章 图论
信 息 科 学
定理7-8.2 若完全二叉树有n个分枝点，且内部通路长度总 和为L，外部通路长度总和为E，则 E=L+2n。 证明：
全版离散数学 练习题及答案.ppt
课件
例3 对任意两个集合A, B,试证 A (A B) A B
证明 对于任意的x
x A (A B)
x {x x A x ( A B)} x {x x A (x A B)} x {x x A (x A x B)} x {x x A (x A x B)} x {x x A x B}
课件
例10 求图的最小生成树
A 1B34 Nhomakorabea5
2 E
6
1A 2
B
E
4
6
C7 D
C
D
课件
例11
• 无向树T有7片树叶, 3个3度顶点,其余的 都是4度顶点，则T有几个4度顶点？
• 解:设T有x个4度顶点 顶点度数之和： 7+3*3+4x 由树的性质可得总边数： 7+3+x-1 由握手原理可得： 7+3*3+4x=2(7+3+x-1)
求g f
g f { 1,b , 2,b , 3,b }
课件
例12 求复合函数
X {1,2,3}, Y {p, q}, Z {a,b} f { 1, p , 2, p , 3, q } g { p,b , q,b }
求g f
g f { 1,b , 2,b , 3,b }
课件
例: 求幺元、零元、逆元
x A B 因为 x 是任意的,所以有
x ((x A (A B)) (x A B)) 的真值为T,
因此 A ( A B)课件 A B
例4 判断关系的性质
R1 { a, a , a,b , b,b , c,c }
a
1 1 0
M R 1 0 1 0
0 0 1
《离散数学》图论 (上)
12
无向图与有向图
v2
e1
e2
e3
v3
e4
v1
e5 (e1)={( v42, v24 )}
v4
(e2)={( v32, v23 )} (e3)={( v3, v4 )}
(e4)=({ v43, v34 )}
(e5)=({ v4,}v4 )
13
无向图与有向图
A B C
D E F
14
无向图与有向图
第八章 图论
第八章 图论
§8.1 基本概念
§8.1.1 无向图、有向图和握手定理 §8.1.2 图的同构与子图 §8.1.3 道路、回路与连通性 §8.1.4 图的矩阵表示
§8.2 欧拉图 §8.3 哈密尔顿图 §8.4 平面图 §8.5 顶点支配、独立与覆盖
2
无向图与有向图
3
无向图与有向图
一个无向图（undirected graph, 或graph） G 指一个三元组 (V, E, )，其中
vV
vV
24
特殊的图
假设 G=(V, E, ) 为无向图，若 G 中所有 顶点都是孤立顶点，则称 G 为零图（null graph）或离散图（discrete graph）；若 |V|=n，|E|=0，则称 G 为 n 阶零图 所有顶点的度数均相等的无向图称为正 则图（regular graph），所有顶点的度数 均为 k 的正则图称为k度正则图，也记作 k-正则图 注：零图是零度正则图
19
握手定理
定理（图论基本定理/握手定理）
假设 G=(V, E, ) 为无向图，则deg(v) 2 E ， vV
即所有顶点度数之和等于边数的两倍。
推论
在任何无向图中，奇数度的顶点数必是偶 数。
无向图与有向图
v2
e1
e2
e3
v3
e4
v1
e5 (e1)={( v42, v24 )}
v4
(e2)={( v32, v23 )} (e3)={( v3, v4 )}
(e4)=({ v43, v34 )}
(e5)=({ v4,}v4 )
13
无向图与有向图
A B C
D E F
14
无向图与有向图
第八章 图论
第八章 图论
§8.1 基本概念
§8.1.1 无向图、有向图和握手定理 §8.1.2 图的同构与子图 §8.1.3 道路、回路与连通性 §8.1.4 图的矩阵表示
§8.2 欧拉图 §8.3 哈密尔顿图 §8.4 平面图 §8.5 顶点支配、独立与覆盖
2
无向图与有向图
3
无向图与有向图
一个无向图（undirected graph, 或graph） G 指一个三元组 (V, E, )，其中
vV
vV
24
特殊的图
假设 G=(V, E, ) 为无向图，若 G 中所有 顶点都是孤立顶点，则称 G 为零图（null graph）或离散图（discrete graph）；若 |V|=n，|E|=0，则称 G 为 n 阶零图 所有顶点的度数均相等的无向图称为正 则图（regular graph），所有顶点的度数 均为 k 的正则图称为k度正则图，也记作 k-正则图 注：零图是零度正则图
19
握手定理
定理（图论基本定理/握手定理）
假设 G=(V, E, ) 为无向图，则deg(v) 2 E ， vV
即所有顶点度数之和等于边数的两倍。
推论
在任何无向图中，奇数度的顶点数必是偶 数。
离散数学-图论-习题公开课获奖课件百校联赛一等奖课件
e1 e2 e3 e4 e5 e6 e7 e8 e9 A100001010 B011000100 C000110010 D1 1 0 0 0 0 0 0 1 E000011100 F001100001
311页（2）构造一种欧拉图，其结点数v和边数e满足下述条件
a)v，e旳奇偶性一样。 b) v，e旳奇偶性相反。 假如不可能，阐明原因。
练习 321页（1）
(a) v*=5,e*=8,r*=5
(b) v*=7,e*=13,r*=12
(c) v*=5,e*=6,r*=3
(d) v*=7,e*=12,r*=7
321页(4)证明：若图G是自对偶旳，则e=2v-2。
证明： 若图G是自对偶旳，则v=v*，e=e*，即 r*=v=v*=r，e=e* 则由欧拉定理v-e+r=2 得v-e+v=2，即e=2v-2。 若图G是自对偶旳，则e=2v-2。
1 0 1 10
A=
1 0 0 00
1 0 1 00
0 0 0 00 i=4时，因为A[4,2]=1，将第四行
用Warshall算法求可
加到第2行，A不变。
达性矩阵。
i=5时，因为A旳第5列全为0，所
i=1时，因为A旳第一行 以A不变。
0 0 0 00
全为0，所以A不变。
i=2时，因为A旳第2列 全为0，所以A不变。
无向图G具有一条欧拉回 路，当且仅当G是连通旳，而且 全部结点度数全为偶数。下面旳 图中全部结点度数全为偶数，所
以都是欧拉图。
ห้องสมุดไป่ตู้v=3,e=3
v=5,e=5
v=4,e=4 v=4,e=6
v=7,e=8
v=6,e=7
311页（6）