第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，E>的顶点集V划分成两个子集V1和V2，使得G中任何一条边的两个端点一个属于V1，另一个属于V2，则称G为二部图。V1，V2为互补顶点集G=<V1, V2, E>(b)
§8.1 二部图 1.定义8.1 二部图 若能将无向图G=<V，E>的顶点集V划分成两 个子集V1和V2，使得G中任何一条边的两个端点 一个属于V1，另一个属于V2，则称G为二部图。 V1，V2为互补顶点集， G=<V1， V2， E> （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=<V,，E>是二部图当且仅当G中无奇数长度的回路(b)
§8.1 二部图 2.定理8.1 一个无向图G=<V，E>是二部图当且仅当G 中无奇数长度的回路。 （a） （b） （c）