第6 章?一些特殊的图内容介绍Y$6.1二部图中V$6.2欧拉图Y36.3哈密顿图V$6.4平面图V86.5例题分析$6.1二部图1、定义6.1二部图若能将无向图G=<V，E>的顶点集V划分成两个子集V1和V2，使得G中任何一条边的两个端点一个属于V1，另一个属于V2，则称G为二部图。V1，V2为互补顶点集，G=<V1，V2，E>。(b)(a)若V1中任一项点与V2中每一个顶点均有且仅有一条边相关联，则称G为完全二部图。若/V1/=n，/V2/=m，记作：Kn，m。2、定理6.1一个无向图G=<V，E>是二部图当且仅当G中无奇数长度的回路。(b)(c)(a)3、定义6.2匹配极大匹配最大匹配完美匹配设G=<V，E>为无向图，E*E。（1）匹配：E*中任意两条边均不相邻
第 6 章 一些特殊的图 内容介绍 ✓ §6.1 二部图 ✓ §6.2 欧拉图 ✓ §6.3 哈密顿图 ✓ §6.4 平面图 ✓ §6.5 例题分析 §6.1 二部图 1、定义 6.1 二部图 若能将无向图G=<V，E>的顶点集V划分成两个子集V1和V2，使得G中任何 一条边的两个端点一个属于V1，另一个属于V2，则称G为二部图。V1，V2为互 补顶点集， G=<V1， V2， E>。 若V1中任一顶点与V2中每一个顶点均有且仅有一条边相关联，则称G为完 全二部图。 若|V1|=n，|V2|=m，记作：Kn，m。 2、定理 6.1 一个无向图G=<V，E>是二部图当且仅当G中无奇数长度的回路。 3、定义 6.2 匹配 极大匹配 最大匹配 完美匹配 设G=<V，E>为无向图，E* E。 （1）匹配：E*中任意两条边均不相邻
e2ele3 e4e5e7e6Q(a)(a)图中匹配是：(el)、(el，e7)、(e5)、{e4，e6)。（2）极大匹配：在E*中再加入任何一条边就都不是匹配（a）图中的极大匹配是：（e5)、（el，e7)、(e4，e6)。（3）最大匹配：边数最多的极大匹配。（b）图中极大匹配el，e4，e7)、e2，e4，e6)。（4）匹配数：最大匹配中边的条数。（5）饱和点：与匹配关联的顶点。（6）完美匹配：G中每个顶点都是M的饱和点。elQ(e1)e6e2(e1,e4,e7)e7(e1,e7)[e2,e4,e6][e5]-e5e4-[e4,e6]e6.(a)(b)$6.2欧拉图1、比较几个图-(a)(b)(c)(d)边只能画一次，能一笔画出的图：（c）、（d)。2、定义6.4欧拉通路（回路）欧拉图（1）欧拉通路（回路）：经过图中每条边一次且仅一次并且行遍图中每个顶
（a）图中匹配是：{e1}、{e1，e7}、{e5}、{e4，e6}。 （2）极大匹配：在E*中再加入任何一条边就都不是匹配。 （a）图中的极大匹配是：{e5}、{e1，e7}、{e4，e6}。 （3）最大匹配：边数最多的极大匹配。 （b）图中极大匹配{e1，e4，e7}、{e2，e4，e6}。 （4）匹配数：最大匹配中边的条数。 （5）饱和点：与匹配关联的顶点。 （6）完美匹配：G中每个顶点都是M的饱和点。 §6.2 欧拉图 1、比较几个图 边只能画一次，能一笔画出的图：（c）、（d）。 2、定义 6.4 欧拉通路（回路） 欧拉图 （1）欧拉通路（回路）：经过图中每条边一次且仅一次并且行遍图中每个顶
点的通路（回路）。（2）欧拉图：存在欧拉回路的图。(a)(b)(c)3、定理6.4（1）无向图G具有欧拉回路，当且仅当G是连通图且无奇度顶点。（2）无向图G具有欧拉通路，但无欧拉回路，当且仅当G是连通图且恰好有两个奇度顶点。这两个奇度顶点时每条欧拉通路的端点。4、定理6.5（1）有向图D具有欧拉回路，当且仅当D是连通图且每个顶点的入度等于出度。（2）有向图D具有欧拉通路，但无欧拉回路，当且仅当D是连通图，且除了两个顶点外，其他顶点的入度等于出度。86.3哈密顿图1、定义6.5哈密顿图哈密顿通路（回路）：经过图中每个顶点一次且仅一次的通路（回路）。哈密顿图：存在哈密顿回路的图。?(b)(a)(c)$6.4平面图1、定义6.6平面图平面嵌入平面图：一个图G如果能以这样的方式画在平面上：除顶点处外没有边交叉出现。画出的没有边交叉出现的图称为G的一个平面嵌入
点的通路（回路）。 （2）欧拉图：存在欧拉回路的图。 3、定理 6.4 （1）无向图G具有欧拉回路，当且仅当G是连通图且无奇度顶点。 （2）无向图G具有欧拉通路，但无欧拉回路，当且仅当G是连通图且恰好有 两个奇度顶点。这两个奇度顶点时每条欧拉通路的端点。 4、定理 6.5 （1）有向图D具有欧拉回路，当且仅当D是连通图且每个顶点的入度等于出 度。 （2）有向图D具有欧拉通路，但无欧拉回路，当且仅当D是连通图，且除了 两个顶点外，其他顶点的入度等于出度。 §6.3 哈密顿图 1、定义 6.5 哈密顿图 哈密顿通路（回路）：经过图中每个顶点一次且仅一次的通路（回路）。 哈密顿图：存在哈密顿回路的图。 §6.4 平面图 1、定义 6.6 平面图 平面嵌入 平面图：一个图G如果能以这样的方式画在平面上：除顶点处外没有边交叉 出现。 画出的没有边交叉出现的图称为 G的一个平面嵌入
(b)(a)(d)（b）是（a）的一个平面嵌入。（d）是（c）交叉边最少的一种画法，所以，（c）不是平面图。2、定义6.7面无限面有限面（1）面：G是一个平面图，G的边将G所在的平面划分成若干个区域，每个区域称为G的一个面。（2）无限面：面积无限的区域，记作R0。（3）有限面：面积有限的区域。（4）边界：包围每个面的所有边构成的回路。（5）次数：边界的长度，记作deg(R)。41V.CRoRRRVNVsVe(b)(a)3、定理6.9面无限面有限面在一个平面图G中，所有面的次数之和都等于边数m的2倍，即：-Zdeg（R,)=2mi=1其中，r为面数
（b）是（a）的一个平面嵌入。（d）是（c）交叉边最少的一种画法，所以， （c）不是平面图。 2、定义 6.7 面 无限面 有限面 （1）面：G是一个平面图，G的边将G所在的平面划分成若干个区域，每个 区域称为G的一个面。 （2）无限面：面积无限的区域，记作R0。 （3）有限面：面积有限的区域。 （4）边界：包围每个面的所有边构成的回路。 （5）次数：边界的长度，记作deg(R)。 3、定理 6.9 面 无限面 有限面 在一个平面图G中，所有面的次数之和都等于边数m的2倍，即： 其中，r为面数
4、定义6.8极大平面图极小非平面图设G为一个简单平面图，如果在G中任意不相邻的两个顶点之间再加一条边，所得图为非平面图，称G为极大平面图。若在非平面图G中任意删除一条边，所得图为平面图，则称G为极小非平面图。$6.5题例分析1、例6.1在下图所示的各图中，找出欧拉图和哈密顿图答案：（1）欧拉图：（d）abcdefgebjghija(2）哈密顿图：（b）、（c）、（d）(b):abcdefa(c):abcdhgfea(d):abcdefghijaaaS(a)(b)RCdd3gi(d)(c)doOh-g8T2、例6.3在下图所示的各图中，找出二部图及二部图中存在完美匹配的图和匹配数。答案：（1）二部图：（a）、（c）（2）完美匹配：（c）
4、定义 6.8 极大平面图 极小非平面图 设G为一个简单平面图，如果在G中任意不相邻的两个顶点之间再加一条边， 所得图为非平面图，称G为极大平面图。 若在非平面图G中任意删除一条边，所得图为平面图，则称G为极小非平面 图。 §6.5 题例分析 1、例 6.1 在下图所示的各图中，找出欧拉图和哈密顿图 。 答案： （1）欧拉图：（d） abcdefgebjghija （2）哈密顿图：（b）、（c）、（d） （b）：abcdefa （c）：abcdhgfea （d）：abcdefghija 2、例 6.3 在下图所示的各图中，找出二部图及二部图中存在完美匹配的图和匹配数。 答案： （1）二部图：（a）、（c） （2）完美匹配：（c）