离散数学概论 第2版 第六章 特殊的图.ppt

几点说明：规定平凡图为欧拉图.欧拉通路是生成的简单通路，欧拉回路是生成的简单回路.环不影响图的欧拉性.**【定理1】证若G为平凡图无问题.下设G为n阶m条边的无向图.必要性设C为G中一条欧拉回路.(1)G连通显然.(2)?vi?V(G)，vi在C上每出现一次获2度，所以vi为偶度顶点.由vi的任意性，结论为真.充分性对边数m做归纳法（第二数学归纳法）.(1)m=1时，G为一个环，则G为欧拉图.(2)设m?k（k?1）时结论为真，m=k+1时如下证明：*什么是哈密顿周游世界问题？-我爱学习网(52xx.cn)*注意:此定理只是哈密尔顿图的必要条件,而不是充分条件.我们可以利用其逆否命题来判断某些图是否不是哈密尔顿图,即下述定理.)、*********下面给出一个判断偶图是否存在匹配的一个充分条件,对于任何偶图来说,都很容易确定这些条件.因此,在考察相异性条件之前,应首先试用这个充分条件.*****四色定理是一个著名的数学定理,通俗的说法是：每个平面地图都可以只用四种颜色来染色,而且没有两个邻接的区域颜色相同.四色问题又称四色猜想、四色定理,是世界三大数学猜想之一.人们发现,要证明宽松一点的“五色定理”（即“只用五种颜色就能为所有地图染色”,我们在后面会加以证明）很容易,但四色问题却出人意料地异常困难.曾经有许多人发表四色问题的证明或反例,但都被证实是错误的.1976年,数学家凯尼斯·阿佩尔和沃夫冈·哈肯借助电子计算机首次得到一个完全的证明,四色问题也终于成为四色定理.这是首个主要借助计算机证明的定理.*********二.欧拉公式证明:(续)（3）假设对少于m条边的所有连通平面图,欧拉公式成立.现考虑m条边的连通平面图,设它有n个结点.分以下两种情况：①若G是树,那么m＝n-1,这时r＝1,所以n-m+r＝n-(n-1)+1＝2.②若G不是树,则G中必有回路,因此有基本回路,设e是某基本回路的一条边,则G＝V,E-{e}仍是连通平面图,它有n个结点,m-1条边和r-1个面,按归纳假设知n-(m-1)+(r-1)＝2,整理得n-m+r＝2.所以对m条边时,欧拉公式也成立.欧拉公式得证.*二.欧拉公式例：求下面各图的顶点数V,边数E和区域数R.并检验欧拉公式.解：欧拉公式：V-E+R=2.图(a)：V=5,E=8,R=5,且5-8+5=2.图(b)：V=12,E=17,R=7,且12-17+7=2.图(c)：V=3,E=6,R=5,且3-6+5=2.图(d)：V=4,E=6,R=4,且4-6+4=2.图(e)：V=9,E=8,R=1,且9-8+1=2.图(f)：V=8,E=11,R=5,且8-11+5=2.*三.平面图判定根据平面的定义,无圈的图显然是平面图.故研究图的平面性问题,只需要限制有圈的一类图即可.判别方法一是：(1)对于有圈的图找出一个长度尽可能大的且边不相交的基本圈.(2)将图中那些相交于非结点的边,适当放置在已选定的基本圈内侧或外侧,若能避免除结点之外边的相交,则该图是平面图;否则,便是非平面图.*三.平面图判定*三.平面图判定*三.平面图判定*三.平面图判定判别方法二：根据库拉图斯基定理来作为判别平面图充要条件.在图论中,称K3,3和K5是库拉图斯基图.*三.平面图判定【定义】(1)同胚:若图G2可由图G1中的一些边上适当插入或涂抹度为2的有限个结点后而得到,则称G1与G2同胚.(2)细分:在图G的边uv上新增加一个二度结点,称为图G的细分.(3)细分图:一条边上也可以同时增加有限个二度结点,所得的新图称为原来图的细分图.*三.平面图判定【定理】库拉图斯基定理(Kuratowski定理)：一个图G是平面图的充要条件为G中不含同胚于K3,3或K5的子图.*三.平面图判定例a)图称为彼得森图,该图是非平面图.因为当删去边[v6,v8]和[v3,v4]时,它成为含有同胚于K3,3的子图,如图b)和c)所示.*三.平面图判定*三.平面图判定例：鉴别下图a)b)c)d)中哪些图是平面图.解：只有a)和b)是平面图.因为它们可以被画成没有交叉边的图形.*1.1欧拉图1.2哈密尔顿图1.3二部图1.4平面图1.5图的着色问题第