离散数学习题课-图论

《离散数学习题课-图论》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、图论2021/7/62of220图的基本概念主要内容无向图、有向图、关联与相邻、简单图、完全图、子图、补图；握手定理与推论；图的同构通路与回路及其分类无向图的连通性与连通度有向图的连通性及其分类图的矩阵表示最短路径2021/7/63of220基本要求深刻理解握手定理及推论的内容并能灵活地应用它们深刻理解图同构、简单图、完全图、子图、补图、的概念以及它们的性质及相互之间的关系记住通路与回路的定义、分类及表示法深刻理解与无向图连通性、连通度有关的多个概念会判别有向图连通性的类型熟练掌握用邻接矩阵及其幂求有向图中通路与回路数的方法，会求可达矩阵2021/7

2、/64of220练习19阶无向图G中，每个顶点的度数不是5就是6.证明G中至少有5个6度顶点或至少有6个5度顶点.方法一：穷举法方法二：反证法设G中有x个5度顶点，则必有(9x)个6度顶点，由握手定理推论可知，(x,9x)只有5种可能：(0,9),(2,7),(4,5),(6,3),(8,1）它们都满足要求.否则，由握手定理推论可知，“G至多有4个5度顶点并且至多有4个6度顶点”，这与G是9阶图矛盾.2021/7/65of220练习2(1)D中有几种非同构的圈？(2)D中有几种非圈非同构的简单回路？(3)D是哪类连通图?(4)D中v1到v4长度为

3、1,2,3,4的通路各多少条？其中几条是非初级的简单通路？(5)D中v1到v1长度为1,2,3,4的回路各多少条？讨论它们的类型.(6)D中长度为4的通路（不含回路）有多少条？(7)D中长度为4的回路有多少条？(8)D中长度4的通路有多少条？其中有几条是回路？(9)写出D的可达矩阵.3．有向图D如图所示，回答下列各问：2021/7/66of220练习2(续)(1)D中有几种非同构的圈？(2)D中有几种非圈非同构的简单回路？(3)D是哪类连通图?(1)D中有3种非同构的圈，长度分别为1,2,3.(2)D中有3种非圈的非同构的简单回路，它们的长度分别为

4、4,5,6.(3)D是强连通的.2021/7/67of220练习2(续)D的邻接矩阵的前4次幂.(4)D中v1到v4长度为1,2,3,4的通路各多少条？其中几条是非初级的简单通路？(5)D中v1到v1长度为1,2,3,4的回路各多少条？讨论它们的类型.2021/7/68of220练习2(续)(4)v1到v4长度为1,2,3,4的通路数分别为0,0,2,2.其中只有长度为4的两条是非初级的简单通路（定义意义下），见下图所示.2021/7/69of220练习2(续)(5)v1到v1长度为1,2,3,4的回路数分别为1,1,3,5.其中长度为1的是初级的(

5、环)；长度为2的是复杂的；长度为3的中有1条是复杂的，2条是初级的；长度为4的有1条是复杂的，有4条是非初级的简单回路.(6)长度为4的通路(不含回路)为33条.(7)长度为4的回路为11条.(8)长度4的通路88条，其中22条为回路.(9)44的全1矩阵.2021/7/610of220习题3求最短路径Dijstra算法V2V13V3V6V7V4V5914218736252021/7/611of220树主要内容无向树及其性质生成树、最小生成树根树及其分类、最优树2021/7/612of220习题课基本要求深刻理解无向树的定义及性质熟练地求解无向树

6、准确地求出给定带权连通图的最小生成树克鲁斯卡尔算法与普里姆算法会画n阶（n较小）非同构的无向树及根树（1n6）熟练掌握求最优树的方法2021/7/613of220习题1已知无向树T中有2个3度顶点，3个2度顶点，其余顶点全是树叶，试求树叶数解解本题用树的性质m=n1，握手定理.设有x片树叶，于是n=2+3+x=5+x,2m=2(n1)=2(5+x)=23+32+x解出x=2，故T有2片树叶.2021/7/67.8根树14of220习题2求带权5,9,11,13,17的最优树.解2021/7/615of220习题3求最小生成树克鲁斯卡尔算

7、法与普里姆算法