离散数学教程-王元元-第10章 特殊图.pptVIP

离散数学 第10章 特殊图 第10章 特殊图 10.1.1 欧拉图及欧拉路径 定理10.1：无向图G为欧拉图当且仅当G连通，并且所有顶点的度都 是偶数。有向图G为欧拉图，当且仅当G是弱连通的，并且每 个顶点的出度与入度相等。 证：（无向图） 必要性： 设G为一欧拉图，那么G显然是连通的。 又由于G本身为一闭路径，它每经过一个顶点一次，便给这 一顶点增加度数2，因而各顶点的度均为该路径经历此顶点的 次数的两倍，从而均为偶数。 充分性：设G连通，且每个顶点的度均为偶数，证G为一欧拉图。 为此，对G的边数归纳。 10.1.1 欧拉图及欧拉路径 设想从G的任一顶点出发，沿着边构画，使笔不离开图 且不在构画过的边上重新构画。由于每个顶点都是偶数度， 笔在进入一个顶点后总能离开那个顶点，除非笔回到了起 点。在笔回到起点时，它构画出一条闭路径，记为H。从 图G中删去H的所有边，所得图记为G’，G’未必连通，但其 各顶点的度数仍均为偶数。考虑G’的各连通分支，由于它 们都连通，顶点度数均为偶数，而边数均小于m，因此据 假设都是欧拉图。此外，由于G连通，它们都与H共有一个 或若干个公共顶点(如上图)，因此它们与H一起构成一个闭 路径。所以说，G是一个欧拉图。 10.1.1 欧拉图及欧拉路径 例10.1(1) 哥尼斯堡问题——是否为一欧拉图 ？ 4个顶点都是奇数度的，所以不是 欧拉图，也不是欧拉路径。 结论：无论是否要求回到原地， 不重复走遍7桥是不可能的。 10.1.1 欧拉图及欧拉路径 例10.1(3) 一笔画游戏，一个欧拉图、欧拉路径的判定问题。 图 (a) 可以从一点出发一笔画所有边后回到起点；欧拉图 图 (b) 可以一笔画所有边，但不能使笔回到起点；欧拉路径 图 (c) 根本不可能一笔画所有边。非欧拉图、欧拉路径 10.1.1 欧拉图及欧拉路径 10.1.2 哈密顿图及哈密顿通路 10.1.2 哈密顿图及哈密顿通路 10.1.2 哈密顿图及哈密顿通路 用构造法证明G有哈密顿通路，即在G中构作出一条长为n-1的通路。 令P为G中任意一条长为p-1,p＜n,的通路，设其顶点序列为v1,v2,…,vp 。扩充P: (1) 如果有v ? v1,v2,…,vp, 它与v1或vp间有边相关联, 则可立即扩充P为长度为p的通路。 (2) 如果v1，vp均只与原通路P上的顶点相邻，如下可证： G中有一条包含v1,v2,…,vp，长度为p的回路。 如果v1与vp相邻，那么我们已经如愿。 如果v1与vi1 ,vi2 , …,vir相邻，1＜i1，i2, …, ir＜p, 考虑vp： (2.1) 若vp与vi1-1 ,vi2-1 , …, vir-1之一，例如vi1-1相邻，则可得到包含v1，v2，…，vp 的回路：（v1，v2，…，vi1-1 ,vp , vp -1 , …，vi1 , v1）如图10.6(a)所示。 (2.2) 若vp不与vi1-1 ,vi2-1 , …, vir-1中任何一个相邻，那么d (vp) ≤p - r - l，因而 d (v1)+d (vp)≤r+p–r–l = p–1＜n–1 与题设矛盾，因此(2.2)不可能发生，而(2.1)必然发生。 事实(2)得证。 10.1.2 哈密顿图及哈密顿通路 现考虑G中这条包含v1，v2，…，vp、长度为p的回路。 由于已证G为一连通图且p≤n-l，故必有回路外顶点v与回路上顶点(例如vk)相邻， (图 (b))，那么可以得到一条长度为p的、包含v1，v2，…，vp的通路： （v, vk ,vk-1,…, v1,vi1 ,vi1+1,…, vp ,vi1-1 ,…, vk+1） (图 (c))。 重复过程(l)，(2)不断扩充通路P，直至它的长度为n–1 ， 这时便得到G中的一条哈密顿通路。 定理的后半部分仿上可证。 10.1.2 哈密顿图及哈密顿通路 1