离散数学第八章.ppt

第八章 一些特殊的图 第一节 二部图 内容： 二部图。重点： 二部图的定义及判定。本节讨论的图均为无向图。一、二部图的定义。1、若存在无向图 的顶点集 的一个划分， ， ，使得 中任何一条边的两个端点分别在 和 中，则称为 二部图 (或 偶图 )。其中 称互补顶点子集， 记为。一、二部图的定义。2、完全二部图 (或完全偶图 )。若 中任一顶点与 中每一顶点均有且只有一条边相关联，则称此二部图 为 完全二部图 (或 完全偶图 )。若 ，则记完全二部图为， 。例 1、二部图完全二部图二部图例 1、完全二部图二部图二、判定定理。一个无向图 是二部图当且仅当中无奇数长度的回路。例 2、 判断以下是否二部图。(1)二部图图 (1)中所有的回路长度均为偶数。(思考，求其互补顶点子集 )例 2、 判断以下是否二部图。二部图例 1同构以上二图均为 。例 2、 判断以下是否二部图。例 1同构二部图以上二图均为 。