第11章特殊图105.ppt

《第11章特殊图105.ppt》由会员分享，可在线阅读，更多相关《第11章特殊图105.ppt（62页珍藏版）》请在第壹文秘上搜索。

1、离离 散散 数数 学学第第1111章章 特殊图特殊图2 22023-10-122023-10-1211.2 11.2 欧拉图欧拉图 11.2.1 11.2.1 欧拉图的引入与定义欧拉图的引入与定义定义定义11.2.1设设G是是无孤立结点的图无孤立结点的图，若存在一条通，若存在一条通路路(回路回路)，经过图中每边一次且仅一次经过图中每边一次且仅一次，则称此通，则称此通路路(回路回路)为该图的一条为该图的一条欧拉通路欧拉通路(回路回路)(Eulerian Entry/Circuit)。具有欧拉回路的图称为。具有欧拉回路的图称为欧拉图欧拉图(Eulerian Graph)。规定：规定：平凡图为欧拉图

2、。平凡图为欧拉图。以上定义既适合无向图，又适合有向图。以上定义既适合无向图，又适合有向图。3 32023-10-122023-10-12例例11.2.111.2.1判断下面的判断下面的6 6个图中，是否是欧拉图？是个图中，是否是欧拉图？是否存在欧拉通路？否存在欧拉通路？v v3 3v v1 1v v2 2v v4 4(c)(c)v v3 3v v1 1v v2 2v v4 4(a)(a)v v3 3v v1 1v v2 2v v4 4(b)(b)v v3 3v v1 1v v2 2v v4 4(f)(f)v v3 3v v1 1v v2 2v v4 4(d)(d)v v3 3v v1 1v v

3、2 2v v4 4(e)(e)欧拉图欧拉图 欧欧拉拉图图 不是欧拉图，但不是欧拉图，但存在欧拉通路存在欧拉通路 不存在欧不存在欧拉通路拉通路 不不存存在在欧欧拉拉通通路路 不是欧拉图，但存在欧拉通路不是欧拉图，但存在欧拉通路 4 42023-10-122023-10-1211.2.2-4 11.2.2-4 欧拉图的判定及应用欧拉图的判定及应用定理定理11.2.111.2.1 （含推论（含推论11.2.111.2.1）（1 1）无向图无向图G=G=是欧拉图，当且仅当是欧拉图，当且仅当G G是连通的，且仅有零个奇度数结点。是连通的，且仅有零个奇度数结点。（2 2）无向图无向图G=G=有欧拉通路但不

4、是欧有欧拉通路但不是欧拉图，当且仅当拉图，当且仅当G G是连通的，并且恰有两个奇是连通的，并且恰有两个奇度数结点。度数结点。（两个奇度数结点必是（两个奇度数结点必是G G中每条欧拉通路中每条欧拉通路的端点）的端点）例如例如5 52023-10-122023-10-12定理定理11.2.211.2.2 有向图有向图G G具有一条欧拉通路，当且仅当具有一条欧拉通路，当且仅当G G是连是连通的，且除了两个结点以外，其余结点的入度等于出度，通的，且除了两个结点以外，其余结点的入度等于出度，而这两个例外的结点中，一个结点的入度比出度大而这两个例外的结点中，一个结点的入度比出度大1 1，另，另一个结点的出

5、度比入度大一个结点的出度比入度大1 1。推论推论11.2.211.2.2 有向图有向图G G具有一条欧拉回路，当且仅当具有一条欧拉回路，当且仅当G G是是连通的，且所有结点的入度等于出度。连通的，且所有结点的入度等于出度。例如，对完全图例如，对完全图 Kn，因因 d(Kn)=n-1，故当故当n为奇数时是为奇数时是欧拉图，当欧拉图，当n为偶时不是欧拉图。为偶时不是欧拉图。图图 G 有欧拉通路有欧拉通路G 能能“一笔画一笔画”G 连通且连通且 G 中度数为奇数的点的个数不超过中度数为奇数的点的个数不超过26 62023-10-122023-10-12定义定义11.2.2 设设G=，eE，如果，如果

6、p(G-e)p(G)称称e为为G的的桥桥(Bridge)或或割边割边(Cut edge)。显然，显然，所有的悬挂边都是桥所有的悬挂边都是桥。求一个欧拉图的欧拉回路的求一个欧拉图的欧拉回路的FleuryFleury算法算法的简述：的简述：从任一点出发按下法来描画一条边不重复的通路，从任一点出发按下法来描画一条边不重复的通路，使在每一步中未描画的子图的割边仅当没有别的边使在每一步中未描画的子图的割边仅当没有别的边可选择时才被描画。可选择时才被描画。7 72023-10-122023-10-12例例：例：8 82023-10-122023-10-12例例11.2.311.2.3图中的三个图能否一笔画

7、？为什么？图中的三个图能否一笔画？为什么？v v1 1v v2 2v v3 3v v4 4v v5 5(b)(b)v v1 1v v2 2v v3 3v v4 4(c)(c)v v1 1v v2 2v v3 3v v4 4v v5 5(a)(a)解解 因为图因为图(a)(a)和和(b)(b)中分别有中分别有0 0个和个和2 2个奇度数结点，所以个奇度数结点，所以它们分别是欧拉图和存在欧拉通路，因此能够一笔画，并它们分别是欧拉图和存在欧拉通路，因此能够一笔画，并且在且在(a)(a)中笔能回到出发点，而中笔能回到出发点，而(b)(b)中笔不能回到出发点。中笔不能回到出发点。图图c c中有中有4 4

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

9、奇数的结点图中仅有两个度数为奇数的结点B B、C C，因而存在从，因而存在从B B到到C C的欧拉通路，蚂蚁乙走到的欧拉通路，蚂蚁乙走到C C只要走一条欧拉通路，边只要走一条欧拉通路，边数为数为9 9条，而蚂蚁甲要想走完所有的边到达条，而蚂蚁甲要想走完所有的边到达C C，至少要先，至少要先走一条边到达走一条边到达B B，再走一条欧拉通路，因而它至少要走，再走一条欧拉通路，因而它至少要走1010条边才能到达条边才能到达C C，所以乙必胜。，所以乙必胜。10102023-10-122023-10-1211.3 11.3 哈密顿图哈密顿图 11.2.1 11.2.1 哈密顿图的引入与定义哈密顿图的引

10、入与定义 定义定义11.3.111.3.1 经过图中经过图中每个结点一次且仅一次每个结点一次且仅一次的通的通路路(回路回路)称为称为哈密顿通路哈密顿通路(回路回路)。存在。存在哈密顿回路哈密顿回路的图称为的图称为哈密顿图哈密顿图。规定：规定：平凡图为哈密顿图平凡图为哈密顿图。以上定义既适合无向图，又适合有向图。以上定义既适合无向图，又适合有向图。11112023-10-122023-10-12二、二、Hamilton图图例例例例2 2只有哈密尔顿通路，但不是哈密尔顿图只有哈密尔顿通路，但不是哈密尔顿图哈密尔顿图哈密尔顿图无哈密尔顿通路无哈密尔顿通路12122023-10-122023-10-1

11、2例：例：对下面的图对下面的图v v3 3v v1 1v v2 2v v4 4(a)(a)v v3 3v v1 1v v2 2v v4 4(d)(d)v v3 3v v1 1v v2 2v v4 4(b)(b)v v5 5v v6 6v v7 7v v3 3v v1 1v v2 2v v4 4(e)(e)v v3 3v v1 1v v2 2v v4 4(f)(f)哈密哈密顿图顿图 不存不存在哈在哈密顿密顿通路通路 哈密哈密顿图顿图 不是哈密不是哈密顿图，但顿图，但存在哈密存在哈密顿通路顿通路 不存不存在哈在哈密顿密顿通路通路 13132023-10-122023-10-1211.3.2 11.

12、3.2 哈密顿图的判定哈密顿图的判定 定理定理11.3.1 设无向图设无向图G=是哈密顿图，是哈密顿图，V1是是V的任意的任意非空子集，则非空子集，则p(G-V1)|V1|其中其中p(G-V1)是从是从G中删除中删除V1后所得到图的连通分支数。后所得到图的连通分支数。证明证明 设设C 是是G 中一条中一条哈密尔顿回路。任取哈密尔顿回路。任取 V 中中非空子集非空子集V，因因 C 是是G 的的哈密尔顿回路含哈密尔顿回路含G 的所有点，故的所有点，故V 也是子图也是子图 C 的的非空子集。由点不重复的回路的特性知任意删去非空子集。由点不重复的回路的特性知任意删去C 中中|V|个个点，最多将点，最多

13、将C 分为分为|V|“段段”，即，即 P(C-V)|V|（*）而而 C 是是 G 的生成子图，又有的生成子图，又有：P(G-V)(C-V)所以所以 P(G-V)|V|14142023-10-122023-10-12推论推论11.3.111.3.1设无向图设无向图G=G=中存在哈密顿通路，中存在哈密顿通路，则对则对V V的任意非空子集的任意非空子集V V1 1，都有，都有p(G-Vp(G-V1 1)|V)|V1 1|+1|+1 v v3 3v v1 1v v2 2v v4 4v v5 5v v6 6v v7 7v v2 2v v4 4v v1 1v v5 5v v3 3例例 下列图不是哈密顿图，

14、其中下列图不是哈密顿图，其中V1=蓝色记号。蓝色记号。15152023-10-122023-10-12例例11.3.211.3.2证明图中不存在哈密顿回路。证明图中不存在哈密顿回路。a ab bc cg gi ih h证明证明 在图中，删除结在图中，删除结点子集点子集d,e,fd,e,f，得，得新图，它的连通分支为新图，它的连通分支为4 4个，由定理个，由定理11.3.111.3.1知，知，该图不是哈密顿图，因该图不是哈密顿图，因而不会存在哈密顿回路。而不会存在哈密顿回路。d df fe ea ab bc cg gi ih h16162023-10-122023-10-12 可验证彼得森图（下

15、图）不是哈密尔顿图，但可验证彼得森图（下图）不是哈密尔顿图，但满足满足 p(G-V1)|V1|。这表明定理。这表明定理11.3.111.3.1给出的条件给出的条件只是图只是图 G 是哈密尔顿图的是哈密尔顿图的必要条件而不是充分条必要条件而不是充分条件。件。17172023-10-122023-10-12例例 设设G=是具有是具有n个结点的简单无向图。如果对个结点的简单无向图。如果对任意两个不相邻的结点任意两个不相邻的结点u,vV，均有，均有 deg(u)+deg(v)n-1则则G是连通的。是连通的。证明证明 用反证法：用反证法：假设假设G有两个或更多连通分支。设一有两个或更多连通分支。设一个连

16、通分支有个连通分支有n1个结点，另一个连通分支有个结点，另一个连通分支有n2个结点。个结点。这二个连通分支中分别有两个结点这二个连通分支中分别有两个结点v1、v2。显然，。显然，deg(v1)n1-1，deg(v2)n2-1。从而。从而 deg(v1)+deg(v2)n1+n2-2 n-2与已知矛盾，故与已知矛盾，故G是连通的。是连通的。18182023-10-122023-10-12定理定理11.3.2 11.3.2 设设G=G=是具有是具有n n个结点的简单无向图。个结点的简单无向图。如果对任意两个不相邻的结点如果对任意两个不相邻的结点u,vVu,vV，均有，均有deg(u)+deg(v)n-1deg(u)+deg(v)n-1则则G G中存在哈密顿通路。中存在哈密顿通路。推论推论11.3.211.3.2 设设G=G=是具有是具有n n个结点的简单无向图。个结点的简单无向图。如果对任意两个不相邻的结点如果对任意两个不相邻的结点u,vVu,vV，均有，均有deg(u)+deg(v)ndeg(u)+deg(v)n则则G G中存在哈密顿回路。中存在哈密顿回路。推论推论11.3.311.3.