第11章特殊图ppt课件.ppt

《第11章特殊图ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、离散数学电子科技大学08八月2021数学科学学院第11章特殊图11.2欧拉图11.2.1欧拉图的引入与定义定义11.2.1设G是无孤立结点的图，若存在一条通路(回路)，经过图中每边一次且仅一次，则称此通路(回路)为该图的一条欧拉通路(回路)(EulerianEntry/Circuit)。具有欧拉回路的图称为欧拉图(EulerianGraph)。规定：平凡图为欧拉图。以上定义既适合无向图，又适合有向图。例11.2.1判断下面的6个图中，是否是欧拉图？是否存在欧拉通路？v3v1v2v4(c)v3v1v2

2、v4(a)v3v1v2v4(b)v3v1v2v4(f)v3v1v2v4(d)v3v1v2v4(e)欧拉图欧拉图不是欧拉图，但存在欧拉通路不存在欧拉通路不存在欧拉通路不是欧拉图，但存在欧拉通路11.2.2-4欧拉图的判定及应用定理11.2.1（含推论11.2.1）（1）无向图G=是欧拉图，当且仅当G是连通的，且仅有零个奇度数结点。（2）无向图G=有欧拉通路但不是欧拉图，当且仅当G是连通的，并且恰有两个奇度数结点。（两个奇度数结点必是G中每条欧拉通路的端点）例如定理11.2.2有向图

3、G具有一条欧拉通路，当且仅当G是连通的，且除了两个结点以外，其余结点的入度等于出度，而这两个例外的结点中，一个结点的入度比出度大1，另一个结点的出度比入度大1。推论11.2.2有向图G具有一条欧拉回路，当且仅当G是连通的，且所有结点的入度等于出度。例如，对完全图Kn，因d(Kn)=n-1，故当n为奇数时是欧拉图，当n为偶时不是欧拉图。图G有欧拉通路G能“一笔画”G连通且G中度数为奇数的点的个数不超过2定义11.2.2设G=，e∈E，如果p(G-e)＞p(G)称e为G的桥(Bridge)或割

4、边(Cutedge)。显然，所有的悬挂边都是桥。求一个欧拉图的欧拉回路的Fleury算法的简述：从任一点出发按下法来描画一条边不重复的通路，使在每一步中未描画的子图的割边仅当没有别的边可选择时才被描画。例例：例11.2.3图中的三个图能否一笔画？为什么？v1v2v3v4v5(b)v1v2v3v4(c)v1v2v3v4v5(a)解因为图(a)和(b)中分别有0个和2个奇度数结点，所以它们分别是欧拉图和存在欧拉通路，因此能够一笔画，并且在(a)中笔能回到出发点，而(b)中笔不能回到出发点。图c中有4个度

5、数为3的结点，所以不存在欧拉通路，因此不能一笔画。例11.2.4蚂蚁比赛问题甲、乙两只蚂蚁分别位于图的结点A、B处，并设图中的边长度相等。甲、乙进行比赛：从它们所在的结点出发，走过图中所有边最后到达结点C处。如果它们的速度相同，问谁先到达目的地？A(甲)B(乙)C解图中仅有两个度数为奇数的结点B、C，因而存在从B到C的欧拉通路，蚂蚁乙走到C只要走一条欧拉通路，边数为9条，而蚂蚁甲要想走完所有的边到达C，至少要先走一条边到达B，再走一条欧拉通路，因而它至少要走10条边才能到达C，所以乙必胜。11.3哈

6、密顿图11.2.1哈密顿图的引入与定义定义11.3.1经过图中每个结点一次且仅一次的通路(回路)称为哈密顿通路(回路)。存在哈密顿回路的图称为哈密顿图。规定：平凡图为哈密顿图。以上定义既适合无向图，又适合有向图。二、Hamilton图例例2只有哈密尔顿通路，但不是哈密尔顿图哈密尔顿图无哈密尔顿通路例：对下面的图v3v1v2v4(a)v3v1v2v4(d)v3v1v2v4(b)v5v6v7v3v1v2v4(e)v3v1v2v4(f)哈密顿图不存在哈密顿通路哈密顿图不是哈密顿图，但存在哈密顿通路不存在哈

7、密顿通路11.3.2哈密顿图的判定定理11.3.1设无向图G=是哈密顿图，V1是V的任意非空子集，则p(G-V1)≤

8、V1

9、其中p(G-V1)是从G中删除V1后所得到图的连通分支数。证明设C是G中一条哈密尔顿回路。任取V中非空子集V’，因C是G的哈密尔顿回路含G的所有点，故V’也是子图C的非空子集。由点不重复的回路的特性知任意删去C中

10、V’

11、个点，最多将C分为

12、V’

13、“段”，即P(C-V’)≤

14、V’

15、（*）而C是G的生成子图，又有：P(G-V’)≤ω(C-V’)所以P(G-V’)≤

16、V’

17、

18、推论11.3.1设无向图G=中存在哈密顿通路，则对V的任意非空子集V1，都有p(G-V1)≤

19、V1

20、+1v3v1v2v4v5v6v7v2v4v1v5v3例下列图不是哈密顿图，其中V1=｛蓝色记号｝。例11.3.2证明图中不存在哈密顿回路。abcgih证明在图中，删除结点子集｛d,e,f｝，得新图，它的连通分支为4个，由定理11.3.1知，该图不是哈密顿图，因而不会存在哈密顿回路。dfeabcgih可验证彼得森图（下图）不是哈密尔顿图，但满足p(G-V1)≤

21、