离散数学第7章 几类特殊的图.ppt

Chapter 7 几类特殊的图 本章讨论几类在理论研究和实际应用中都有着重要意义的特殊图： Euler图; Hamilton图; 平面图。 7.1 Euler图 1. Euler图的有关概念 7.2 Hamilton 图 所谓哈密尔顿图,起源于一个名叫“周游世界”的游戏, 它是由英国数学家哈密尔顿(Hamilton)于1859年提出的.他用一个正十二面体的20个顶点代表20个大城市(见下左图), 这个正十二面体同构于一个平面图(见下右图).要求沿着正十二面体的棱, 从一个城市出发, 经过每个城市恰好一次, 然后回到出发点. 这个游戏曾风靡一时, 它有若干个解.下页给出了一个解. 7.5 平面图 本节仅讨论无向图. 有些实际问题要求把图画在一个平面上，同时使 得图的边仅仅在节点处才相交. 例如单层印刷电路版、集成电路的布线等问题就需要满足上面的要求. 1. 铁路互不交叉能否实现 二部图：V划分为V1和V2, 任意边关联的两个节点中一个在V1中, 一个在V2中. 完全二部图： V1中的所有节点与V2的所有节点都邻接的二部图，记为Km, n 2. 土地分割问题 ● 2.Euler公式 Theorem (Euler公式) 任意(n, m)连通平面图的面数 r = m – n +2, 即 n –m + r = 2。 证：对边数m进行归纳： 1） m =1时，仅有两种类型连通平面图， n=2, r=1或 n=1, r=2，均满足公式。 2）设对m -1条边公式成立，现考虑m条边的连通平面图G， 若G是树，那么m =n-1，而此时r=1,成立， 若G不是树，则G中至少存在一个圈c，设j是c的一条边， 令G＃=G-{j}，则G＃也是连通平面图，且有n个结点, m -1条边和r-1个面，由归纳假设 n-(m -1)+(r-1)=2,即n- m +r=2， 故公式对m条边也成立， 由归纳法可知，公式成立。 例 设连通平面图除无限面是四边形外, 其余面全为三角形, 结点数为 n = 50, 求边数m和面数k. 解 由前述定理和欧拉公式，有 定理 若连通平面图的每个面的度数至少为k，则 证 设G有r个面，则由定理可得 再由欧拉公式，得 m = 10, n = 5 3n - 6 = 9 m 3n - 6 K5 不是平面图 K5是否平面图? Corollary 1 任意(n, m)简单平面图, 若n ? 3, 则m ? 3n - 6. Theorem 任何简单平面图必存在一个度数? 5 的节点. Proof 不妨设n ? 3. 假设?v?V, deg(v) ? 6. * * A B C D A B C D 定义 设G = (V, E)是任意图, G中经过所有边一次且仅一次的路称为Euler轨迹; G中经过所有边一次且仅一次的回路称为Euler回路; 存在Euler回路的图称为Euler图或简称为E图. Euler回路?Euler轨迹, 但反过来一般不成立. a b c d e 欧拉轨迹： (a, c, d, e, b, d, a, b) 欧拉回路 ? d e a b c d e a b c 无 欧拉回路： (a, e, c, d, e, b, a, ) 无欧拉轨迹；无欧拉回路 2. Euler定理 Theorem 设G是连通无向图, 则G是Euler图的充要条件是G的每节点度数为偶数. 证：必要性显然。 充分性： 设G的所有结点都是偶结点，来构造一条欧拉回路。 从G的任一结点v0开始，必可沿着某一边到另一结点v1。 v1为偶结点，可沿着没有走过的边至v2… 每个结点均为偶结点，这个过程必以回到v0告终。 则得到一条简单回路C1，如经过了G所有边，则为欧拉回路。 否则，C1没有经过的边中至少有一条与C1的某个结点 关联（否则G不连通）。 设此结点为vk,从它出发，沿着C1没有走过的边走，与上述同法， 必回到vk ，构成简单回路C2，加到C1中得到更大简单回路。 重复这个过程，由于边数有限，最后得到一条Euler回路。 根据Euler定理容易得出 Theorem 设G是连通无向图, 则G不是Euler图但存在Euler轨迹 G有2个度数为奇数的节点. 根据定理,“七桥问题”无解, 甚至不存在Euler轨迹. 设G中仅有奇结点v1 ，v2，在它们之间添一条边，所得图记为G`。 G有连接v1 ，v2的欧拉路 G`有一条欧拉回路 G`所有结点为偶结点 G的所有结点除了v1 ，v2奇结点外，