08一些特殊的图.ppt

第八章一些特殊的图
§ 二部图
§ 欧拉图
§ 哈密尔顿图
§ 平面图
§ 树
4/26/2018
1
离散数学
二部图(偶图):若无向图G = <V, E>的顶点集V能划
分成两个子集V1和V2,使得G中任何一条边的
两个端点一个属于V1,另一个属于V2,则称G
为二部图(偶图)。V1,V2称为互补顶点子集。
§ 二部图
完全二部图(完全偶图):若V1中任一顶点与V2中每个
顶点均有且仅有一条边相关联,则称G为完全
二部图(完全偶图)。
若|V1| = n,|V2| = m,则记完全二部图G为Kn, m
4/26/2018
2
离散数学
二部图(续)
K2, 3
K3, 3
一个无向图G = <V, E>是二部图当且仅当
G中无奇数长度的回路。
二部图
判定定理
4/26/2018
3
离散数学
二部图(续)
例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
4/26/2018
4
离散数学
§ 欧拉图
哥尼斯堡七桥问题
4/26/2018
5
离散数学
欧拉通路(欧拉回路):经过图中每条边一次且仅一
次并且行遍每个顶点的通路(回路),
称为欧拉通路(欧拉回路)。
欧拉图:存在欧拉回路的图。
4/26/2018
6
离散数学
欧拉图(续)
(1) 无向图G具有欧拉通路当且仅当G是连通图且有
零个或两个奇数度顶点。
欧拉图的判定定理:
(2) 无向图G是欧拉图(具有欧拉回路)当且仅当G是
连通图且所有顶点的度数全为偶数。
4/26/2018
7
离散数学
欧拉图(续)
欧拉图的判定定理:
(4) 有向图D是欧拉图(具有欧拉回路)当且仅当D是
连通图,且所有顶点的入度等于出度。
(3) 有向图D具有欧拉通路当且仅当D是连通图,且
除了两个顶点外,其余顶点的入度均等于出度。
这两个特殊的顶点中,一个顶点的入度比出度
大1,另一个顶点的出度比入度大1。
4/26/2018
8
离散数学
欧拉图(续)
例2:判断下列图是否为欧拉图。
f
d
b
a
e
c
g
h
i
j
d
b
a
e
c
d
b
a
e
c
是欧拉图
不是欧拉图,但有欧拉通路
是欧拉图
4/26/2018
9
离散数学
§ 哈密尔顿图
哈密尔顿通路(哈密尔顿回路):经过图中每个顶点
一次且仅一次的通路(回路),
称为哈密尔顿通路(哈密尔顿回路)。
哈密尔顿图:存在哈密尔顿回路的图。
d
b
a
e
c
d
b
a
e
c
d
b
a
e
c
f
4/26/2018
10
离散数学