08一些特殊的图-课件（PPT-精）.pptVIP

离散数学 * 离散数学 第八章 一些特殊的图 §8.1 二部图 §8.2 欧拉图 §8.3 哈密尔顿图 §8.4 平面图 §8.5 树 离散数学 二部图(偶图)：若无向图G = V, E的顶点集V能划 分成两个子集V1和V2，使得G中任何一条边的 两个端点一个属于V1，另一个属于V2，则称G 为二部图(偶图)。V1,V2称为互补顶点子集。 §8.1 二部图 完全二部图(完全偶图)：若V1中任一顶点与V2中每个 顶点均有且仅有一条边相关联，则称G为完全 二部图(完全偶图)。 若|V1| = n，|V2| = m，则记完全二部图G为Kn, m 离散数学 二部图（续） K2, 3 K3, 3 一个无向图G = V, E是二部图当且仅当 G中无奇数长度的回路。 二部图 判定定理 离散数学 二部图（续） 例1：判断下列图是否为二部图。 v4 v3 v2 v1 v5 v6 v7 v8 同构于 v4 v3 v2 v1 v5 v6 同构于 v6 v4 v3 v2 v1 v5 v7 v8 v4 v3 v2 v1 v5 v6 §8.2 欧拉图 哥尼斯堡七桥问题 离散数学 欧拉通路(欧拉回路)：经过图中每条边一次且仅一 次并且行遍每个顶点的通路(回路)， 称为欧拉通路(欧拉回路)。 欧拉图：存在欧拉回路的图。 离散数学 欧拉图（续） (1) 无向图G具有欧拉通路当且仅当G是连通图且有 零个或两个奇数度顶点。 欧拉图的判定定理： (2) 无向图G是欧拉图(具有欧拉回路)当且仅当G是 连通图且所有顶点的度数全为偶数。 离散数学 欧拉图（续） 欧拉图的判定定理： (4) 有向图D是欧拉图(具有欧拉回路)当且仅当D是 连通图，且所有顶点的入度等于出度。 (3) 有向图D具有欧拉通路当且仅当D是连通图，且 除了两个顶点外，其余顶点的入度均等于出度。 这两个特殊的顶点中，一个顶点的入度比出度 大1，另一个顶点的出度比入度大1。 离散数学 欧拉图（续） 例2：判断下列图是否为欧拉图。 f d b a e c g h i j d b a e c d b a e c 是欧拉图 不是欧拉图，但有欧拉通路 是欧拉图 离散数学 §8.3 哈密尔顿图 哈密尔顿通路(哈密尔顿回路)：经过图中每个顶点 一次且仅一次的通路(回路)， 称为哈密尔顿通路(哈密尔顿回路)。 哈密尔顿图：存在哈密尔顿回路的图。 d b a e c d b a e c d b a e c f 离散数学 设G是n(n ? 3)阶无向简单图， (1)若G中任何一对不相邻的顶点的度数之和 都大于等于n -1，则G中存在哈密尔顿通路。 (2)若G中任何一对不相邻的顶点的度数之和 都大于等于n，则G是哈密尔顿图。 哈密尔顿图 设无向图G = V, E是哈密尔顿图，V1是V的 任意非空子集，则p(G –V1) ? |V1|。 其中，p(G –V1)为从G中删除V1 (删除V1中各 顶点及其关联的边)后所得子图的连通分支数。 必要条件 充分条件 离散数学 哈密尔顿图 例3：判断下列图是否为哈密尔顿图。 d b a e c f V1 ={a} p(G –V1)=2 |V1|=1 不满足必要条件； V1 ={a，b} p(G –V1)=3 |V1|=2 不满足必要条件； a b 离散数学 §8.4 平面图 平面图：图G若能够以除顶点外没有边交叉的方式 画在平面上，则称G为平面图。 K5 K3,3 一、平面图的基本概念及性质 画出的没有边交叉的图称为G的一个平面嵌入。 离散数学 一、平面图的基本概念及性质（续） 面：设G是一个连通的平面图(G的某个平面嵌入)， G的边将G所在的平面划分成若干个区域， 每个区域称为的一个面。 其中面积无限的区域称为无限面(或外部面)，记R0， 面积有限的区域称为有限面(或内部面)。 包围每个面的所有边所构成的回路称为该面的边界。边界的长度称为该面的次数，R的次数记为deg(R)。 对于含k(k ? 2)个连通分支的非连通的平面图，其无限面R0的边界则由k个回路围成。 离散数学 一、平面图的基本概念及性质（续） v1 v2 v4 v3 v5 v6 R0 R1 R2 v1 v2 v4 v3 v5 R0 R1 R2 R3 v1 v2 v4 v3 v5 R0 R1 R2 v6 v7 deg(R1) = 3 deg(R1) = 4