天津理工大学：《离散数学》课程教学资源（PPT课件）第八章 一些特殊的图

第8章一些特殊的图

第8章 一些特殊的图

内容介绍$ 8.1二部图S8欧拉图8.2$8.3哈密顿图$8.4平面图$8.5例题分析

内容介绍 ✓§8.1 二部图 ✓§8.2 欧拉图 ✓§8.3 哈密顿图 ✓§8.4 平面图 ✓§8.5 例题分析

S8.1二部图1.定义8.1二部图若能将无向图G=的顶点集V划分成两个子集V1和V2，使得G中任何一条边的两个端点一个属于V1，另一个属于V2，则称G为二部图。V1，V2为互补顶点集G=(b)

§8.1 二部图 1.定义8.1 二部图 若能将无向图G=的顶点集V划分成两 个子集V1和V2，使得G中任何一条边的两个端点 一个属于V1，另一个属于V2，则称G为二部图。 V1，V2为互补顶点集， G= （a） （b）

S8.1二部图1.定义8.1二部图若V1中任一顶点与V2中每一个顶点均有且仅有一条边相关联，则称G为完全二部图记作：Kn,m若/V1|=n，/V2|=m，i(b)

§8.1 二部图 1.定义8.1 二部图 若V1中任一顶点与V2中每一个顶点均有且 仅有一条边相关联，则称G为完全二部图。 若|V1|=n，|V2|=m，记作：Kn，m （a） （b）

S8.1二部图2.定理8.1一个无向图G=是二部图当且仅当G中无奇数长度的回路(b)

§8.1 二部图 2.定理8.1 一个无向图G=是二部图当且仅当G 中无奇数长度的回路。 （a） （b） （c）

$8.1二部图3.定义8.2匹配极大匹配最大匹配完美匹配设G=为无向图，E*E。(1)匹配：E*中任意两条边均不相邻。(e1)e2el福(e1,e7)e3 e4[e5)e5er(e4,e6]e6

§8.1 二部图 3.定义8.2 匹配 极大匹配 最大匹配 完美匹配 设G=为无向图，E*  E。 （1）匹配：E*中任意两条边均不相邻。 e1 e2 e3 e4 e5 e6 e7 （a） {e1} {e1,e7} {e5} {e4,e6}

$8.1二部图3.定义8.2匹配极大匹配最大匹配完美匹配(2)极大匹配：在E*中再加入任何一条边就都不是匹配[e5]el(e1,e7)e3e4(e4,e6)esPe6

§8.1 二部图 3.定义8.2 匹配 极大匹配 最大匹配 完美匹配 （2）极大匹配：在E*中再加入任何一条边就都 不是匹配。 e1 e2 e3 e4 e5 e6 e7 （a） {e5} {e1,e7} {e4,e6}

$8.1二部图3.定义8.2匹配极大匹配最大匹配完美匹配(3)最大匹配：边数最多的极大匹配(4)匹配数：最大匹配中边的条数。(e1,e7)e2el[e4,e6]e3e4e5匹配数：2e7e6

§8.1 二部图 3.定义8.2 匹配 极大匹配 最大匹配 完美匹配 （3）最大匹配：边数最多的极大匹配。 （4）匹配数：最大匹配中边的条数。 e1 e2 e3 e4 e5 e6 e7 （a） {e1,e7} {e4,e6} 匹配数：2

$8.1二部图3.定义8.2匹配极大匹配最大匹配完美匹配(5)饱和点：与匹配关联的顶点。(6)完美匹配：G中每个顶点都是M的饱和点。?[e1)e6eele[e1,e4,e7)(e1,e7)(e2,e4,e6]e3e4[e5]eseP[e4,e6]e6-e4(b)

§8.1 二部图 3.定义8.2 匹配 极大匹配 最大匹配 完美匹配 （5）饱和点：与匹配关联的顶点。 （6）完美匹配：G中每个顶点都是M的饱和点。 e1 e2 e3 e4 e5 e6 e7 （a） e1 e2 e3 e4 e5 e6 e7 （b） {e1} {e1,e7} {e5} {e4,e6} {e1,e4,e7} {e2,e4,e6}

$8.2欧拉图1.比较几个图(d)(b)边只能画一次，能一笔画出的图(c)(d)

§8.2 欧拉图 1.比较几个图 （a） （b） （c） （d） 边只能画一次，能一笔画出的图 （c）（d）