离散数学 -贾振华 第九章 特殊图.pptVIP

第9章 特殊图 本章学习目标 本章主要介绍了三个特殊的图：树、二部图和平面图。通过本章学习，读者应该掌握以下内容： ?(1)树的定义 l??????(2)生成树、最小生成树的定义 l??????(3)最小生成树的求法 l??????(4)最优树的求法 l??????(5)有向树与根树 l??????(6)二部图 l??????(7)平面图的概念及有关性质 l??????(8)平面图的对偶的概念 (9)图的着色问题 9.1 树 9.1 树 9.1.1 无向树 9.1.2 生成树与最小生成树 9.1.3 有向树与根树 9.2 二部图 9.3 平面图 9.3.1 平面图的定义 9.3.2 欧拉公式 9.3.3 库拉托夫斯基定理 9.3.4 平面图的对偶图 9.1 树 9.1.1 无向树 9.1 树 9.1.1 无向树 9.1 树 9.1.1 无向树 9.1 树 9.1.2 生成树与最小生成树 9.1 树 9.1.2 生成树与最小生成树 9.1 树 9.1.2 生成树与最小生成树 9.1 树 9.1.2 生成树与最小生成树 9.1 树 9.1.2 生成树与最小生成树 9.1 树 9.1.2 生成树与最小生成树 9.1 树 9.1.3 有向树与根树 9.1 树 9.1.3 有向树与根树 9.1 树 9.1.3 有向树与根树 9.1 树 9.1.3 有向树与根树 9.1 树 9.1.3 有向树与根树 9.1 树 9.1.3 有向树与根树 9.1 树 9.1.3 有向树与根树 9.1 树 9.1.3 有向树与根树 9.1 树 9.1.3 有向树与根树 9.1 树 9.1.3 有向树与根树 9.1 树 9.1.3 有向树与根树 9.1 树 9.1.3 有向树与根树 9.1 树 9.1.3 有向树与根树 9.1 树 9.1.3 有向树与根树 9.2 二部图 9.2 二部图 9.2 二部图 9.2 二部图 9.2 二部图 9.2 二部图 9.2 二部图 9.2 二部图 9.2 二部图 9.2 二部图 9.3 平面图 9.3 平面图 9.3 平面图 9.3 平面图 9.3 平面图 9.3 平面图 9.3 平面图 9.3 平面图 9.3 平面图 9.3 平面图 9.3 平面图 9.3 平面图 9.3 平面图 9.3 平面图 9.3 平面图 9.3 平面图 9.3 平面图 9.3 平面图 9.3 平面图 9.3 平面图 9.3 平面图 9.3 平面图 9.3 平面图 9.3 平面图 9.3 平面图 9.3 平面图 9.3 平面图 本章小结 例如图9.2-2所示的三个图中，（a）和（c）不是二部图，（b）是二部图。 定义9.2.2 设G=V,E是一个二部图，如果E的一个子集M中的任意两条边均不相邻，则称M为二部图G的一个匹配（或边独立集）。匹配M中的边所关联的顶点称为M的饱和顶点，称G的其他顶点为的非饱和顶点。 若在M中再加入一条边后M不再匹配，则称M为极大匹配。边数最多的极大匹配称为最大匹配。 在图9.2-1（a）所示的二部图中，边集{(v1,v2)}、 {(v2,v4)}、 {(v1,v4),(v2,v5)}都是匹配，而且{(v2,v4)}、 {(v1,v4),(v2,v5)} 是极大匹配， {(v1,v4),(v2,v5)}是最大匹配。 例:某教研室有5位教师x1,x2,x3,x4,x5，要开设5门课程y1,y2， y3,y4,y5。已知x1能讲授y1和y2 ； x2能讲授y2和y3 ； x3能讲授y2和y5 ； x4只能讲授y3 ； x5能讲授y3,y4,和y5。问：能否通过适当安排，使每位教师只讲一门课程，且每门课程也只有一位教师讲授？ 解：我们只要求这个二部图一个匹配即可(如图9.2-4所示)。 解：我们只要求这个二部图一个匹配即可(如图9.2-4所示)。 图9.2-3 图9.2-4 定义9.2.3 设M是二部图G的一个匹配，若G中每个顶点都是M的饱和顶点，则称M为G中的完美匹配。 定义9.2.4 设G=V1,V2,E为一个二部图，|V1|≤|V|2，M为G中最