离散数学习题课-图论省公开课一等奖全国示范课微课金奖PPT课件.pptx

该【离散数学习题课-图论省公开课一等奖全国示范课微课金奖PPT课件 】是由【liaoyumen】上传分享，文档一共【15】页，该文档可以免费在线阅读，需要了解更多关于【离散数学习题课-图论省公开课一等奖全国示范课微课金奖PPT课件 】的内容，可以使用淘豆网的站内搜索功能，选择自己适合的文档，以下文字是截取该文章内的部分文字，如需要获得完整电子版，请下载此文档到您的设备，方便您编辑和打印。图 论
第1页
2025/2/10
2 of 220
图基本概念
主要内容
无向图、有向图、关联与相邻、简单图、完全图、子图、补图；握手定理与推论；图同构
通路与回路及其分类
无向图连通性与连通度
有向图连通性及其分类
图矩阵表示
最短路径
第2页
2025/2/10
3 of 220
基本要求
深刻了解握手定理及推论内容并能灵活地应用它们
深刻了解图同构、简单图、完全图、子图、补图、概念以及它们性质及相互之间关系
记住通路与回路定义、分类及表示法
深刻了解与无向图连通性、连通度相关多个概念
会判别有向图连通性类型
熟练掌握用邻接矩阵及其幂求有向图中通路与回路数方法，会求可达矩阵
第3页
2025/2/10
4 of 220
练习1
9阶无向图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 阶图矛盾.
第4页
2025/2/10
5 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如图所表示，回答以下各问：
第5页
2025/2/10
6 of 220
练习2 (续)
(1) D中有几个非同构圈？
(2) D中有几个非圈非同构简单回路？
(3) D是哪类连通图?
(1) D中有3种非同构圈，长度分别为1,2,3.
(2) D中有3种非圈非同构简单回路，它们长度分别为 4,5,6.
(3) D是强连通.
第6页
2025/2/10
7 of 220
练习2(续)
D邻接矩阵前4次幂.
(4) D中v1到v4长度为1,2,3,4通路各多少
条？其中几条是非初级简单通路？
(5) D中v1到v1长度为1,2,3,4回路各多少
条？讨论它们类型.
第7页
2025/2/10
8 of 220
练习2(续)
(4) v1到v4长度为1,2,3,4通路数分别为0,0,2,2. 其中只有长度为4两条是非初级简单通路（定义意义下），见下列图所表示.
第8页
2025/2/10
9 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矩阵.
第9页
2025/2/10
10 of 220
习题3 求最短路径
Dijstra算法
V2
V1
3
V3
V6
V7
V4
V5
9
1
4
2
1
8
7
3
6
2
5
第10页