离散数学E图和H

《离散数学E图和H》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第八章E图和H图7/18/20211离散数学§8.1七桥问题与E图七桥问题：有四块陆地与连结它们的七座桥，问能否从这四块陆地中的任意一块出发，经过每一座桥恰好一次，最后回到原地？7/18/20212离散数学一笔画该问题等价于“能否一笔画出下图？”Euler证明了，七桥问题是无解的。图中：顶点表示陆地，边表示陆地之间的桥。7/18/20213离散数学E图定义8.1.1：设G是一个图，经过G的每一条边的链称为E链；闭的E链称为E闭链。如果G中存在E链，称G为半E图；如果G中存在E闭链，称G为E图。下面的讨论中设G是非平凡的连通图

2、。7/18/20214离散数学无奇点的连通图是E图引理8.1.1：连通图G中无奇点，则G是E图。证明：设G是无奇点的连通图且G不是E图。在所有连通无奇点的非E图中，选一个边最少的图G。因G的每个顶点的度至少是2，从而G必含闭链。为什么？若G不含回路，则G是树。我们知道树中至少有两个悬挂点（奇点）。矛盾，所以G中一定含有回路。而回路就是闭链。如果回路之间有重复出现的边，我们可以去掉重复者，使每条边仅出现一次，这样就得到了一条闭链。所以G中必含闭链。设C是G中最长的闭链，由假设C不是E闭链，于是G–E(C)中必含非平凡连通分支G

3、且G中无奇点，显然q(G)

4、C中的每个点都既是起点也是终点。于是，从C上的任一点u出发，每经过一个顶点v，就有两条与v关联的边出现(一进一出)。这样，C上的每个顶点，也即G的每个顶点的度均为偶数，故G中无奇点。由引理8.1.1和8.1.1’，我们有：定理8.1.1：连通图G是E图当且仅当G中无奇点。7/18/20217离散数学半E图中最多有两个奇点推论8.1.1：G是半E图当且仅当G中最多有两个奇点。证明：(必要性)设G是半E图，C是G的一条E链。除起点与终点外，C中每个顶点的度均为偶数。又因G连通，故G最多有两个奇点。(充分性)设G最多只有两个奇点。

5、若G无奇点，则由定理8.1.1知，G为E图，亦为半E图；若G有两个奇点，设为u和v,则在G中加入e=uv的边，使G中无奇点。由定理8.1.1知，G+e为E图，即G+e含E闭链C，于是C–e构成G的一条E链，所以G是半E图。7/18/20218离散数学哥尼斯城堡桥不是E图半E图7/18/20219离散数学§8.2周游世界问题与H图周游世界问题:用一个正十二面体的二十个顶点来代表二十个城市，要求从其中任一顶点出发，沿着这个正十二面体的棱走遍这二十个顶点，且每个城市只经过一次，最后回到起点。该问题等价于“能否从下图找一条含所有顶点

6、的回路？”7/18/202110离散数学H图定义8.2.1：设G是一个图，含G的每个顶点的通路称为H通路；起点与终点重合的H通路称为H回路；如果G中存在H回路，称G为H图；若G中存在H通路，称G为半H图；说明：H图必是半H图，反之不然。?7/18/202111离散数学Herschel图该图是半H图。因为它是一个具有奇数个顶点的二分图。所以不可能有H回路。？因为二分图中的回路一定是偶数条边。(定理5.5.2)7/18/202112离散数学H图的一个必要条件定理8.2.1如果G是一个H图，则对V(G)的任何非空真子集S，均成立：

7、(G–S)

8、S

9、(8.1)证明：设C是G的H回路(G的所有顶点都在C上)，则显然有(C–S)

10、S

11、成立，其中SV(G)。由于C–S是G–S的生成子图，C–S的连通分支数不比G–S的少，因此：(G–S)(C–S)

12、S

13、故(8.1)式成立。7/18/202113离散数学G(H图)C(H回路）定理8.2.1证明图示7/18/202114离散数学一个非H图的判定取S为红色点集。

14、S

15、=5。(G–S)=6＞

16、S

17、根据定理8.2.1，此图不是H图。7/18/202115离散数学注意：这只是必要条件注意定理8.2.

18、1只是判断H图的必要条件，有的图虽然满足条件，却不是H图。如右边的Peterson图不是H图。可是它却满足定理8.2.1的条件。Peterson图Peterson图是半H图而不是H图。7/18/202116离散数学H图的一个充分条件定理8.2.2：设G是p(3)阶简单图。如果G中任何两个