[理学]离散数学第24讲图论.ppt

將一个平面图画在平面上,用小刀沿着边切下,则这平面将分割成几块,这种块就称为图的面,即一个平面图的面定义为平面的一块。 与平面图有密切关系的一个图论的应用是图形的着色问题，这个问题最早起源于地图的着色，一个地图中相邻国家着以不同颜色，那么最少需用多少种颜色？一百多年前，英国盖思里(Guthrie)提出了用四种颜色即可对地图着色的猜想，1879年肯普(Kempe)给出了这个猜想的第一个证明，但到1890年希伍德(Hewood)发现肯普证明是错误的，但他指出肯普的方法 虽不能证明地图着色用四种颜色就够了，但可证明用五种颜色就够了，即五色定理成立。 此后四色猜想一直成为数学家感兴趣而未能解决的难题。直到1976年美国数学家阿佩尔和海肯宣布：他们用电子计算机证明了四色猜想是成立的。所以从1976年以后就把四色猜想这个名词改成“四色定理”了。为了叙述图形着色的有关定理，下面先介绍对偶图的概念。 2、自对偶图 如果图G的对偶图G*同构于G,则称G是自对偶图。 例：证明K3,3是非平面图。 如果K*3,3是平面图,则存在对偶图K3,3,由下表左侧K3,3的情况可推出右侧K*3,3的情况: 由上表(3)和(2)知,长度为5基本回路必有下图形式,否则将出现平行边而与(2)矛盾。 1、图的正常着色：图G的正常着色(或简称着色)是指对它的每一个结点指定一种颜色，使得没有两个邻接的结点有同一种颜色。如果图在着色时用了k种颜色，我们称G为k-可着色的。 2、色数：对于图G正常着色时，需要的最少颜色数称为G的色数，记作 。 5着色问题的证明 引理： 在平面连通的简单图中，至少有一个顶点v0，其次数d(v0)≤5。 证明： 反证法。 假设任何顶点次数都不小于6。由于是平面图故满足3n-6≥m。 故6n-12≥2m = ∑d(vi)≥6n 矛盾。 证毕。 定理 任何平面图都是5-可着色的。 证明思路：对结点个数v采用归纳法 (1)归纳基础：图G的结点数为v=1,2，3，4，5时，结论 显然成立。 (2)归纳假设：设G有k个结点时结论成立。即G是最多可 5-着色的。 (3)归纳推理：需要证明G有k+1个结点时结论仍成立。 先在G中删去度数小于5的结点u,根据归纳假设，所得 的图G-{u}有k个结点,结论成立。 然后考虑在G-{u}中加上一个结点的情况。 若加入的结点满足deg (u)5，则可以对u进行5-着色。 若加入的结点满足deg (u)=5，则与它邻接的5个结点可 以用4种颜色着色。分两中情况证明： 1.邻接顶点可属于不同连通分图中 2.邻接顶点属于同一个连通分图中 证毕。 雄关漫道真如铁，而今迈步从头越！ C S | S W U S T XDC 雄关漫道真如铁，而今迈步从头越！ 8.5 平面图 8.5.1 平面图 ? 先看一个例子。一工厂有A、B、C三个车间和L、M、N三个仓库,因为工作需要车间与仓库间将设专用车道,为了避免车祸,车道最好没有交点,问这可能吗? 定义8.5―1一个无向图G=〈V,E〉,如果能把它图示在一平面上,边与边只在顶点处相交的图叫平面图。 定义8.17　如果能把一个无向图G的所有结点和边画在平面上，使得任何两边除公共结点外没有其他交叉点，则称G为平面图，否则称G为非平面图。 1750年，欧拉发现，任何一个凸多面体，若有n个顶点、m条棱和r个面，则有n-m+r＝2。这个公式称之为欧拉公式，我们要将它推广到平面图上来，即得到平面图欧拉公式。 8.5.2　平面图欧拉公式 定义8.18　设G是一个平面图，由图中的边所包围的其内部不包含图的结点和边的区域，称为G的一个面，记为r。 包围该面的诸边所构成的回路称为这个面的边界， 面r的边界的长度称为该面的次数，记为D(r)。 区域面积有限的面称为有限面，区域面积无限的面称为无限面。 显然，平面图有且仅有一个无限面。 例 在右图中有9个结点，11 条边。其中含有的平面： r1的边界为abca，D(r1)＝3； r2的边界为becijikicb，D(r2)＝9； r3的边界为bdeb，D(r3)＝3。 r0的边界为abdeheca，D(r0)＝7； r1、r2和r3是有限面，r0是无限面。 r1 r2 r3 r0 结论： 在一个平面图中，所有面的次数之和等于图中边数的二倍。 证明　因任何一条边，或者是两个面边界的公共边，或者是在一个面中作为边界被重复计算两次，故平面图所有面的次数之和等