离散数学习题课-图论.ppt
图 论2023/2/202 of 220图的基本概念n主要内容主要内容n无向图、有向图、关联与相邻、简单图、完全图、子图、补图；握手定理与推论；图的同构n通路与回路及其分类n无向图的连通性与连通度n有向图的连通性及其分类n图的矩阵表示n最短路径2023/2/203 of 220基本要求n深刻理解握手定理及推论的内容并能灵活地应深刻理解握手定理及推论的内容并能灵活地应用它们用它们n深刻理解图同构、简单图、完全图、子图、补深刻理解图同构、简单图、完全图、子图、补图、的概念以及它们的性质及相互之间的关系图、的概念以及它们的性质及相互之间的关系n记住通路与回路的定义、分类及表示法记住通路与回路的定义、分类及表示法n深刻理解与无向图连通性、连通度有关的多个深刻理解与无向图连通性、连通度有关的多个概念概念n会判别有向图连通性的类型会判别有向图连通性的类型n熟练掌握用邻接矩阵及其幂求有向图中通路与熟练掌握用邻接矩阵及其幂求有向图中通路与回路数的方法，会求可达矩阵回路数的方法，会求可达矩阵 2023/2/204 of 220练习1n9阶无向图阶无向图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 阶图阶图矛盾矛盾.2023/2/205 of 220练习2(1)D中有几种非同构的圈？中有几种非同构的圈？(2)D中有几种非圈非同构的简单回路？中有几种非圈非同构的简单回路？(3)D是哪类连通图是哪类连通图?(4)D中中v1到到v4长度为长度为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如图所示，如图所示，回答下列各问：回答下列各问：2023/2/206 of 220练习2(续续)(1)D中有几种非同构的圈？中有几种非同构的圈？(2)D中有几种非圈非同构的简单回路？中有几种非圈非同构的简单回路？(3)D是哪类连通图是哪类连通图?(1)D中有中有3种非同构的圈，种非同构的圈，长度分别为长度分别为1,2,3.(2)D中有中有3种非圈的非同构种非圈的非同构的简单回路，它们的长度分的简单回路，它们的长度分别为别为 4,5,6.(3)D是强连通的是强连通的.2023/2/207 of 220练习2(续续)nD的邻接矩阵的前的邻接矩阵的前4次幂次幂.(4)D中中v1到到v4长度为长度为1,2,3,4的通路各多少的通路各多少条？其中几条是非初级的简单通路？条？其中几条是非初级的简单通路？(5)D中中v1到到v1长度为长度为1,2,3,4的回路各多少的回路各多少条？讨论它们的类型条？讨论它们的类型.2023/2/208 of 220练习2(续续)(4)v1到到v4长度为长度为1,2,3,4的通路数分别为的通路数分别为0,0,2,2.其中只有其中只有长度为长度为4的两条是非初级的简单通路（定义意义下），见的两条是非初级的简单通路（定义意义下），见下图所示下图所示.2023/2/209 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)4 4的全的全1矩阵矩阵.2023/2/2010 of 220习题3 求最短路径nDijstra算法算法V2V13V3V6V7V4V5914218736252023/2/2011 of 220树n主要内容主要内容n无向树及其性质n生成树、最小生成树n根树及其分类、最优树2023/2/2012 of 220习题课n基本要求基本要求n深刻理解无向树的定义及性质深刻理解无向树的定义及性质n熟练地求解无向树熟练地求解无向树n准确地求出给定带权连通图的最小生成树准确地求出给定带权连通图的最小生成树 克鲁斯卡尔算法与普里姆算法克鲁斯卡尔算法与普里姆算法n会画会画n阶（阶（n较小）非同构的无向树及根树较小）非同构的无向树及根树（1 n 6）n熟练掌握求最优树的方法熟练掌握求最优树的方法2023/2/2013 of 220习题1n已知无向树已知无向树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片树叶片树叶.2023/2/207.8 根树14 of 220习题2 求带权5,9,11,13,17的最优树.解2023/2/2015 of 220习题3 求最小生成树n克鲁斯卡尔算法与普里姆算法克鲁斯卡尔算法与普里姆算法
