第7章 欧拉图(最新整理版).pptxVIP

7.4 欧拉图与哈密尔顿图;7.4.1 欧拉图; 每逢假日， 城中居民进行环城游玩， 人们对此提出了一个“遍游”问题， 即能否有这样一种走法， 使得从某地出发通过且只通过每座桥一次后又回到原地呢？ ; 我们将图7.4.1中的哥尼斯堡城的4块陆地部分分别标以A， B， Ｃ， D， 将陆地设想为图的结点， 而把桥画成相应的连接边， 这样图7.4.1可简化成图7.4.2。 于是七桥“遍游”问题等价于在图7.4.2中， 从某一结点出发找到一条回路， 通过它的每条边一次且仅一次， 并回到原来的结点。 ;图 7.4.1哥尼斯堡七桥问题示图 ; 图 7.4.2哥尼斯保七桥问题简化图 ; 定义 7.4.1 给定无孤立结点的图G， 若存在一条经过G中每边一次且仅一次的回路， 则该回路为欧拉回路。 具有欧拉回路的图称为欧拉图。 例如， 给出如图7.4.3所示的两个图， 容易看出， (a)是欧拉图， 而(b)不是欧拉图。 ; 图 7.4.3; 定理 7.4.1 连通图G是欧拉图的充要条件是G的所有结点的度数都是偶数。 证明: 必要性： 设G是一欧拉图， α是G中的一条欧拉回路。 当α通过G的任一结点时， 必通过关联于该点的两条边。 又因为G中的每条边仅出现一次， 所以α所通过的每个结点的度数必定是偶数。 ; 图 7.4.4 图G ; 充分性： 我们可以这样来作一个闭迹β， 假设它从某结点A开始， 沿着一条边到另一结点， 接着再从这个结点， 沿没有走过的边前进， 如此继续下去。 因为我们总是沿着先前没有走过的新边走， 又由于图G的边数有限， 所以这个过程一定会停止。 但是， 因为每一个结点都与偶数条边关联， 而当沿β前进到达结点v 时， 若v≠A， β走过了与v关联的奇数条边， 这样在v上总还有一条没有走过的边。 因此， β必定返回停止在A（见图7.4.4）。 ; 如果β走遍了G的所有边， 那么我们就得到所希望的一条欧拉回路。 如果不是这样， 那么在β上将有某一结点B， 与它关联的一些边尚未被β走过（因G连通）。 但是， 实际上， 因为β走过了与B关联的偶数条边， 因此不属于β的与B关联的边也是偶数条。 对于其他有未走过边所关联的所有结点来说， 上面的讨论同样正确。 于???若设G1是G－β的包含点B的一个连通分支， 则G1的结点全是偶数度结点。 ; 运用上面的讨论， 我们在G1中得到一个从B点出发的一条闭迹β1。 这样我们就得到了一条更大的闭迹， 它是从A点出发沿β前进到达B， 然后沿闭迹β1回到B， 最后再沿β由B走到A。 如果我们仍然没有走遍整个图， 那么我们再次把闭迹扩大， 以此类推， 直到最后得到一个欧拉回路。 由于在七桥问题的图7.4.2中， 有４个点是奇数度结点， 故不存在欧拉回路， 七桥问题无解。 ; 在图7.2.3中， (a)图的每个结点的度数都为４， 所以它是欧拉图；(b)图不是欧拉图。 但我们继续考察(b)图可以发现， 该图中有一条路v2v3v4v5v2v1v5， 它经过(b)图中的每条边一次且仅一次， 我们把这样的路称为欧拉路。 定义7.4.2 通过图G的每条边一次且仅一次的路称为图G的欧拉路。 对于欧拉路有下面的判定方法。 ; 定理7.4.2 连通图G具有一条连接结点vi和vj的欧拉路当且仅当vi和vj是G中仅有的奇数度结点。 ; 证明: 将边(vi， vj)加于图G上， 令其所得的图为G′（可能是多重图）。 由定理7.4 .1知： G有连接结点vi和vj的欧拉路， iff G′有一条欧拉回路， iff G′的所有结点均为偶度结点， iff G的所有结点除vi和vj外均为偶度结点， iff vi和vj是G中仅有的奇度结点。; 我国民间很早就流传一种“一笔画”游戏。 由定理7.4 .1和定理7.4.2知， 有两种情况可以一笔画。 1) 如果图中所有结点是偶数度结点， 则可以任选一点作为始点一笔画完； 2) 如果图中只有两个奇度结点， 则可以选择其中一个奇度结点作为始点也可一笔画完。 ; 【例7.4.1】图7.4.5(a)是一幢房子的平面