离散数学导论(盘) 教学课件 作者 王元元 张桂芸 第九章演示文稿-支持高清浏览

第

九

章特

殊

图第九章特殊图9.1二分

图9.2平面

图9.3树第九章

特

殊

图二

分

图二分图的基本概念匹配第九章

特

殊

图平

面

图平面图的基本概念欧拉公式和库拉托夫斯基定理着色问题第九章

特

殊

图树树的基本概念生成树根树第九章

特

殊

图二

分

图二分图的基本概念定义9.1无向图G=<V，E，>称为二分图（bipartitegraph），如果有非空集合X，Y使X∪Y=V，X∩Y

=

，且对每一e

E，

(e)

=

(x,

y)，x

X，y此时常用<X，E，Y>表示二分图G。若对X中任一x及Y中任一y恰有一边e

E，使

(e)

=

(x,

y),

则称G为完二分图（complete

bipartite

graph）。当

X

=

mn时，完全二分图G记为Km,n。第九章

特

殊

图二

分

图二分图的基本概念√定理9.1无向图G为二分图的充分必要条件是，

G至少有两个顶点,且其所有回路的长度均为偶数。第九章

特

殊

图9.1

二

分

图9.1.2

二分图的基本概念定义9.2设G

=

<X，E，Y>为二分图，M

E。称M为G的一个匹配（matching），如果M中任何两条边都没有公共端点。G的所有匹配中边数最多的匹配称为最大匹配（maximal

matching）。如果X(Y)中任一顶点均为匹配M中边的端点，那么称M为X(Y)-完全匹配(perfectmatching)。若M既是X-完全匹配又是Y-完全匹配，则称M为G的完全匹配。第九章

特

殊

图9.1

二

分

图9.1.2

二分图的基本概念定义9.3设G=<X，E，Y>，M为G的一个匹配。M中边的端点称为M-顶点，其它顶点称为非M-顶点。G中vk到vl的通路P称为交替链，如果P的起点vk和终点vl为非M-顶点，而其边的序列中非匹配边与匹配边交替出现（从而首尾两边必为非匹配边，除顶点vk，vl以外各顶点均为M-顶点）。特别地，当一边（v,v‘）两端点均为非M-顶点，通路（v,v"）亦称为交替链。第九章

特

殊

图9.1

二

分

图9.1.2

二分图的基本概念√定理9.2设图G

=

<X，E，Y>。G有X-完全匹配的充分必要条件是：对每一S

X有N(S)

≥

S此定理是霍尔（Hall）于1935年证明的，通常称为霍尔婚姻著名定理。第九章

特

殊

图平

面

图平面图的基本概念定义9.4无向图G称为平面图（planar

graph），如果G可以在一个平面上图示出来，而使各边仅在顶点处相交。否则称G为非平面图。第九章

特

殊

图平

面

图平面图的基本概念定义9.5平面连通图中各边所界定的区域称为平面图的

面（regions）。有界的区域称为有界面，无界的区域称为无界面。界定各面的闭的拟路径称为面的边界（boundary），它的长度称为面的度（degree）第九章

特

殊

图平

面

图平面图的基本概念定义9.6称平面简单图G是极大平面图（maximal

planargraph）,如果在G中添加任一边（它不是环，也不是其他边的平行边）后所得的图均非平面图。√定理9.3极大平面图所有有界面都是三度的面，无界面也是三度的。即所有面的边界均为K3

。第九章

特

殊

图平

面

图平面图的基本概念√定理9.4顶点个数n≥4的极大平面图中，顶点的最小度数不少于3。第九章

特

殊

图9.2

平

面

图9.2.2

欧拉公式和库拉托夫斯基定理√定理9.5设G为一平面连通图，n为其顶点数，m为其边数，r为其面数，那么n

–

m

+

r

=

2第九章

特

殊

图9.2

平

面

图9.2.2

欧拉公式和库拉托夫斯基定理√定理9.6如果平面连通图G的每个面的边界都具有长度l(l≥3)，那么其中m为G的边数，n为G的顶点数。第九章

特

殊

图9.2

平

面

图9.2.2

欧拉公式和库拉托夫斯基定理√定理9.7设G为一平面连通简单图，其顶点数n≥3，其边数为m，那么

m

≤

3n

–

6√定理9.8设G为一平面简单连通图，其顶点数n≥4，边数为m，且G不以K3为其子图，那么m

≤

2n

–

4第九章

特

殊

图9.2

平

面

图9.2.2

欧拉公式和库拉托夫斯基定理√定理9.9顶点数n不少于4的平面连通简单图G，至少有一个顶点的度数不大于5。√定理9.10√（库拉托夫斯基定理）图G是平面图，当且仅当对G或G的子图作任何同胚操作后所得图均不以K5及K3,3为子图。第九章

特

殊

图9.2

平

面

图9.2.3

着色问题定义9.7对连通平面图G实施下列步骤所得到的图

G*称为G的对偶图（dual

of

graph）：在G的每一个面ri的内部作一个G*的顶点v。若G中面ri与ri有公共边界，那么过边界的每一边ek作关联v与v的一条边e。e与G*的其它边不相交。当ek为面ri的边界而非ri与其它面的公共边界时作v的一条环与ek相交（且仅交于一处）。所作的环不与G*的边相交。第九章

特

殊

图9.2

平

面

图9.2.3

着色问题定义9.8无自环图G称为可k-着色的（k-chromatic），如果可用k种颜色给G的所有顶点着色，使每个顶点着一种颜色，而同一边的两个端点着不同颜色。√定理9.11任何平面图都是可5-着色的。第九章

特

殊

图树树的基本概念定义9.9连通无回路的无向图称为无向树，简称为树（tree）。树中的悬挂点又称为树叶（leave），其它结点称为分支点（branched

node）。单一孤立结点称为空树（null

tree）。诸连通分支均为树的图称为森林（forest），树也是森林第九章

特

殊

图树树的基本概念√定理9.12树和森林都是可2-着色的，从而都是二分图。√定理9.13√

树和森林都是平面图，其面数为

1。第九章

特

殊

图树树的基本概念√定理9.14设图T为一树，其顶点数、边数分别是n,

m,

那么

n

–

m

=

1

或

m

=

n

–

1√定理9.15任何树都至少有两片叶。第九章

特

殊

图树树的基本概念√定理9.16命题“（n，m）图T为树”与下列5命题中的每一命题等价：（1）T无回路且m=n–1。（2）T连通且m=n–1。T无回路，但任意添加边时，T中产生 唯一的一条回路。T连通，但删去任一边时便不再连通（T的每一边均为割边）。任意两个不同顶点之间有且仅有一条通路。第九章

特

殊

图9.3

树9.3.2

生成树定义9.10图T称为无向图G的生成树（spanning

tree）如果T为G的生成子图且T为树。√定理9.17√

任一连通图G都至少有一棵生成树。第第九九章章特特殊殊图图9.93.3.3

树树9.3.2

生成树√定理9.18设G为连通无向图，那么G的任一回路与任一生成树T的关于G的补

G–T，至少有一条公共边。√定理9.19设G为连通无向图，那么G的任一割集与任一生成树至少有一条公共边。第第九九章章

特特

殊殊

图图99..33

树树9.3.2

生成树定义9.11设T为图G的生成树，称T中的边为树枝（branch）称G–T中的边为弦（chord）。对每一树枝t，T–t分两个连通分支T1，T2，那么t及两端点分别在T1，T2中的弦组成G的一个割集，它被称为枝t-割集（t-cut

set而每一条弦e与T中的通路构成一回路，它被称为弦e-路（e-circuit）。第九章

特

殊

图9.3

树9.3.2

生成树√定理9.20在连通无向图G中，任一回路与任一割集均有偶数条公共边。第九章

特

殊

图9.3

树9.3.2

生成树√定理9.21设G为一连通无向图，T是G的生成树，

S={e1,e2,e3,…,ek}为枝e1-割集，那么e1必在弦ei-回路中（i=2，3,…，不在其它弦e-回路中。（e1与弦ei-回路恰有两条公共边

e1和ei，而e1与其它弦e-回路无公共边。）第九章

特

殊

图9.3

树9.3.2

生成树√定理9.22设G为一连通无向图，T是G的生成树，

C=（e1,e2,…,ek）为弦e1-回路，那么e1必定在枝e1-割集中（i=2，3,…，k），不在其它任何枝e1-割集中。第九章

特

殊

图9.3

树9.3.2

生成树√定理9.23设G是连通边赋权图，且各边的权互不相等。若C是G中的一条回路，那么C上权最大的边e必定不在G的最小生成树上。第九章

特

殊

图树根树定义9.12树T称为根树（rootedtree），如果（1）T为一孤立结点v0

。v0又被称为T的树根。（2）T1，T2,…,Tk为以v1，v2,…，vk为树根的根树，T由T1，T2,…,Tk及与v1，v2,…，vk相邻的结点v0所组成。v0称为T的树根。第九章

特

殊

图9.3

树9.3.3 根树定义9.13在定义9.12中，（1）v1，v2,…，vk称为v0的儿子，v0称为它们的父亲。vi，vj同为一顶点v的儿子时，称它们为兄弟。顶点间的父子关系的传递闭包称为顶点间的祖孙关系。即当vi为vi+1

(i=1,2,…,l-1)的父亲时，v1是vl的祖先，vl为v1的子孙。根树T自身及以它的树根的子孙为根的根树（T的子图），均称为T的子树（subtree），后者又称为T的真子树。第九章

特

殊

图9.3

树9.3.3 根树定义9.14除了树叶外，每个结点都有两个儿子的根树称为完全2元树（binary

tree）。√定理9.24√

完全2元树的顶点个数n必定是奇数。第九章

特

殊

图9.3

树9.3.3 根树√定理9.25√完全二元树中叶的数目其中n为树的顶点数。第九章

特

殊

图9.3

树9.3.3 根树√定理9.26完全二