离散数学教案 编号：C1701 课时安排：2学时教学课型：理论课√实验课口习题课口实践课口其它口 题目（教学章、节或主题）： 17平面圆及图的若备 §17.1平面图的基本概色 §17.2欧拉公式 教学目的要求（分掌握、热悉、了解三个层次）： 1。掌握平面图的定义 2 掌握平面图的Euler公式 3. 基本掌握平面图的一些常见性质：了解树的基本定义及性质 教学重点、难点： 1)重点：平面图的基本概念，Euler公式 2)难点：平面图的基本概念，Euler公式 教学方法 利用黑板，CAI课件等教学 教学用具： 黑板，CA课件及其辅助设备。 教学内容（注明：幸重点 #难点 ?疑点) 一、平面图的基本概念 1,定义设一个无向图G=。若能把它画在平面上，且除V中的顶点之外，任意两条边均不相 交，则称该图为平面图。画出的没有边相交的图叫G的平面嵌入（平图）。 [例]平面图的例子。 B C 0 有些图表面上看上去有边交叉，但经过改画后，就可使边不交叉，则这样的图实际上是平面图。但 有些图，无论怎样改画都避免不了边的交叉，这样的图就是非平面图。 [例]两个典型的非平面图：K,K3(库拉图斯基图)。 判别平面图的一种直观方法 ()若一个图无基本回路，则它是一个平面图：否则从有基本回路的图找出一个长度尽可能大且边不 1701
1701 离 散 数 学 教 案 编号：C1701 课时安排： 2 学时 教学课型：理论课√ 实验课□ 习题课□ 实践课□ 其它□ 题目（教学章、节或主题）： Ch17 平面图及图的着色 §17.1 平面图的基本概念 §17.2 欧拉公式 教学目的要求（分掌握、熟悉、了解三个层次）： 1． 掌握平面图的定义 2． 掌握平面图的 Euler 公式 3． 基本掌握平面图的一些常见性质；了解树的基本定义及性质 教学重点、难点： 1） 重点：平面图的基本概念，Euler 公式 2） 难点：平面图的基本概念，Euler 公式 教学方法: 利用黑板,CAI 课件等教学. 教学用具: 黑板,CAI 课件及其辅助设备. 教学内容（注明：* 重点 # 难点 ？疑点）： *一、平面图的基本概念 1．定义 设一个无向图 G=。若能把它画在平面上，且除 V 中的顶点之外，任意两条边均不相 交，则称该图为平面图。画出的没有边相交的图叫 G 的平面嵌入（平图）。 [例]平面图的例子。 A B C D E 有些图表面上看上去有边交叉，但经过改画后，就可使边不交叉，则这样的图实际上是平面图。但 有些图，无论怎样改画都避免不了边的交叉，这样的图就是非平面图。 ［例］两个典型的非平面图: 5 33 K , K （库拉图斯基图）。 判别平面图的一种直观方法: (1)若一个图无基本回路，则它是一个平面图; 否则从有基本回路的图找出一个长度尽可能大且边不
相交的基本回路 (2)将图中那些交叉的边，适当放置在己选定的基本回路内侧或外侧。若最后能避免边的交叉，则该 图是平面图，否则它是非平面图 2.定义设G是一个（连通）平面图，若由G的若干条边组成的回路所界定的区域内不含G的任何边和 顶点，则称这样的区域为G的一个（有限）面。面积无限的面叫无限面。包围这个面的各条边所构成 的回路，称为该面的边界，它的长度称为面f的次数，记为dg()。用F表示G中所有面的集合。 [例]求下列平面图的面、面的次数。 e 二、相关定理 1.定理若G=w,D是平面图，则合dcg(0-2。 2.定理设G=是连通平面图，则nm+f2 3.定理设G=是连通平面图，Vm,Em,每个面的次数至少为1023，则m≤1-2(-2) 4.定理设G=是连通的简单平面图，n,Em,且n≥3，则m≤3n-6。 5.定理设G=是连通的简单平面图，Vm,Fm,则G中至少有一个顶点的度数不超过5 三、Euler公式 1.定理(Euler公式)设G为连通平图，则v-g+中=2。 推论对平图G的任二平面嵌入H及R都有H=MR)。 推论当v23时，若G为简单平面图，则≤3v-6。 推论设G为简单平面图，则8≤5。 四、课常小结（约5分钟）
1702 相交的基本回路; (2)将图中那些交叉的边，适当放置在已选定的基本回路内侧或外侧。若最后能避免边的交叉，则该 图是平面图，否则它是非平面图。 2．定义 设 G 是一个(连通)平面图，若由 G 的若干条边组成的回路所界定的区域内不含 G 的任何边和 顶点，则称这样的区域为 G 的一个（有限）面。面积无限的面叫无限面。包围这个面 f 的各条边所构成 的回路，称为该面的边界，它的长度称为面 f 的次数，记为 deg(f)。用 F 表示 G 中所有面的集合。 ［例］求下列平面图的面、面的次数。 a b c d e f 二、相关定理 1．定理 若 G=是平面图，则 f F deg (f)=2|E|。 2．定理 设 G=是连通平面图，则 n-m+f=2。 3．定理 设 G=是连通平面图，|V|=n，|E|=m，每个面的次数至少为 l(l 3)，则 m l − 2 l (n-2)。 4．定理 设 G=是连通的简单平面图，|V|=n，|E|=m，且 n 3，则 m 3n-6。 5．定理 设 G=是连通的简单平面图，|V|=n，|E|=m，则 G 中至少有一个顶点的度数不超过 5。 三、Euler 公式 1．定理 (Euler 公式) 设 G 为连通平图，则 - + = 2 。 推论 对平图 G 的任二平面嵌入 H 及 R 都有(H) = (R) 。 推论 当 3 时，若 G 为简单平面图，则 3 - 6 。 推论 设 G 为简单平面图，则 5 。 推论 K5 为非平面图。 推论 K3，3 为非平面图。 四、课堂小结（约 5 分钟）
离散 数学教案 编号：C1702 课时安排： 2学时教学课型：理论课√实验课口习题课口实践课口其它口 题目（教学章、节或主题）： Ch17平面图及图的若色 §17.3平面图的判 §17.4平面图的对偶图 教学目的要求（分掌握、热悉、了解三个层次）： 1.了解平面图的判定定理(Kuratowski定理)片 2. 了解平面图的对偶图及简单性质 教学重点、难点： )重点：平面图的判断 2)难点：平面图的判断 教学方法： 利用黑板，CA课件等教学 教学用具： 黑板，CAI课件及其辅助设备。 教学内容（注明：幸重点#难点？疑点）： 一、平面图的判断（约45分钟） 1.定义若图G1与G2同构或图G2可由图G1中的一些边上适当插入度为2的结点或涂抹掉2度的结 点合并相邻边后得到，则称G1与G2同胚。 2.定义若图G中相邻顶点山v的初等收缩为 (1)刷除边u,v,(2)用W代替(uv).(3)W关联uv关联的一切边（除(uv) 3.定理（库拉图斯基定理）一个图G是平面图一G中不含同胚于K3,3或K5的子图。 4. 定理（库拉图斯基定理）一个图G是平面图一G中没有收缩到K3,3或K5的子图 ,平面图的对偶图（约40分钟） 1.定义平图G的对偶图(dual graph)G*是这样的一个图：它们之间有如下的一一对应关系 G的面fG*的顶点：G的边eG*的边e*。 且G*的顶点I*与2*被边e*连接台G的面1与2被边e分隔 列如， 左面所示平图G的对偶图G*=(V,E)为 V*=1* ，f5*}, E*={c1*=f门*5*，c2*=6*5*，c3*=2*5*，.,c8*=2*3*}。 1703
1703 离 散 数 学 教 案 编号：C1702 课时安排： 2 学时 教学课型：理论课√ 实验课□ 习题课□ 实践课□ 其它□ 题目（教学章、节或主题）： Ch17 平面图及图的着色 §17.3 平面图的判断 §17.4 平面图的对偶图 教学目的要求（分掌握、熟悉、了解三个层次）： 1． 了解平面图的判定定理（Kuratowski 定理）； 2． 了解平面图的对偶图及简单性质 教学重点、难点： 1） 重点：平面图的判断 2） 难点：平面图的判断 教学方法: 利用黑板,CAI 课件等教学. 教学用具: 黑板,CAI 课件及其辅助设备. 教学内容（注明：* 重点 # 难点 ？疑点）： *一、平面图的判断（约 45 分钟） 1．定义 若图 G1 与 G2 同构或图 G2 可由图 G1 中的一些边上适当插入度为 2 的结点或涂抹掉 2 度的结 点合并相邻边后得到，则称 G1 与 G2 同胚。 2．定义若图 G 中相邻顶点 u,v 的初等收缩为 （1）删除边(u,v),(2)用 W 代替(u,v),(3)W 关联 u,v 关联的一切边（除（u,v））. 3．定理 (库拉图斯基定理)一个图 G 是平面图G 中不含同胚于 K3，3 或 K5 的子图。 4．定理 (库拉图斯基定理)一个图 G 是平面图G 中没有收缩到 K3，3 或 K5 的子图。 二、平面图的对偶图（约 40 分钟） 1．定义 平图 G 的对偶图（dual graph）G*是这样的一个图：它们之间有如下的一一对应关系 G 的面 f G*的顶点 f* ； G 的边 e G*的边 e* 。 且 G*的顶点 f1* 与 f2* 被边 e* 连接 G 的面 f1 与 f2 被边 e 分隔。 例如，左面所示平图 G 的对偶图 G* = (V* , E*) 为 V* = {f1*，.，f5*} ， E* = {e1* = f1*f5* ， e2* =f5*f5* ，e3* = f2*f5* ，.，e8* = f2*f3*}
易见，平图G的对偶图G*是一平面图，事实上存在G*的一个平面嵌入（称为几何对偶）如下：在 G的每个面f中放置顶点，对应于G的每一边,画一条边*使它穿过c恰好一次（且不穿过G的其 它边)。例如，上例平图G的对偶图G*如右图所示。 2.定理G°一定是连通平面图。且有 e是G的环当且仅当e*是G*的制边。 e是G的制边当且仅当e*是G*的环。 有时，为方便计，把平图G的几何对偶G*当作G的对偶图。这时，若G连通，则有 G*来=(G*)*三G。 (当G不连通时，上式不一定成立)。 注意“平图G三H→G*三H”不一定成立 例如，右边二平图是同构的，但它们的对偶图并不同构。因此，对偶图的概念只对平图有意义，不能指 广到平面图上。 三、课堂小结（约5分钟） 174
1704 e1 e2 e3 e4 e5 e6 e7 f1 e8 f5 f2 f3 f4 易见，平图 G 的对偶图 G*是一平面图，事实上存在 G* 的一个平面嵌入（称为几何对偶）如下：在 G 的每个面 f 中放置顶点 f*，对应于 G 的每一边 e，画一条边 e* 使它穿过 e 恰好一次（且不穿过 G 的其 它边）。例如，上例平图 G 的对偶图 G* 如右图所示。 2．定理 G* 一定是连通平面图。且有 e 是 G 的环 当且仅当 e* 是 G* 的割边。 e 是 G 的割边当且仅当 e* 是 G* 的环。 有时，为方便计，把平图 G 的几何对偶 G* 当作 G 的对偶图。这时，若 G 连通，则有 G** = (G* )* G。 （当 G 不连通时，上式不一定成立）。 注意 “平图 G H G* H* ”不一定成立。 例如，右边二平图是同构的，但它们的对偶图并不同构。因此，对偶图的概念只对平图有意义，不能推 广到平面图上。 三、课堂小结（约 5 分钟）
离散数学教案 编号：C1703 课时安排： 2学时教学课型：理论课√实验课口习题课口实践课口其它口 题目（教学章、节或主题）： Ch17平面图及图的若色 §175图顶点的若色 §17.6地图着色与平面图的点着色 S17.7边若色 教学目的要求（分掌握、熟悉、了解三个层次）： 了解图的项点和边若色的概念，以及相关的色数概念 2. 了解四色问题的提法和现状 教学重点、难点： 1)重点：图的顶点和边者色的概念 2)难点：图的顶点和边着色的概念 教学方法： 利用黑板，CAI课件等教学 教学用具 黑板，CAI课件及其辅助设备 教学内容（注明：·重点#难点？疑点）： *一、图项点的者色（约30分钟） l.定义顶点着色(k.(Vertex)colouring) 一k种色在V(G)上的一种分配，且任二相邻（的不同）顶点不同色。 V的一个k划分(V1, ,k)使每个M(可为②)都是G的一个 独立集。 k(顶点)可着色(k.(vertex)colourable)台G有一k着色。 显然，G为k可若色→G的基础简单图为k可若色。 2.定理G为1-可着色的当且仅当G为一空图。 3。定理G为k.可着色的当且仅当G为k.部图。 4. 定理G为k可着色的则G为小可着色的(k≤j)。 5.定理对任一图G都有x≤A+1 二、地图的者色（约20分钟） 图的者色起源于四色问题：在画任何地图时，能否用4种颜色涂图中的不同区域，使得不会有两个 相邻的区域有相同的颜色。这个问题最早见于1852年10月25日德摩根致哈密尔顿的一封信中。1976 年两个美国数学家使用当时的高速计算机，共花费了1200个机时，才算解决。 1705
1705 离 散 数 学 教 案 编号：C1703 课时安排： 2 学时 教学课型：理论课√ 实验课□ 习题课□ 实践课□ 其它□ 题目（教学章、节或主题）： Ch17 平面图及图的着色 §17.5 图顶点的着色 §17.6 地图着色与平面图的点着色 §17.7 边着色 教学目的要求（分掌握、熟悉、了解三个层次）： 1． 了解图的顶点和边着色的概念，以及相关的色数概念； 2． 了解四色问题的提法和现状 教学重点、难点： 1） 重点：图的顶点和边着色的概念 2） 难点：图的顶点和边着色的概念 教学方法: 利用黑板,CAI 课件等教学. 教学用具: 黑板,CAI 课件及其辅助设备. 教学内容（注明：* 重点 # 难点 ？疑点）： *一、图顶点的着色（约 30 分钟） 1．定义 顶点着色（k-（Vertex）colouring） k 种色在 V(G)上的一种分配，且任二相邻（的不同）顶点不同色。 V 的一个 k-划分（V1，.，Vk）使每个 Vi（可为）都是 G 的一个 独立集。 k-（顶点）可着色（k-（vertex） colourable） G 有一 k-着色。 显然， G 为 k-可着色 G 的基础简单图为 k-可着色。 2．定理 G 为 1-可着色的当且仅当 G 为一空图。 3． 定理 G 为 k-可着色的当且仅当 G 为 k-部图。 4． 定理 G 为 k-可着色的则 G 为 j-可着色的（k j）。 5． 定理 对任一图 G 都有 + 1 二、地图的着色（约 20 分钟） 图的着色起源于四色问题：在画任何地图时，能否用 4 种颜色涂图中的不同区域，使得不会有两个 相邻的区域有相同的颜色。这个问题最早见于 1852 年 10 月 25 日德摩根致哈密尔顿的一封信中。1976 年两个美国数学家使用当时的高速计算机，共花费了 1200 个机时，才算解决
三、边着色（约35分钟） l.定义边者色(k-edge colouring) k种色在图G的边集上的一种分配。C是E(G)的一个k划分，即C=(E1,Ek) 边若色C是正常的当日仅当每个E都是G的 个匹配。 G为k-边可若色的(k-edge colurable):若能用k种色给G的边者色 2.定义G的边色数(edge chromatic number) 3.定理设连通图G不是奇圈，则G有一2边着色，使该二色表现于G的每个度≥2的顶点。 4.定理设C=(E1,Ek)为G的一个最优k边着色。若G中有一顶点u及色i与j,使i不表 现于u,而j在u上至少表现2次。则GEUj]中含u的分支是一奇圈。 5.定理设G为偶图，则x=△。 四、课堂小结（约5分钟
1706 三、边着色（约 35 分钟） 1．定义 边着色（k-edge colouring） k 种色在图 G 的边集上的一种分配。C 是 E(G)的一个 k-划分，即 C =（E1 ，。，Ek） 边着色 C 是正常的当且仅当每个 Ei 都是 G 的一个匹配。 G 为 k-边可着色的（k-edge colurable）：若能用 k 种色给 G 的边着色 2．定义 G 的边色数（edge chromatic number） 3．定理 设连通图 G 不是奇圈，则 G 有一 2-边着色，使该二色表现于 G 的每个度 2 的顶点。 4．定理 设 C =（E1 ，。，Ek）为 G 的一个最优 k-边着色。若 G 中有一顶点 u 及色 i 与 j，使 i 不表 现于 u，而 j 在 u 上至少表现 2 次。则 G[Ei Ej ]中含 u 的分支是一奇圈。 5．定理 设 G 为偶图，则 = 。 四、课堂小结（约 5 分钟）