离散数学7-6对偶图与着色7-7树+复习

7-6对偶图与着色掌握对偶图的定义，会画图G的对偶图

G*掌握自对偶图的定义及必要条件。与平面图有密切关系的一个图论的应用是图形的着色问题，这个问题最早起源于地图的着色，一个地图中相邻国家着以不同颜色，那么最少需用多少种颜色？一百多年前，英国格色里(Guthrie)提出了用四种颜色即可对地图着色的猜想，1879年肯普(Kempe)给出了这个猜想的第一个证明，但到1890年希伍德(Hewood)发现肯普证明是错误的，但他指出肯普的方法虽不能证明地图着色用四种颜色就够了，但可证明用五种颜色就够了，即五色定理成立。此后四色猜想一直成为数学家感兴趣而未能解决的难题。直到1976年美国数学家阿佩尔和黑肯宣布：他们用电子计算机证明了四色猜想是成立的。所以从1976年以后就把四色猜想这个名词改成“四色定理”了。为了叙述图形着色的有关定理，下面先介绍对偶图的概念。一、对偶图1、对偶图定义7-6.1对具有面F1,F2,...,

Fn的连通平面图G=<V,E>实施下列步骤所得到的图G*称为图G的对偶图（dualofgraph）：如果存在一个图G*=<V*，E*>满足下述条件：（a）在G的每一个面Fi的内部作一个G*的顶点vi*

。即对图G的任一个面Fi内部有且仅有一个结点vi*∈V*。(b)若G的面Fi，Fj有公共边ek，则作ek*=(vi*，vj*)，且ek*与ek相交。即若G中面Fi与Fj有公共边界ek

，那么过边界的每一边ek作关联vi*与vj*的一条边ek*=(vi*,vj*)

。

ek*与G*的其它边不相交。(c)当且仅当ek只是一个面Fi的边界时(割边)，vi*存在一个环e*k与ek相交。即当ek为单一面Fi的边界而不是与其它面的公共边界时，作vi*的一条环与ek相交（且仅交于一处）。所作的环不与G*的边相交。则称图G*为G的对偶图。实线边图为平面图，虚线边图为其对偶图。v*=r，e*=e，r*=v2、自对偶图定义7-6.2

如果图G的对偶图G*同构于G,则称G是自对偶图。二、图的着色1、问题的提出该问题起源于地图的着色问题。图着色的三种情况:对点着色是对图G的每个结点指定一种颜色，使得相邻结点的颜色不同;对边着色给每条边指定一种颜色使得相邻的边的颜色不同，给面着色给每个面指定一种颜色使得有公共边的两个面有不同的颜色。对边着色和对面着色均可转化为对结点着色问题。从对偶图的概念，可以看到，对于地图的着色问题，可以归纳为对于平面图的结点的着色问题，因此四色问题可以归结为要证明对于任何一个平面图，一定可以用四种颜色，对它的结点进行着色，使得邻接的结点都有不同的颜色。2、图的正常着色：图G的正常着色(或简称着色)是指对它的每一个结点指定一种颜色，使得没有两个邻接的结点有同一种颜色。如果图在着色时用了n种颜色，我们称G为n-色的图。3、色数：对于图G着色时，需要的最少颜色数称为G的色数，记作x(G)。

证明一个图的色数为n，首先必须证明用n种颜色可以着色该图，其次证明用少于n种颜色不能着色该图。4、对点着色的鲍威尔方法：第一步：对每个结点按度数递减次序进行排列(相同度数的结点次序可随意)第二步：用第一种颜色对第一个结点着色，并按次序对与前面着色点不相邻的每一点着同样的颜色。第三步：用第二种颜色对未着色的点重复第二步，用第三种颜色继续这种做法，直到全部点均着了色为止。5、定理7-6.1：对于完全图Kn有χ(Kn)=n。证明：因为完全图的每一个结点与其他各个结点都邻接，故n个结点的着色数不能少于n，又n个结点的着色数至多为n，故χ(Kn)=n。6、定理7-6.2：连通平面图G=<V，E>至少有三个结点，则必有一点u∈V使得deg(u)≤5。证明：设|V|=v，|E|=e，若G的每个结点均有

v

deg(u)≥6，

deg(vi)=2|E|=2e

i=1

则有2e≥6v，即e≥3v>3v-6，与定理矛盾。*7、定理7-6.3：(五色定理)任意平面图最多是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正常着色。若加入的结点满足deg(u)=5，则与它邻接的5个结点可以用4种颜色着色。分两中情况证明：

.对调v1,v3两个结点的颜色后，给着v1的颜色。

.对调v2,v4两个结点的颜色后，给着v2的颜色。

自从四色猜想提出后，一百多年来，一直成为数学上的著名难题，它吸引许许多多的人，为之而作出大量辛劳，也得到很多重要结果，但长久未能得到解决。直到1976年6月，由美国伊利诺斯大学两名数学家爱普尔(K.I.Apple)、黑肯(W.Haken)在考西(J.Koch)帮助下借助于电子计算机，用了一百多亿次逻辑判断，花了1200多机时才证明四色猜想是成立的，从此宣告，四色猜想成为四色定理。相应地有下面的定理。9、定理：对于任何地图M，M是四着色的，即χ(M)≤4。8、四色定理：平面图的色数不超过4。作业P321：（1）（4）7-7树树是图论中重要的概念之一，它在计算机科学中应用非常广泛，这里将介绍树的一些基本性质和应用。一、树的概念1、定义7-7.1：一个连通且无回路的无向图称为树（tree）。树中度数为1的结点称为树叶（leave）。度数大于1的结点称为分支点（branchednode）或内点。每个连通分支是树的无向图称为森林。平凡图也是树，称为平凡树。2、定理7-7.1：给定图T=<V，E>，以下关于树的定义是等价的。(1)无回路的连通图(2)无回路且e=v-1(3)连通且e=v-1(4)无回路，但增加一边后得到且仅得一个回路(5)连通，但删去任一边后就不连通(6)每一对结点间有且仅有一条通路。证明思路：6个命题可以循环推出。即(1)(2)(3)(4)(5)(6)(1)3、定理7-7.2：任一棵树中至少存在两个叶。证明：因T连通则u∈T，deg(u)≥1。设T有k个一度点，其它点均大于等于2，则

2e=∑deg(vi)≥k+2(v-k)=2v-k。

因e=v-1，故2(v-1)≥2v-k，则k≥2。二、生成树有一些图，本身不是树，但它的子图却是树，一个图可能有许多子图是树，其中很重要的一类是生成树。1、生成树定义7-7.2：若G的生成子图是一棵树，则称这棵树为G的生成树。设G的一棵生成树为T，则T中的边称为树枝，在G中而不在T中的边称弦，所有弦的集合称为生成树T的补。e1、e7、e5、e8、e3是T的树枝，e2、e4、e6是T的弦，{e2、e4、e6}是T的补。2、定理7-7.3：连通图至少有一棵生成树。证明：如果连通图G无回路，则G本身就是它的生成树。如果G有回路，则在回路上任取去掉一条边，得到图G1仍是连通的，如G1仍有回路，重复上述步骤，直到图Gi中无回路为止，此时该图就是G的一棵生成树。由定理的证明过程可以看出，一个连通图可以有许多生成树。因为在取定一个回路后，就可以从中去掉任一条边，去掉的边不一样，故可能得到不同的生成树。一般如果G有v个点e条边连通，则e≥v-1，则G删除e-(v-1)条边，破坏了e-(v-1)个回路，必成G的一棵生成树，这是”破圈法”。也可以从e条边中选取v-1条边并使它不含有回路，这是”避圈法”。3、定理7-7.4：一条回路和任何一棵生成树的补至少有一条公共边。证明：若有一条回路和一棵生成树的补没有公共边，那么这回路包含在生成树中，然而这是不可能的，因为一棵生成树不能包含回路。4、定理7-7.5：一个边割集和任何生成树至少有一条公共边。证明：若有一个边割集和一棵生成树没有公共边，那么删去这个边割集后，所得子图必包含该生成树，这意味着删去边割集后仍是连通图，与边割集定义矛盾。5、最小生成树设G=<V，E>是一连通图，G的每一条边e有权C(e)，G的生成树T的权w(T)就是T的边的权和。定义7-7.3：在图G所有生成树中，树权最小的那棵树称为G的最小生成树。

构造图的一棵最小生成树，即：在e条带权的边中选取n-1条边（不构成回路），使“权值之和”为最小。该问题等价于：具体做法:先构造一个只含n个顶点的子图SG，然后从权值最小的边开始，若它的添加不使SG中产生回路，则在SG上加上这条边，如此重复，直至加上n-1条边为止。考虑问题的出发点:为使生成树上边的权值之和达到最小，则应使生成树中每一条边的权值尽可能的小。克鲁斯卡尔算法的基本思想：abcdegf195141827168213ae12dcbgf7148531621例如:7121819求最小生成树的克鲁斯卡尔(Kruskal)算法(避圈法)：a)在G中选取最小权的边，记作e1，置i=1。b)当i=n-1时结束，否则转c)。c)设已选择边为e1，e2，……ei，此时无回路。在G中选取不同于这i条边的边ei+1，该边使得{e1，…，ei+1}生成的子图中无回路，并ei+1是满足该条件中权最小的一条边。d)置i：=i+1，转b)。定理7-7.6：克鲁斯卡尔(Kruskal)算法产生的是最小生成树。作业327页（6）(b)的最小生成树有5棵，最小生成树的树权为11。(a)的最小生成树：7-8根树及其应用一、根树1、有向树定义7-8.1

如果一个有向图在不考虑边的方向时是一棵树，那么，该有向图称为有向树。2、根树

定义7-8.2

一棵有向树,如果恰有一个结点的入度为0，其余所有结点的入度都为1,则称为根树(rootedtree)。入度为0的结点称为T的树根。出度为0的结点称为树叶。出度不为0的结点称为分支点或内点。

根树的画法有：树根在下，向上生长；树根在上，向下生长。习惯把有向树的根画在最上方，边的箭头全指向下，则可以省略全部箭头，树根到一个结点的有向通路的长度称为该点的层数。所有结点的最大层数称为树高。3、子树定义7-8.3：任一结点v及其后代导出的子图称为根树的子树。

定义7-8.3

根树包含一个或多个结点,这些结点中的某一个称为根,其他所有结点被分成有限个子根树。

在有向树中，结点的出现次序是没有意义的。但实际应用中，有时要给出同一级中结点的相对次序，这便导出有序树的概念。4、有序数：在根树中规定了每一层上结点的次序，称为有序树。为表示结点间的关系，有时借用家族中的术语。定义在以v0为根的树中，（1）v1，v2,…，vk称为v0的儿子，v0称为它们的父亲。vi，vj

同为一顶点v的儿子时，称它们为兄弟。（2）顶点间的父子关系的传递闭包称为顶点间的祖孙关系。即当vi为vi+1(i=1,2,…,l-1)的父亲时，v1是vl的祖先，vl为v1的子孙。（3）根树T自身及以它的树根的子孙为根的根树（T的子图），均称为T的子树（subtree），后者又称为T的真子树。5、m叉树

定义7-8.4：在根树中,若每个结点的出度均≤m，则称T为m元树(m叉树)，若每个分支点的出度恰好等于m，则称T为m叉完全树，若T的所有树叶的层数均相同，则称T正则m元树。若m元树是有序的，则称T为m元有序树，若m元完全树是有序的则称T为完全m元有序树，若m元正则树是有序的，则称T为m元正则有序树。当m=2时，称为二元树，二元有序树的每个结点至多有两个儿子，其序按左右分，分别为左儿子，右儿子，任一分支点最多有两棵子树，称为左子树和右子树。当m=2时，便可得到常用的二叉树、完全二叉树和正则二叉树。不难看出，二叉树中的每个结点v，至多有两个子树，分别称为v的左子树和右子树。若v只有一个子树，则称它为左子树或右子树均可。在二叉树的图形表示中，v的左子树画在v的左下方，v的右子树画在v的右下方。

6.定理7-8.1设有完全m叉树，其树叶的数目为t,分支数为i,则(m-1)×i=t-1。

7.定义7-8.5在根树中，一个结点的通路长度，就是从树根到该结点的通路中的边数。分支点的通路长度称为内部通路长度，树叶的通路长度称为外部通路长度。二、最优树二叉树的一个重要应用就是最优树问题。给定一组数w1，w2，…，wn。令一棵二叉树有n个叶结点，并对它们分别指派w1，w2，…，wn作为权，则该二叉树称为加权二叉树。

8.定理7-8.2设有完全二叉树有n个分支点，且内部通路长度为总和为I

，外部通路长度总和为E

，则

E=I+2n。

已知w1，w2，…，wn为权，T0为加权二叉树，其权为w(T0)，如果对任意加权二叉树T，它的权是w(T)，均有w(T0)≥w(T)，则称T0是最优树或Huffman树。

9.定义7-8.6在带权二叉树T中，若带权为wi树叶，其通路长度为L(wi),把

t

w(T)=wi

L(wi)

i=1

称为该带权二叉树权，所有带权w1,w2,…,wt的二叉树树中，w(T)最小的那棵树，称为最优树。离散数学总复习曾庆田Email：qtzeng@163.com2008年.12月第一章

命题逻辑第二章

谓词逻辑第四章函数

第六章格和布尔代数第七章

图论第一篇数理逻辑第二篇集合论

第三章集合与关系第四篇图论教学内容：数理逻辑、集合论、代数结构与布尔代数和图论共四部分。第五章

代数结构第三篇代数系统第一章命题逻辑

一、知识点1．命题的概念、表示方法；联结词的逻辑意义。2．命题公式的递归定义，自然语言翻译成命题公式3．真值表的构造、命题公式等价的概念。4．重言式与蕴涵式的定义、逻辑意义，逻辑等价与逻辑蕴涵的意义和证明方法。常用的逻辑等价公式和逻辑蕴涵公式。

5．命题公式的对偶式、合取范式、析取范式、主合取范式、主析取范式。逻辑小项、逻辑大项。任给公式化为析取范式、任给公式化为主析取范式、任给公式化为合取范式、任给公式化为主合取范式。

6．命题逻辑的推理理论，主要的推理方法：真值表法、直接证明法、间接证明法。常用推理规则：P规则、T规则、CP规则。重点命题符号化主析（合）取范式求取方法命题逻辑推理第2章谓词逻辑一、知识点1.谓词的概念与表示方法2.命题函数与量词3.谓词逻辑的合式公式与自然语言的翻译4.谓词中变元约束5.谓词逻辑的等价式和蕴含式6.前束范式7.推理理论谓词逻辑的推理方法规则：P、T规则；US、UG、ES、EG规则公式表：命题逻辑的等价式、蕴含式；谓词逻辑的常用等价式和蕴含式；推理方法： 直接证明方法 间接证明方法 反证法

CP规则重点谓词逻辑推理方法

一、知识点1．集合的基本概念与表示方法；2．集合的运算:并、交、对称差、幂集、划分、覆盖；3．序偶与笛卡尔积；4．关系及其表示、关系矩阵、关系图；5．关系的性质，复合关系、逆关系；6．关系的闭包运算：t(R),r(R),s(R),tr(R)；第三章集合与关系7．集合的划分与覆盖、等价关系与等价类；相容关系；细分；8．序关系、偏序集、哈斯图。9.偏序集中特殊的元素极小元、极大元最小元、最大元上界、下界上确界、下确界第三章集合与关系重点关系的三种闭包求取方法关系的性质证明一、知识点1．函数的概念，定义域、值域、定义域与前域的关系、值域与陪域的关系，入射函数、满射函数、双射函数。2．复合函数、逆函数的概念，复合函数与关系复合的联系与区别，逆函数与逆关系的联系与区别。第四章函数第五章 代数结构运算的性质：封闭性、结合性、分配性、交换性；特殊的元素：幺元、零元、逆元、等幂元的识别主要的代数系统：广群、半群、独异点、群、子群；代数系统之间的关系；交换群和循环群；陪集、拉格朗日定理；同态映射、同构映射；环、同态象、域重点半群、含幺半群、群、Abel群的运算性质半群、含幺半群、群、Abel群的证明方法第6章格与布尔代数一、知识点格的概念，偏序