河北工业大学计算机科学技术与软件学院离散数学
Discrete Mathematics
郭永芳
guoyongfang.2006@yahoo.com.cn
Guoyongfang.2006@yahoo.com.cn
一、图定义 一个 图 是一个三元组 <V(G),E(G),φ G>,简记为
G＝ <V,E>，
7-1 图的基本概念其中：
1) V＝ {v1,v2,v3,…,vn}是一个非空集合,vi(i＝
1,2,3,…,n)称为 结点,简称 点,V为 结点集 ；
2) E＝ {e1,e2,e3,…,em}是一个有限的集合,ei(i＝
1,2,3,…,m)称为 边,E为 边集,E中的每个元素都有 V
中的结点对（有序偶或无序偶）与之对应。
Guoyongfang.2006@yahoo.com.cn
图的术语
若边 e与结点无序偶 (u,v)相对应，则称边 e为 无向边,记为 e＝ (u,v)，这时称 u,v是边 e的两个 端点 ；
2) 若边 e与 结点 有偶 <u,v>相对应,则称边 e为 有向边
(或 弧 ),记为 e＝ <u,v>,这时称 u是边 e的 始点 (或弧尾 ).v是边 e的 终点 (或 弧头 ),统称为 e的 端点 ；
3) 在一个图中,关联结点 vi和 vj的边 e,无论是有向的还是无向的,均称边 e与结点 vI和 vj相关联,而 vi和
vj称为 邻接点,否则称为 不邻接的 ；
Guoyongfang.2006@yahoo.com.cn
续：
续：
4) 关联于同一个结点的两条边称为 邻接边 ；
5) 图中关联同一个结点的边称为 自回路 (或 环 )；
6) 图中不与任何结点相邻接的结点称为 孤立结点 ；
7) 仅由孤立结点组成的图称为 零图 ；
8) 仅含一个结点的零图称为 平凡图 ；
9) 含有 n个结点,m条边的图称为 (n,m)图 ；
Guoyongfang.2006@yahoo.com.cn
续：续：
每条边都是无向边的图称为 无向图 ；
每条边都是有向边的图称为 有向图 ；
有些边是无向边,而另一些是有向边的图称为 混合图 。
在有向图中,两个结点间 (包括结点自身间 )若有同始点和同终点的几条边,则这几条边称为 平行边,在无向图中,
两个结点间 (包括结点自身间 )若有几条边,则这几条边称为 平行边,两结点 vi,vj间相互平行的边的条数称为边 (vi，
vj)或 <vi,vj>的 重数 ；
Guoyongfang.2006@yahoo.com.cn
续：
14)含有平行边的图称为 多重图 。 非多重图称为 线图 ；无环和平行边的图称为 简单图 。
Guoyongfang.2006@yahoo.com.cn
(a)
例：
(b)
(c) (d)
例：
Guoyongfang.2006@yahoo.com.cn
二、度数定义 在无向图 G＝ <V,E>中，与结点 v(v?V)关联的边的条数，
称为该结点的 度数,记为 deg(v)；
二、度数定义 在有向图 G＝ <V,E>中,以结点 v(v?V)为始点引出的边的条数,称为该结点的 引出度数,简称 出度,记为 deg+(v)；
以结点 v(v?V)为终点引入的边的条数,称为该结点的 引入度数,简称 入度,记为 deg-(v)；而结点的出度和入度之和 称 为 该 结 点 的 度数,记为 deg(v),即 deg(v) ＝
deg+(v)+deg-(v)；
δ(G)最小度,Δ(G)最大度定义 在图 G＝ <V,E>中,对任意结点 v?V,若度数 deg(v)为奇数,则称此结点为 奇度数结点,若度数 deg(v)为偶数,则称此结点为 偶度数结点 。
Guoyongfang.2006@yahoo.com.cn
例：
deg(v1)＝ 3,deg+(v1)＝ 2,deg-(v1)＝ 1；
deg(v2)＝ 3,deg+(v2)＝ 2,deg-(v2)＝ 1；
deg(v3)＝ 5,deg+(v3)＝ 2,deg-(v3)＝ 3；
deg(v4)＝ deg+(v4)＝ deg-(v4)＝ 0；
deg(v5)＝ 1,deg+(v5)＝ 0,deg-(v5)＝ 1；
例：
Guoyongfang.2006@yahoo.com.cn
定理定理
1.在无向图 G＝ <V,E>中,则所有结点的度数的总和等于边数的两倍,即：；m2)vd e g (
Vv
，m)v(d e g)v(d e g
VvVv
2,在有向图 G＝ <V,E>中，则所有结点的出度之和等于所有结点的入度之和，所有结点的度数的总和等于边数的两倍，即：
。m2)v(d e g)v(d e g)vd e g (
VvVvVv
Guoyongfang.2006@yahoo.com.cn
定理定理 在图 G＝ <V,E>中，其 V＝ {v1,v2,v3,…,vn},E＝
{e1,e2,……,em}，度数为奇数的结点个数为偶数。
证明 V1＝ {v|v?V且 deg(v)＝奇数 },V2＝ {v|v?V且
deg(v)＝偶数 }。显然,V1∩V 2＝ Φ，且 V1∪V 2＝ V，于是有：
。m2)vd e g ()vd e g ()vd e g (
21 VvVvVv
由于上式中的 2m和偶度数结点度数之和均为偶数，因而也为偶数。于是 |V1|为偶数 (因为 V1中的结点 v之 deg(v)
都为奇数 )，即奇度数的结点个数为偶数。■
Guoyongfang.2006@yahoo.com.cn
三、完全图定义 在图 G＝ <V,E>中，若所有结点的度数均有相同度数 d，则称此图为 d次正则图。
定义 一个 (n,m)(n?2)的简单无向图，若它为 n-1次正则图，则称该 (n,m)图为 无向简单完全图,简称 完全图,记为 Kn。
有向完全图定理 设无向完全图 G有 n个顶点，则 G有 n(n-1)/2条边。
Guoyongfang.2006@yahoo.com.cn
例：
例,如图 (a),(b),(c),(d)所示，它们分别是无向的简单完全图 K3,K4,K5和有向的简单完全图 K3。
Guoyongfang.2006@yahoo.com.cn
定义 设有图 G＝ <V,E>和图 G1＝ <V1,E1>，若 G和 G1满足
：
若 V1?V,E1?E，则称 G1是 G的 子图,记为 G1?G；
若 G1?G，且 G1?G(即 V1?V或 E1?E)，则称 G1
是 G的 真子图,记为 G1?G；
四、子图和补图
Guoyongfang.2006@yahoo.com.cn
定义 若 V1＝ V,E1?E，则称 G1是 G的 生成子图,记为 G1?G；
定义 设 G＝ <V,E>为具有 n个结点的简单图,从完全图 Kn中删去 G中的所有的边而得到的图称为 G
的 补图 (或 G的 补 ),记为 。
四、子图和补图
G
Guoyongfang.2006@yahoo.com.cn
定义 Ｇ＝ <Ｖ,Ｅ >是图,Ｇ ’ ＝ <Ｖ ’,Ε ’>是
Ｇ的子图,Ｅ,＝Ｅ－Ｅ ’,Ｖ,是Ｅ,中边所关联的所有顶点集合,则Ｇ,＝ <Ｖ,,Ｅ,>称为
Ｇ ’ 关于Ｇ的 相对补图 。
关于完全图的子图的补图称为此子图的绝对补图 。
相对补图
Guoyongfang.2006@yahoo.com.cn
例：
例,在下图中，给出了图 G以及它的真子图 G’和生成子图 G’’。
Guoyongfang.2006@yahoo.com.cn
例：
例,在下图 (a),(b),(c),(d)中,(a)与 (b)
是互为补图； (c)和 (d)是互为补图。
Guoyongfang.2006@yahoo.com.cn
7-2 路与回路一、路定义 给定图 G=〈 V,E〉,设 v0,v1,…,vn∈ V,e1，
e2,…,en∈ E,其中 ei是关联结点 vi-1,vi的边,交替序列 v0e1v1e2… envn称为联结 v0到 vn的路 。
v0,vn分别为该路的起点和终点,统称为路的 端点 。
路中边的条数称为该 路的长度 。
此时,若 v0＝ vn,则该路称为 回路 。
Guoyongfang.2006@yahoo.com.cn
若路中所有边全不相同，则称此路为一条 迹 ；
若路中所有结点全不相同，则称此路为 通路 。
若回路中除 v0＝ vn以外所有结点全不相同，则称此回路 圈。 （闭的通路）
在简单图中一条路 v0e1v1e2… envn，由它的结点序列 v0v1 … vn确定,所以简单图的路,由可由其结点序列 [v0v1 … vn]表示。在有向图中,结点数大于 1的一条路可由边序列 [e1e2 … en ]表示。
续：
Guoyongfang.2006@yahoo.com.cn
定理定理 在一个具有 n个结点的图中，如果从结点 vj到结点 vk存在一条路，则从结点 vj到结点 vk必 存在一条不多于 n-1条边的路。
证明 如果从结点 vj到结点 vk存在一条路,则该路上的结点序列是 [vj… vi… vk],如果在这路上有 l条边,
则序列中必有 l+1个结点,若 l>n-1,则必有结点 vs，
它 在 序 列 中 不 止 一 次 出 现,即 必 有 序 列
[vj… vs… vs… vk],在路中去掉从 vs到 vs的这些边,仍然得到一条从结点 vj到结点 vk的路,但此路比原来的路的边数要少 。 如此重复进行下去,必得到一条从结点 vj到结点 vk不多于 n-1条边的路 。
Guoyongfang.2006@yahoo.com.cn
定理推论 G中，如果从结点 vj到结点 vk
存在一条路，则必存在一条从 vj到 vk而 长度小于 n的通路。
Guoyongfang.2006@yahoo.com.cn
二、无向图的连通性定义 设 G＝ <V,E>是一个图，对 vi,vj?V，从 vi到 vj
如存在一条 路，则称 结点 vi和 vj是连通的 。
定义 设 G＝ <V,E>是一个无向图，若 G中任意两个结点之间都是连通的，则称该无向图 G是一个 无向连通图,否则，则称 G是一个 非连通图 (或 分离图 )。
定义 设 G＝ <V,E>是一个无向图，该无向图 G中的每个连通的划分块称为 G的一个 连通分支,用 W(G)表示 G
中的 连通分支数 。无向图 G＝ <V,E>是连通图当且仅当 W(G)＝ 1。
Guoyongfang.2006@yahoo.com.cn
G1是连通图,W(G1)＝ 1；
G2是非连通图，且 W(G2)＝ 4。
例：
例：
Guoyongfang.2006@yahoo.com.cn
定义 设无向图 G=〈 V,E〉 为连通的,若有结点集
V1是 V的真子集,使得图 G删除了 V1所有结点后,
所得的子图是不连通的,而删除了 V1的任意真子集后,所得的子图仍然是连通图 。 则称集合 V1为图 G的 点割集 。 若某一结点就构成点割集,则称该结点为 割点 。
这样,一个连通图,删除它的一个点割集后,将分成两个或多于两个连通分支 。
割点
Guoyongfang.2006@yahoo.com.cn
若 G不是完全图,我们定义 k(G)=min{| V1 |
|V1是 G的点割集 }为 G的点连通度 (或连通度 )。
连通度 k(G)是为了产生一个不连通图需要删去的点的最少数目 。 于是,一个不连通图的连通度等于 0,存在着割点的连通图的连通数为 1。
完全图 Kp中删去任何 m个 (m＜ p-1)点后仍然连通,
但是删去了 p-1个结点后产生一个平凡图,故定义 k(Kp )= p-1。
割点
Guoyongfang.2006@yahoo.com.cn
定义 设无向图 G=〈 V,E〉 为连通的,若有边集 E1是 E
的真子集,使得图 G删除了 E1所有边后,所得的子图是不连通的,而删除了 E1的任意真子集后,所得的子图仍然是连通图 。 则称集合 E1为图 G的 边割集 。
若某一边构成边割集,则称该边为 割边 (或桥 )。
G的割边也就是 G中的一条边 e使得 W(G-e)＞
W(G)。与点连通度相似，我们定义非平凡图 G的边连通度为,λ (G)=min{| E1 ||E1是 G的边割集 }，边连通度 λ (G)是为了产生一个不连通需要删去边的最少数目。对于 平凡图 λ (G)=0，此外一个不连通图也有
λ (G)=0。
割边
Guoyongfang.2006@yahoo.com.cn
定理 对于任何一个图 G =〈 V,E〉,有
k(G)≤λ(G)≤δ(G)
证明 若 G不连通,则 k(G)=λ(G)=0,故上式成立 。
若 G连通,
① 证明 λ(G)≤δ(G)。 若 G是平凡图,则 λ(G)=0≤δ(G),若
G是非平凡图,则因每一结点的所有关连边必含一个边割集,故 λ(G)≤δ(G)。
定理
Guoyongfang.2006@yahoo.com.cn
② 再证 k(G)≤λ(G)
.设 λ(G)=1,即 G有一割边,显然此时 k(G)=1,上式成立 。
.设 λ(G)≥2,则必可删去某 λ(G)条边,使 G不连通,而删除 λ(G)-1条边,它仍然连通,而且有一条桥 e=(u，
v)。 对 λ(G)-1条边中每一条边都选取一个不同于 u，
v的端点,将这些端点删去必至少删去 λ(G)-1条边 。
若这样产生的图是不连通的,则 k(G)≤λ(G)-1≤λ(G)，
若这样产生的图是连通的,则 e=(u,v)仍然是桥,
此时再删去 u,v,就必产生一个不连通图,故
k(G)≤λ(G)。
由此得 k(G)≤ λ (G)≤ δ (G)。
续：
Guoyongfang.2006@yahoo.com.cn
定理 一个连通无向图 G =〈 V,E〉 的某一点 v是图 G的割点的充分必要条件是存在两个结点 u
和 w,使得结点 u和 w的每一个路都通过结点
v。
定理
Guoyongfang.2006@yahoo.com.cn
三、有向图的连通性三、有向图的连通性定义 设 G＝ <V,E>是一个有向图，对 vi,vj?V，从
vi到 vj如存在一条 路，则称 结点 vi到 vj是可达的。
在有向图中，如从 vi到 vj可达，但从 vj到 vi则不一定是可达的。
为此，若将可达性看成是图 G＝ <V,E>的结点集合 V上的二元关系的话,对有向图来说，该可达性关系仅是自反的、传递的关系,但不一定是对称的关系、
也不一定是反对称的关系。
Guoyongfang.2006@yahoo.com.cn
定义定义 在图 G＝ <V,E>中，对?vi,vj?V，如果从 vi
到 vj存在路，则称长度最短的路为从 vi到 vj的 短程线,从 vi到 vj的短程线的长度称为从 vi到 vj的 距离,记为 d(vi,vj)。
d(vi,vj)满足下列性质：
d(vi,vj)?0；
d(vi,vi)＝ 0；
d(vi,vk)+d(vk,vj)? d(vi,vj)；
d(vi,vj)＝? (当 vi到 vj不存在路时 )。
Guoyongfang.2006@yahoo.com.cn
在 (a)中有：
d(v2,v1)＝ 1,d(v1,v2)＝ 2，
d(v3,v1)＝ 2,d(v1,v3)＝ 4；
在 (b)中有：
d(v1,v3)＝ 2,d(v3,v7)＝ 3,d(v1,v7)＝
4。
例：
例：
Guoyongfang.2006@yahoo.com.cn
定义
设 G＝ <V,E>是一个有向图，若略去 G中所有有向边的方向后所得到的无向图 G1是一个无向连通图，则称该有向图 G是一个 弱连通图 ；
设 G＝ <V,E>是一个有向图，若 G中任意两个结点之间至少单方向可达的，则称该有向图 G是一个 单侧连通图 ；
设 G＝ <V,E>是一个有向图，若 G中任意两个结点之间都是相互可达的，则称该有向图 G是一个 强连通图 。
定义
Guoyongfang.2006@yahoo.com.cn
G1是弱连通图；
G2是单侧连通图 (当然它也是弱连通图 )；
G3是强连通图 (当然它也是弱连通图、单向连通图 )。
例：
例：
Guoyongfang.2006@yahoo.com.cn
定理定理 一个有向图 G是强连通图当且仅当 G中有一个回 路，它至少包含每一个结点一次。
证明,,?” G中有一个回路，它至少包含每个结点，则
G中任何两个结点间都是相互可达的，故 G为强连通图。
,?” G是强连通图，则任意两个结点之间都是相互可达的，设 G＝ <V,E>,V＝ {v1,v２,v３,…,vｎ }，则 v1到 v2可达，
v2到 v3可达,v3到 v4可达,……,vｎ -１ 到 vｎ 可达,vn到 v1可达，
由此可得到一条回路 (v1,v２,v３,……,vｎ,v1)，它至少包含每个结点一次。■
Guoyongfang.2006@yahoo.com.cn
定义定义 设 G＝ <V,E>是一个有向图,G1＝ <V1，
E1>是 G的子图,若 G1是弱连通图 (单侧连通图，强连通图 )，且没有包含 G1的更大的子图是弱连通图 (单侧连通图，强连通图 )，
则称 G1是 极大弱连通子图 (极大单侧连通子图，极大强连通子图 )或称为 弱分图 (单侧分图，强分图 )。
Guoyongfang.2006@yahoo.com.cn
例,如上图 (a)所示，有：
例：
由 {v２ },{v６ },{v1,v３,v４,v５,v７ }所导出的子图构成了该图的强分图；
由 {v1,v２,v３,v４,v５,v7},{v1,v３,v４,v5,v６,v７ }所导出的子图构成了该图的单侧分图；
(a)图本身就是一个弱分图。
Guoyongfang.2006@yahoo.com.cn
例：
如上图 (b)所示，有：
由 {v1},{v２ },{v3},{v4},{v5,v6,v７ }所导出的子图构成了该图的强分图；
由 {v1,v２,v３ },{v1,v3,v4},{v５,v６,v７ }所导出的子图构成了该图的单侧分图；
由 {v1,v２,v３,v４ },{v５,v６,v７ }所导出的子图构成了该图的弱分图。
Guoyongfang.2006@yahoo.com.cn
定理
在有向图 G＝ <V,E>，它的每一个结点必然位于且仅位于一个强分图中。
定理
Guoyongfang.2006@yahoo.com.cn
证：
①,对?v?V，令 S是 G中所有与 v相互可达的结点集，则有 v?S，由于 v与 S中的一切结点相互可达，所以，由可达性具有传递性知,S
中的一切结点之间是相互可达的，即 S是 G的一个强分图，所以,v
位于一个强分图中；
②,设 v还位于另一个强分图 T中，则由 S中的每个结点都与 v相互可达，且 T中的每个结点也都与 v相互可达，所以，由可达性具有传递性知,S中的一切结点与 T中的一切结点之间是相互可达的，即由
S∪T 就构成了一个更大的强连通的子图，这就与 S,T都是两个强分图矛盾，故 G的每个结点仅位于一个强分图中。■
Guoyongfang.2006@yahoo.com.cn
7-3 图的矩阵表示一,邻接矩阵设 G＝ <V,E>是一个简单图,V＝ {v1,v2,…,vn}，
E＝ {e1,e2,…,en}，则 n阶方阵 A(G)＝ (aij)n?n称为 G
的 邻接矩阵 。其中：
EvvEvv0
EvvEvv1
a
jiji
jiji
ij ），或（，，
），或（，，
由邻接矩阵的定义知：其矩阵的元素是一个二值元素，所以，又称该矩阵为 位矩阵 或 布尔矩阵 。
Guoyongfang.2006@yahoo.com.cn
例：
邻接矩阵,。，
0100
1100
0101
0110
)G(A
0011
0110
1101
1010
)G(A 21
例：
Guoyongfang.2006@yahoo.com.cn
性质设 G＝ <V,E>是一个简单图，则有：
1) 如 aii＝ 1,则结点 vi有环,否则 vi无环。 (i?{1,2,3,…,n})
2) 如 aij＝ 1,则从结点 vi到结点 vj有边。 (i,j?{1,2,3,…,n})
3) 如对?i,j?{1,2,3,…,n},都有 aij＝ 0，则此时图 G是一个零图 。
4) 如对?i,j?{1,2,3,…,n},都有 aij＝ 1(i?j),aii＝ 0，则此时图 G是一个完全图。
5) 如 G是一个无向简单图,则对任意 vi?V，都有：
，
n
k
ki
n
k
iki aav
11
)d e g (
n
i
n
k
ik
n
i
n
i
n
k
iki aav
1 11 1 1
)()d e g ( ；
Guoyongfang.2006@yahoo.com.cn
性质如 G是一个有向简单图，则对任意 vi?V，都有：
，）（，）（
n
1k
kii
n
1k
iki avd e gavd e g
，）（）（）（）（
n
1k
kiik
n
1k
ki
n
1k
ikiii aaaavd e gvd e gvd e g；）（）（
n
1i
n
1i
n
1k
kiiki aavd e g
Guoyongfang.2006@yahoo.com.cn
性质
6) 令 B＝ (bij)＝ A2＝ A× A＝ (aij(2))n?n，则有：
n
1k
kjik
)2(
ijij aaab
此时,bij表示从 vi到 vj长度为 2的路数目，如 bij＝
0，则无长度为 2的路，而 bii给出了经过 vi的长度为 2的回路数目；
Guoyongfang.2006@yahoo.com.cn
性质
7) 令 C＝ (cij)＝ Am＝ A× A× … × A＝ (aij(m))n?n，
则有：
n
1k
kj
)1m(
n
1k
)1m(
ik
)m(
ij aaaaac ikkjij
此时,cij表示从 vi到 vj长度为 m的数目，如 cij＝ 0，
则无长度为 m的路，而 cii给出了经过 vi的长度为 m
的回路数目。
Guoyongfang.2006@yahoo.com.cn
性质如下图,V＝ {v1,v2,v3,v4,v5}，其邻接矩阵 A,A2、
A3,A4
。，
，，
3303
3303
0090
3303
A
0030
0030
3303
0030
A
1101
1101
0030
1101
A
0010
0010
1101
0010
A
43
2
上面图中结点的度数和两结点间长度为 k的路的条数。
Guoyongfang.2006@yahoo.com.cn
定理定理 设 A(G)为图 G的邻接矩阵,则 (A(G))l中的 i
行 j列元素等于 G中联结 vi与 vj的长度为 l的路的数目 。
Guoyongfang.2006@yahoo.com.cn
定理例,给定一图 G=〈 V,E〉 如图所示 。
从下面的矩阵中我们可以看到一些结论,
如 v1与 v2之间有两条长度为 3的路,结点 v1与 v3之间有一条长度为 2的路,在结点 v2有四条长度为 4的回路 。
10000
01000
00101
00020
00101
01000
10000
00010
00101
00010
2
AA
10000
01000
00202
00040
00202
01000
10000
00020
00202
00020
43
AA
Guoyongfang.2006@yahoo.com.cn
二、可达性矩阵设 G＝ <V,E>＝ (n,m)是一个简单图,V＝
{v1,v2,v3,…,vn}，定义,Rn＝ (rij)n*n＝ A
+A2+A3+…… +An，
则 rij表明了从结点 vi到 vj长度为 1至 n的所有路数目之和。
rij＝ 0，则表明从结点 vi到 vj是不可达的；
rij?0，则表明从结点 vi到 vj至少有长度为 m(1?m
n)的通路，即此时从结点 vi到 vj是可达的。
Guoyongfang.2006@yahoo.com.cn
二、可达性矩阵
，否则的通路至少存在一条非零长度到，
0
vv1
p jiij (i,j＝ 1,2,3,……,n)
则称矩阵 P为图 G的 可达性矩阵 。
定义 设 G＝ <V,E>＝ (n,m)是一个简单图,V＝ {v1,v2,v3,…,vn}，定义一个 n阶方阵 P＝ (pij)n*n，其中：
Guoyongfang.2006@yahoo.com.cn
图的矩阵表示由矩阵 Rn可知,如 rij＝ 0，则表明从结点 vi
到 vj是不可达的；
rij?0，则表明从结点 vi到 vj至少有长度为
m(1?m?n)的路，即此时从结点 vi到 vj是可达的。
所以有：
pij＝ 0? rij＝ 0，
pij＝ 1? rij?0，
(i,j＝ 1,2,3,……,n)。
Guoyongfang.2006@yahoo.com.cn
例,
，，
0010
1111
1012
1100
A
0001
1011
1100
0010
A 2
。，
1012
3233
3222
1121
A
1100
2122
1121
1012
A 43
，
2123
7477
6455
3253
AAAAR 4324 。
1111
1111
1111
1111
P
Guoyongfang.2006@yahoo.com.cn
利用布尔求乘和布尔求和的运算直接求可达性矩阵
P＝ A?A(2)?A(3)?...?A(n)
A(m)＝ A?A?A?...?A (m＝ 1,2,3,… n)
利用布尔求乘和布尔求和的运算直接求可达性矩阵
Guoyongfang.2006@yahoo.com.cn
例：
例,利用邻接矩阵的布尔运算求可达性矩阵。
，,）（
0010
1111
1011
1100
A
0001
1011
1100
0010
A 2
，,）（）（
1011
1111
1111
1111
A
1100
1111
1111
1011
A 43
。）（）（）（
1111
1111
1111
1111
A......AAAP n32
Guoyongfang.2006@yahoo.com.cn
三：完全关联矩阵三：完全关联矩阵定义 给定无向图 G,令 v1,v2,…,vp和 e1,e2,…,eq分别记为 G的结点和边,则矩阵 M(G)=(mij),其中称 M(G)为完全关联矩阵。
ji
ji
ij ev
ev
m 不关联若关联若
,0
,1
Guoyongfang.2006@yahoo.com.cn
例：
Guoyongfang.2006@yahoo.com.cn
性质从关联矩阵中可以看出图形的一些性质：
⑴图中每一边关联两个结点，故 M(G)的每一列只有两个 1。
⑵每一行元素的和数对应于结点的度数。
⑶一行中的元素全为 0，其对应的结点为孤立点。
⑷两个平行边其对应的两列相同。
⑸同一图当结点或边的编序不同，其对应 M(G)仅有行序、列序的差别。
Guoyongfang.2006@yahoo.com.cn
定义定义 给定简单有向图
G=〈 V,E〉,V={v1,v2,… vp},E={e1,e2,… eq},
p× q阶矩阵 M(G)=(mij),其中称 M(G)为 G的完全关联矩阵 。
ji
ji
ji
ij
evG
evG
evG
m
不关联中在的终点是中在的起点是中在
,0
,1
,1
Guoyongfang.2006@yahoo.com.cn
例：
Guoyongfang.2006@yahoo.com.cn
7-4 Euler图与 Hamilton图一,Euler图哥尼斯堡七桥问题：
Guoyongfang.2006@yahoo.com.cn
例 (蚂蚁比赛问题 )
解,仅有两个度数为奇数的结点 b,c,因而存在从 b到 c的欧拉路,蚂蚁乙走到 c只要走一条欧拉路,边数为 9条 。 而蚂蚁甲要想走完所有的边到达 c,至少要先走一条边到达 b,再走一条欧拉路,因而它至少要走 10条边才能到达 c,所以乙必胜 。
甲、乙两只蚂蚁分别位于如下图 中的结点 a,b处，并设图中的边长度是相等的。甲、乙进行比赛：从它们所在的结点出发，走过图中的所有边最后到达结点 c处。如果它们的速度相同，
问谁先到达目的地？
Guoyongfang.2006@yahoo.com.cn
1.无向的 Euler图定义 给定 G是一个无孤立结点的无向图,若存在一 条路 (回路 ),经过图中每边一次且仅仅一次,
则称此路 (回路 )为该图的一条 欧拉路 (回路 )。 具有欧拉回路的图称为 欧拉图 。
如何判断一个图是否是欧拉图或存在欧拉路呢？
Guoyongfang.2006@yahoo.com.cn
判断欧拉图及欧拉路的方法定理无向图 G＝ <V,E>具有一条欧拉路当且仅当 G
是连通的，且仅有零个或者两个奇度数结点。
无向图 G＝ <V,E>是欧拉图当且仅当 G是连通的，且 G的所有结点的度数都为偶数。
Guoyongfang.2006@yahoo.com.cn
证明
1)、若 G＝ (1,0)是一个平凡图，则定理显然成立。
下面讨论 G是非平凡图的情况。
“?”设 G具有一条 Euler路 L。
① 设该欧拉路 L＝ v0e1v1e2v2e3…… ekvk。即从 v0出发，经过结点 v1，
v2,…… vk-1，边 e1,e2…… ek到达 vk，其中的结点可以重复出现，
但边不重复，并且 L中的边是包括了 G中所有的边。由于 G中无孤立结点，因而 L经过了 G中的所有结点，所以 G是连通的。
② 对于欧拉路 L的任意非端点的结点 vi，在 L中每出现 vi一次，都关联着 G中的两条边，而当 vi又重复出现时，它又关联着 G中的另外的两条边，由于在通路 L中边不可能重复出现，因而 vi每出现一次，
都将使得结点 vi的度数增加 2度，若 vi在路中重复出现 j次，则
deg(vi)＝ 2j。
Guoyongfang.2006@yahoo.com.cn
证明 (续 1)
。
若端点 v0?vk，设 v0,vk在通路中作为非端点分别出 现
j1次和 j2次,v0,vk每出现一次，都将使得结点 v0,vk的度数增加 2度，而 v0,vk作为端结点时，仅仅只出现一次，且在其
v0,vk的度数上只增加 1度，则 v0,vk的总度数分别是：
deg(v0)＝ 2j1+1，
deg(vk)＝ 2j2+1。
综上所述，即 G仅仅只有两个奇度数结点，即两个端结点 v0,vk的度数为奇数。
若端点 v0＝ vk，则 G中的所有结点在通路中都可看成为非端点，由上可知，每个结点的度数都是偶数，即 G中仅有零个奇度数结点。
Guoyongfang.2006@yahoo.com.cn
“?”构造性证明 。
证明 (续 2)
若有两个奇度数结点 。 则我们从两个度数为奇数的结点之一开始构造一条欧拉路,以每条边最多经过一次的方式通过图中的边 。
对于度数为偶数的结点,通过一条边进入这个结点,总可以通过一条未经过的边离开这个结点,因此,这样的构造过程一定以到达另一个度数为奇数的结点而告终 (若无度数为奇数的结点,则以回到原出发点而告终 )。 如果图中所有的边已用这种方式经过了,显然这就是所求的欧拉路 。 如果这个图中不是所有的边都经过了,我们将去掉已经过的边,得到一个由剩余的边组成的子图,这个子图的所有结点的度数均为偶数 。 因为原来的图是连通的,因此,这个子图必与我们已经过的路在一个或多个结点相接 。
Guoyongfang.2006@yahoo.com.cn
证明 (续 3)
由这些结点中的一个开始我们再通过边构造路,因为结点的度数全为偶数，因此，这条路一定最终回到起点。我们将这条回路加到已构造好的路中间组合成一条路。如有必要，
这一过程重复下去，直到我们得到一条通过图中的所有边的路，
即欧拉路。
上述过程即可。
2)、该结论直接是 1)的推广。■
Guoyongfang.2006@yahoo.com.cn
例由定理容易看出,a) 是欧拉图；
b) 不是欧拉图，但存在欧拉路；
c) 即不是欧拉图，也不存在欧拉路。
Guoyongfang.2006@yahoo.com.cn
2.一笔画问题对于上图，有 图 (a)是能一笔画并且能回到出发点的，
图 (b)也能一笔画但不能回到出发点的。
Guoyongfang.2006@yahoo.com.cn
3.有向的 Euler图定义 给定 G是一个无孤立结点的有向图，若存在一 条单向路 (回路 )，经过图中每边一次且仅仅一次，则称此单向路 (回路 )为该图的一条 单向欧拉路 (回路 )。具有单向欧拉回路的图称为 欧拉图 。
如何判断一个有向图是否是欧拉图或存在单向欧拉路呢？
Guoyongfang.2006@yahoo.com.cn
判断欧拉图及欧拉通路的方法定理有向图 G＝ <V,E>具有一条单向欧拉路当且仅当 G是连通的，且除了两个结点以外，其余结点的入度等于出度，而这两个例外的结点中，一个结点的入度比出度大 1，另一个结点的出度比入度大 1。
有向图 G＝ <V,E>具有一条欧拉回路 (即是欧拉图 )当且仅当 G是连通的，且 G的所有结点的入度都等于出度。
Guoyongfang.2006@yahoo.com.cn
例图 a)存在一条单向的欧拉路,v3v1v2v3v4v1；
图 (b)中存在单向欧拉回路 v1v2v3v4v1v3v1，因而 (b)是欧拉图；
图 (c)中有单向欧拉回路 v1v2v3v4v5v6v7v8v2v4v6v8v1因而 (c)
是欧拉图。
Guoyongfang.2006@yahoo.com.cn
已知 a,b,c,d,e五个人中，会讲的语言分别是：
a,英语、汉语、德语 b,俄语、英语
c,汉语、英语、法语
d：汉语、俄语 e,德语、法语请问怎样将他们的作为安排在圆桌旁，使得每个人都能与他身边的人交谈？
Guoyongfang.2006@yahoo.com.cn
二、哈密尔顿图周游世界问题定义 给定 G是一个无孤立结点的无向图，若存在一条路
(回路 )，经过图中每个结点一次且仅仅一次，则称此路 (回路 )为该图的一条 哈密尔顿路
(回路 )。具有哈密尔顿回路的图称为 哈密尔顿图 。
Guoyongfang.2006@yahoo.com.cn
哈密尔顿图的判定定理 (必要条件 ) 若图 G=〈 V,E〉 具有汉密尔顿回路，
则对于结点集 V的每一个非空子集 S均有 W(G－ S)≤|S|
成立。其中 W(G－ S)是 G－ S中连通分支数。
Guoyongfang.2006@yahoo.com.cn
哈密尔顿图的判定证明 设 C是 G的一条汉密尔顿回路,则对于 V
的任何一个非空子集 S在 C中删去 S中任一结点
a1,则 C－ a1是连通非回路,若删去 S中的另一个结点 a2,则 W(C－ a1－ a2)≤2,由归纳法得知 W(C－ S)≤|S|
同时 C－ S是 G－ S的一个生成子图,因而 W(G
－ S)≤W(C－ S)
所以 W(G－ S)≤ |S|
Guoyongfang.2006@yahoo.com.cn
例在图 (a)中，虽然对任意的结点集合 V1,都满足 W(G-V1)?|V1|，
但它仍然不是哈密尔顿图。
在图 (b)中，任意两个结点的度数之和为 4，结点数为 6，即有 4?6，，但它仍然是 哈密尔顿图。
Guoyongfang.2006@yahoo.com.cn
哈密尔顿图的判定定理 (充分条件 ) 设 G具有 n个结点的简单图，如果 G中每一对结点的度数之和大于等于 n-
1，则在 G中存在一条汉密尔顿路。
Guoyongfang.2006@yahoo.com.cn
哈密尔顿图的判定证明 我们首先证明 G是连通的。若 G有两个或更多互不连通的分图，设一个分图有 n1个结点，任取一个结点 v1，设另一个分图有 n2个结点，任取一个结点 v2，
因为 d(v1)≤n1－ 1,d(v2)≤n2－ 1，故 d(v1)+ d(v2)
≤n1+ n2－ 2＜ n－ 1，这表明与题设矛盾，故 G必连通。
其次，我们从一条边出发构成一条路，证明它是汉密尔顿路。
Guoyongfang.2006@yahoo.com.cn
哈密尔顿图的判定设在 G中有 p－ 1条边的路,p＜ n，它的结点序列为 v1，
v2,…,vp。如果有 v1或 vp邻接于不在这条路上的一个结点，我们可立即扩展这条路，使它包含这一个结点，从而得到 p条边的路。否则,v1和 vp都只能邻接于这条路上的结点，我们证明在这种情况下，存在一条回路包含结点 v1,v2,…,vp。若 v1邻接于
vp，则 v1,v2,…,vp,v1即为所求的回路。假设与 v1邻接的结点集是 {vl,vm,…,vj,…,vt}(k个 )，这里 2≤l,m,…,
t≤p-1，如果 vp是邻接于 vl-1,vm-1,…,vj-1,…,vt-1中之一，
譬如说 vj-1，如图 (a)所示,v1v2v3… vj-1vpvp-1… vjv1是所求的包含结点的回路 v1,v2,…,vp。
Guoyongfang.2006@yahoo.com.cn
哈密尔顿图的判定如果 vp不邻接于 vl-1,vm-1,…,vj-1,…,vt-1中任一个，则
vp至少邻接于 p－ k－ 1个结点,deG(vp)≤p-k-1,deG(v1) ≤k，
故 deG(vp)＋ deG(v1) ≤p-k-1+ k= p- 1＜ n-1，即 v1与 vp度数之和至多为 n-2，得到矛盾。
至此,我们有包含所有结点 v1,v2,…,vp的一条回路,因为 G
是连通的,所以在 G中必有一个不属于该回路的结点 vx与 v1，
v2,…,vp中的某一个结点 vk邻接,如图 (b)所示,于是就得到一条包括 p条边的路 (vx,vk,vk+1,vj-1,vp,vp-1,vj,v1,v2，
vk-1)。 如图 (c)所示,重复前述的构造方法,直到得到 n-1条边的路 。
Guoyongfang.2006@yahoo.com.cn
哈密尔顿图的判定
Guoyongfang.2006@yahoo.com.cn
哈密尔顿图的判定定理 (充分条件 ) 设图 G是具有 n个结点的简单图，如果
G中每一对结点的度数大于等于 n，则在 G中存在一条汉密尔顿回路。
证明 由上面定理可知必有一条汉密尔顿路,设为 v1v2… vn，
如果 v1与 vn邻接,则定理得证 。
如果 v1与 vn不邻接，假设 v1邻接于 {vi1,vi2,…,vik},
2≤ ij≤ n-1，可以证明 vn必邻接于 vi1-1,vi2-1,…,vik-1中之一。如果不邻接于中的任意一点，则 vn至多邻接于 n-k-1个结点，因而 d(vn)≤ n－ k－ 1，而 d(v1)= k，故 d(v1)+ d(vn) ≤ n
－ k－ 1+ k= n-1，与题设矛盾，所以必有汉密尔顿回路
v1v2… vj-1vnvn-1… vjv1，如图所示。
Guoyongfang.2006@yahoo.com.cn
哈密尔顿图的判定
Guoyongfang.2006@yahoo.com.cn
例判断图 (a),(b)所示的图中，是否存在哈密尔 顿回路或路。
Guoyongfang.2006@yahoo.com.cn
解
(a)、若图 (a)中存在哈密尔顿回路，则该回路 组成的图中任何结点的度数均为 2。而结点 1,2,3,4,5所关联的边均在回路中，于是在结点 a,b,c,d,e处均应将不与 1、
2,3,4,5关联的边删除，而要删除与结点 a,b,c,d、
e关联的其他边，这样一来，图就不连通了，因而图中不存在哈密尔顿回路。
(b)、在图 (b)中，任取一结点如 1用 A标记，所有与它邻接的结点用 B标记。继续不断地用 A标记所有邻接于 B的结点，
用 B标记所有邻接于 A的结点，直到所有结点都标记完为止。
如果图中有一条哈密尔顿路，那么它必交替地通过结点 A和结点 B，故而或者结点 A与结点 B数目相同，或者两者相差 1个。
然而图 (b)中有 3个结点标记为 A,5个结点标记为 B，它们相差两个，所以该图不存在哈密尔顿路。
Guoyongfang.2006@yahoo.com.cn
7-5 平面图例们三个分成一组，一元件组中的每一个元件都用导线与另一组之每个元件相接，如下图所示。 (其中：元件 ——
结点，边 ——导线 )
Guoyongfang.2006@yahoo.com.cn
1.平面图定义 设 G是一个无向图，若经过某种改画，能把
G
中的所有结点和边都画在一个平面上,使得任何两边除公共结点以外没有其他交叉点,则称 G为平面图 ；若 G无论如何改画,它们的边之间总有交叉现象出现,则称 G为 非平面图 。
Guoyongfang.2006@yahoo.com.cn
2．平面区域与图的面定义 设 G是一个连通的平面图，由图中的边所包围的其内部不包含图的结点和边的区域，称为 G
的一个 面,常常把面记为,r”；包围该面的诸边所构成的回路称为这个面的 边界,面 r的边界的回路的长度称为该面的 次数,记为 deg(r)。
称该面为 有限面,否则称该面为 无限面 。
一个平面图有且仅有一个无限面 。
Guoyongfang.2006@yahoo.com.cn
例如下图所示，该图中有六个结点，九条边，它们把平面图分成了五个面,
Guoyongfang.2006@yahoo.com.cn
定理一个有限平面图，面的次数之和等于其边数的两倍。
Guoyongfang.2006@yahoo.com.cn
欧拉公式定理 G＝ <V,E>是一个连通的平面图。
1) 若它有 v个结点,e条边,r个面，则有：
v-e+r＝ 2 (平面图的欧拉公式 )。
Guoyongfang.2006@yahoo.com.cn
证明
1)、对边 m进行归纳。
1．当 m＝ 1时，则仅有下面两种连通的平面图：
(a) (b)
对情况 (a)，有,m＝ 1,n＝ 2,r＝ 1，所以有,n-m+r＝ 2；
对情况 (b)，有,m＝ 1,n＝ 1,r＝ 2，所以有,n-m+r＝ 2；
2．设 m＝ k-1时成立，即有,nk-1-mk-1+rk-1＝ 2； (其中,nk-1,rk-1分别为对应的结点数和面数,mk-1＝ k-1。 )
3．当 m＝ k时，此时可将其看成是在 k-1条边的连通平面图上增加一条边，使她仍为连通平面图，此时有两种增加方法：
Guoyongfang.2006@yahoo.com.cn
证明 (续 1)
(a)、加一个新的结点 v，使得结点 v与图中的某一点
vj相连，此时有：
nk＝ nk-1+1； mk＝ mk-1+1； rk＝ rk-1。
所以有,nk-mk+rk＝ (nk-1+1)-(mk-1+1)+rk-1＝ 2。
(b)、若增加的一条边是连接的图中的两个结点 vi,
vj，此时有：
nk＝ nk-1； mk＝ mk-1+1； rk＝ rk-1+1。
所以有,nk-mk+rk＝ nk-1-(mk-1+1)+(rk-1+1)＝ 2。
右图给出了上述两种情况。
Guoyongfang.2006@yahoo.com.cn
证明 (续 2)
所以，当 m＝ k时，仍然成立。
由数学归纳法知：对任意一个 (n,m)连通平面图，都有,n-m+r＝ 2。
Guoyongfang.2006@yahoo.com.cn
定理设 G是一个有 v个结点 e条边的连通简单平面图，若 v大于等于 3，则 e小于等于 3v-6。
Guoyongfang.2006@yahoo.com.cn
以上定理可以用来证明某些图不是平面图。
证明 K5不是平面图。
证明对于 K5的任意边 e,K5 -e是平面图。
Guoyongfang.2006@yahoo.com.cn
设 G 为连通的简单平面图，结点数为 v，
面数为 r，证明：
（ 1）若 v≥3，则 r≤2v-4；
Guoyongfang.2006@yahoo.com.cn
K3,3图不是平面图，但 K3,3-e是平面图证明：在 6个结点 12条边的平面简单图中，
每个面用 3条边围成。
Guoyongfang.2006@yahoo.com.cn
与平面图有密切关系的一个图论的应用是图形的着色问题，这个问题最早起源于地图的着色，
一个地图中相邻的国家着以不同的颜色，那么至少需要多少种颜色？
一百多年前，英国格色里提出了用四种颜色即可对地图着色的猜想,1879年肯普给出了这个猜想的第一个证明，但到 1890年希伍德发现肯普证明是错的，但指出肯普的方法虽然不能证明地图着色用四种颜色就够了，但可证明用五种颜色就够了，此后四色猜想一直成为数学家感兴趣而未能解决的难题。
7-6对偶图与着色
Guoyongfang.2006@yahoo.com.cn
直到 1976年美国数学家阿佩尔和黑肯宣布：
他们用电子计算机证明了四色猜想是成立的。所以从 1976年以后，四色猜想就成了四色理论。
7-6对偶图与着色
Guoyongfang.2006@yahoo.com.cn
对偶图的概念定义 给定平面图 G＝ 〈 V,E〉,它有面 F1,F2,…,
Fn,若有图 G*＝ 〈 V*,E*〉 满足下述条件：
⑴ 对于图 G的任一个面 Fi,内部有且仅有一个结点
vi*∈ V*。
⑵ 对于图 G的面 Fi,Fj的公共边 ek,存在且仅存在一条边 ek*∈ E*,使 ek*＝ (vi*,vj*),且 ek*和 ek相交 。
⑶ 当且仅当 ek只是一个面 Fi的边界时,vi*存在一个环
ek*和 ek相交,则图 G*是图 G的对偶图 。
从这个定义看出,G*是 G的对偶图,则 G也是 G*的对偶图 。 一个连通平面图的对偶图也必是平面图 。
Guoyongfang.2006@yahoo.com.cn
图的同构五、图的同构例,如下图 (a),(b),(c),(d)所示，
图 (a)、图 (b)、图 (c)和图 (d)所表示的图形实际上都是一样的。
Guoyongfang.2006@yahoo.com.cn
定义定义 设有图 G＝ <V,E>和图 G1＝ <V1,E1>,如果存在双射函数 g:V→ V 1,使得 对 于任 意的 边 e＝ (vi,vj )
E(或 <vi,vj>?E)当且仅当 e1＝ (g(vi),g(vj))
E1(或 <g(vi),g(vj)>?E1) 则称 G和 G1同构,记为 G≌G 1。
同构的充要条件,两个图的结点和边分别存在一一对应，且保持关联关系。
Guoyongfang.2006@yahoo.com.cn
例：
例,如图 (a),(b)所示的两个图 G＝ <V,E>和 G1＝
<V1,E1>，证明 G≌G 1。
解,显然，定义函数 g,V→V 1，满足 g(vi)＝ vi’（ i＝ 1，
2,3,4,5），可以验证 g一定是一个满足定义的双射，
所以 G≌G 1。
Guoyongfang.2006@yahoo.com.cn
必要条件两个图同构的必要条件：
结点数目相同；
边数相同；
度数相同的结点数相同。
注意,这三个条件并不是充分条件。例如下面两个图满足这三个条件，但它们不同构。
Guoyongfang.2006@yahoo.com.cn
对偶图与着色定义 如果图 G的对偶图 G*同构于 G,则称 G是自对偶的 。
图 G的 正常着色 (或简称为着色 )是指对它的每一个结点指定一种颜色,使得没有两个相邻的结点有同一种颜色 。 如果图 G在着色时用 n种颜色,我们称 G为 n-色 的 。
对于图 G着色时,需最少颜色数称为 着色数,记作 x(G)。
Guoyongfang.2006@yahoo.com.cn
对偶图与着色可用 韦尔奇 ·鲍威尔法 (Welch Powell)对图 G进行着色,
其方法是：
⑴ 将图 G的结点按照度数的递减次序进行排列 。 (这种排列可能并不是唯一的,因为有些点有相同的度数 )。
⑵ 用第一种颜色对第一点进行着色,并且按排列次序,
对与前面着色点不邻接的每一点着上同样的颜色 。
⑶ 用第二种颜色对尚未着色的点重复 ⑵,用第三种颜色继续这种做法,直到所有的点全部着上色为止 。
Guoyongfang.2006@yahoo.com.cn
对偶图与着色例,用韦尔奇 ·鲍威尔法对图着色 。
解 ⑴ 根据递减次序排列各点 A5,A3，
A7,A1,A2,A4,A6,A8。
⑵ 第一种颜色对 A5着色,并对不相邻的结点 A1也着第一种颜色 。
⑶ 对 A3结点和它不相邻的结点 A4,A8着第二种颜色 。
⑷ 对 A7结点和它不相邻的结点 A2,A6着第三种颜色 。
因此图 G是三色的 。 注意图 G不可能是二色的,因为 A1,A2,A3相互邻接,故必须用三种颜色 。 所以 x(G)＝ 3。
Guoyongfang.2006@yahoo.com.cn
对偶图与着色定理 对于 n个结点的完全图 Kn，有 x(Kn)＝ n。
证明 因为完全图每一个结点与其它各结点都相邻接，故 n个结点的着色数不能少于 n，又 n个结点的着色数至多为 n，故有 x(Kn)＝ n。
Guoyongfang.2006@yahoo.com.cn
对偶图与着色定理 设 G至少有三个结点的；连通平面图，则 G中必有一个结点 u，使得 deg(u)≤5。
证明 设 G＝ 〈 V,E〉,若 G的每一个结点 u,都有
deg(u)≥6,但因故 2e≥ 6v,所以 e≥ 3v＞ 3v－ 6,与前边的定理矛盾 。
ev
v
i
i 2
1
)(d e g
Guoyongfang.2006@yahoo.com.cn
7-8 根树及其应用定义 7-8.1 如果一个有向图在不考虑边的方向时是一棵树,那么这个有向图称为有向树,
Guoyongfang.2006@yahoo.com.cn
定义 7-8.2 一棵有向树,如果恰有一结点的入度为 0,
其余所有结点的入度都为 1,则称为根树,入度为 0
的结点称为根,出度为 0的结点称为叶,出度不为 0
的结点称为分枝点或内点,
1为根 ;2,4,7,8为分枝点；
3,5,6,9,10,11为树叶。
1处在第零层，层数为 0；
2,3,4处在第一层，层数为 1；
5,6,7,8同处在第二层，层数为 2；
9,10,11同处在第三层，层数为 3。
该根树的高为 3。
1
8
9 10 11
42 3
65
7
Guoyongfang.2006@yahoo.com.cn
定义：在根树中，从树根到任何一结点的通路长度叫做该结点的层数，称层数相同的结点在同一层上；所有结点中层数最大值称为根树的高。
可用家族关系形象的表示根树中各结点间的关系：
Guoyongfang.2006@yahoo.com.cn
定义：在根树中，若从 vi到 vj可达，则称 vi是 vj的祖先,vj是 vi的后代；又若 <vi,vj>是根树中的有向边，则称 vi是 vj的父亲,vj是 vi的儿子；如果两个结点是同一个结点的儿子，则称这两个结点是兄弟。
在一个家族关系中，兄弟之间是有大小顺序的，
由此引入有序树的概念。
定义：如果在根树中规定了每一层上结点的次序，
这样的根树称为有序树。
Guoyongfang.2006@yahoo.com.cn
有序二叉树的每个结点至多有两个儿子，分别称为左儿子和右儿子；且至多有两棵子树，分别称为左子树和右子树。
Guoyongfang.2006@yahoo.com.cn
定义 7-8.3 根树包含一个或多个结点,这些结点中某一个称为根,其他所有结点被分成有限个子根树,
定义 7-8.4 在根树中,若每一个结点的出度小于或等于 m,则称这棵树为 m叉树,如果每一个结点的出度恰好等于 m或零,则称这棵树为完全 m叉树,若其所有树叶层次相同,称为正则 m叉树,当 m=2时,称为二叉树,
Guoyongfang.2006@yahoo.com.cn
例,M和 E两人进行网球比赛,如果一人连胜两盘或共胜三盘就获胜,比赛结束,(用二叉 树表示,)
E M
M
M
M
M
MM
M
M
E
E
E E
E
E
E
E
Guoyongfang.2006@yahoo.com.cn
任何一棵有序树都可以把它改写为一棵对应的二叉树,( 为左儿子,为右儿子,)
(a)
B
A
O
D
C
k H J
E F G
(b)
B
A
O
D
C
k H J
E
F
G
Guoyongfang.2006@yahoo.com.cn
(c)
O
B
A
D
C
k
H
J
E
F
G
Guoyongfang.2006@yahoo.com.cn
定理 7-8.1 设有完全 m叉树,其树叶数为 t,分枝点数为 i,则 (m-1)i=t-1.
证明,由假设可知,该树有 i+t个结点,由树的定义可知,该树的边数为 i+t-1.因为所有结点的出度之和等于边数,所以根据完全 m叉树的定义可知,
有 m*i=i+t-1
即 (m-1)i=t-1
Guoyongfang.2006@yahoo.com.cn
例,设有 28盏电灯,公用一个电源插座,问需用多少块具有四插座的接线板,
解,将电源插座看作根,四插座接线板看作分枝点,电灯看作树叶,则有
(4-1)i=28-1
得 i=9
需要九块四插座接线板,
Guoyongfang.2006@yahoo.com.cn
定义 7-8.5 在根树中,一个结点的通路长度,
就是从树根到此结点的通路中的边数,我们把分枝点的通路长度称为内部通路长度,树叶的通路长度称为外部通路长度,
定理 7-8.2 若完全二叉树有 n个分枝点,且各分枝点的层数之和为 I,各树叶的层数之和为 E,则
E=I+2n.
Guoyongfang.2006@yahoo.com.cn
例,验证定理 7-8.2
n=4,
I=0+1+1+2=4,
E=2+2+2+3+3=12,
I+2n=4+2*4=12=E
Guoyongfang.2006@yahoo.com.cn
定义 7-8.6 在带权二叉树中,若带权为
wi的树叶,其通路长度为 L(wi),我们把
w(T)=∑称为该带权二叉树的权,在所有带权 w1,w2,,wt,的二叉树中,w(T)最小的那棵树,称为最优树,
t
i=1
最优树问题
Guoyongfang.2006@yahoo.com.cn
我们假设 w1≤w2≤…≤wt。 1952年哈夫曼给出了求最优二叉树的方法。
最优树算法具体步骤如下：
1.初始令 s={w1,w2,,wt};
2.从 s中取出两个最小的权 wi,wj，画结点
vi，带权 wi，画结点 vj，带权 wj。画 vi和 vj
的父亲 v，连接 vi与 v,vj与 v，令带权
wi+wj;
3.令 s=(s-{wi,wj})U{wi+wj};
4.判断 s是否只含一个元素：若是，则停止。
否则转第 2步。
Guoyongfang.2006@yahoo.com.cn
例：用机器分辨一些币值为 1分,2分,5分的硬币，假设各种硬币出现的概率为 0.5,0.4，
0.1，问如何设计一个分硬币的算法，使所需时间最少？
解：利用哈夫曼算法答案如下
1
0.10.4
0.50.5
是否为 1分
1分是否为 2分
2分 5分是否否是
Guoyongfang.2006@yahoo.com.cn
定理 7-8.3 设 T为带权 w1≤w2≤…≤wt的最优树,则
(a)带权 w1,w2的树叶 vw1,vw2是兄弟,
(b)以树叶 vw1,vw2为儿子的分枝点,其通路长度最长,
定理 7-8.4 设 T为带权 w1 ≤w2 ≤ … ≤wt的最优树,若将以带权 w1和 w2的树叶为二子的分枝点改为带权 w1+w2的树叶,得到一棵新树 T’,
则 T’也是最优树,
Guoyongfang.2006@yahoo.com.cn
例,给定权 1,4,9,16,25,36,49,64,81,100:
(a)构造一棵最优二叉树 ;
(b)构造一棵最优三叉树 ;
(c)说明如何构造一棵最优 t叉树 ;
Guoyongfang.2006@yahoo.com.cn
(a) 1,4,9,16,25,36,49,64,81,100
1 4
5 9
14 16
5564
2530
100119
385
219
8185
4936
166
Guoyongfang.2006@yahoo.com.cn
(b) 1,4,9,16,25,36,49,64,81,100
0 1
5 9
4
30
16
91
3625
194
816449
100
385
Guoyongfang.2006@yahoo.com.cn
(c)要构造一棵最优 t叉树，可以如下进行：首先找出
t个最小的 w的值，设为 w1,w2,…,wt然后对 n-t+1
个权 w1+w2+… +wt,wt+1,…,wn求作一棵最优 t
叉树，并且将这棵最优树中的结点
w1+w2+… +wt 代之以 。
依次类推，由构造过程可知，除根外其它分枝点恰有 t个儿子。如果构造出来的树，根恰有 t个儿子，那么这棵树就是最优 t叉树。如果构造出来的树，根的儿子数目 k<t，那么在原来 n个权
w1,w2,…,wn中添加 (t-k)个 0，对于权 0,0,…,
0,w1,w2,…,wn按上法重新构造 t叉树，它能保证每个分枝点都有 t个儿子，这是最优 t叉树。
…w1 w2 wt
Guoyongfang.2006@yahoo.com.cn
定义 7-8.7 给定一个序列的集合,若没有一个序列是另一个序列的前缀,该序列集合称为前缀码,
定理 7-8.5 任意一棵二叉树的树叶可对应一个前缀码,
定理 7-8.6 任何一个前缀码都对应一棵二叉树,
前缀码问题
Guoyongfang.2006@yahoo.com.cn
例：图（ a）给出了与前缀码 {000,001,01,1}
对应的完全二叉树。图（ b）是删剪后得到的对应二叉树。
0 1
1
1 1
000 001
01
1
1 1 1000
0
0
0
(a) (b)
设有二进制序列 00010011011101001可译为,000,1,001,1,01,1,1,01,001。
Discrete Mathematics
郭永芳
guoyongfang.2006@yahoo.com.cn
Guoyongfang.2006@yahoo.com.cn
一、图定义 一个 图 是一个三元组 <V(G),E(G),φ G>,简记为
G＝ <V,E>，
7-1 图的基本概念其中：
1) V＝ {v1,v2,v3,…,vn}是一个非空集合,vi(i＝
1,2,3,…,n)称为 结点,简称 点,V为 结点集 ；
2) E＝ {e1,e2,e3,…,em}是一个有限的集合,ei(i＝
1,2,3,…,m)称为 边,E为 边集,E中的每个元素都有 V
中的结点对（有序偶或无序偶）与之对应。
Guoyongfang.2006@yahoo.com.cn
图的术语
若边 e与结点无序偶 (u,v)相对应，则称边 e为 无向边,记为 e＝ (u,v)，这时称 u,v是边 e的两个 端点 ；
2) 若边 e与 结点 有偶 <u,v>相对应,则称边 e为 有向边
(或 弧 ),记为 e＝ <u,v>,这时称 u是边 e的 始点 (或弧尾 ).v是边 e的 终点 (或 弧头 ),统称为 e的 端点 ；
3) 在一个图中,关联结点 vi和 vj的边 e,无论是有向的还是无向的,均称边 e与结点 vI和 vj相关联,而 vi和
vj称为 邻接点,否则称为 不邻接的 ；
Guoyongfang.2006@yahoo.com.cn
续：
续：
4) 关联于同一个结点的两条边称为 邻接边 ；
5) 图中关联同一个结点的边称为 自回路 (或 环 )；
6) 图中不与任何结点相邻接的结点称为 孤立结点 ；
7) 仅由孤立结点组成的图称为 零图 ；
8) 仅含一个结点的零图称为 平凡图 ；
9) 含有 n个结点,m条边的图称为 (n,m)图 ；
Guoyongfang.2006@yahoo.com.cn
续：续：
每条边都是无向边的图称为 无向图 ；
每条边都是有向边的图称为 有向图 ；
有些边是无向边,而另一些是有向边的图称为 混合图 。
在有向图中,两个结点间 (包括结点自身间 )若有同始点和同终点的几条边,则这几条边称为 平行边,在无向图中,
两个结点间 (包括结点自身间 )若有几条边,则这几条边称为 平行边,两结点 vi,vj间相互平行的边的条数称为边 (vi，
vj)或 <vi,vj>的 重数 ；
Guoyongfang.2006@yahoo.com.cn
续：
14)含有平行边的图称为 多重图 。 非多重图称为 线图 ；无环和平行边的图称为 简单图 。
Guoyongfang.2006@yahoo.com.cn
(a)
例：
(b)
(c) (d)
例：
Guoyongfang.2006@yahoo.com.cn
二、度数定义 在无向图 G＝ <V,E>中，与结点 v(v?V)关联的边的条数，
称为该结点的 度数,记为 deg(v)；
二、度数定义 在有向图 G＝ <V,E>中,以结点 v(v?V)为始点引出的边的条数,称为该结点的 引出度数,简称 出度,记为 deg+(v)；
以结点 v(v?V)为终点引入的边的条数,称为该结点的 引入度数,简称 入度,记为 deg-(v)；而结点的出度和入度之和 称 为 该 结 点 的 度数,记为 deg(v),即 deg(v) ＝
deg+(v)+deg-(v)；
δ(G)最小度,Δ(G)最大度定义 在图 G＝ <V,E>中,对任意结点 v?V,若度数 deg(v)为奇数,则称此结点为 奇度数结点,若度数 deg(v)为偶数,则称此结点为 偶度数结点 。
Guoyongfang.2006@yahoo.com.cn
例：
deg(v1)＝ 3,deg+(v1)＝ 2,deg-(v1)＝ 1；
deg(v2)＝ 3,deg+(v2)＝ 2,deg-(v2)＝ 1；
deg(v3)＝ 5,deg+(v3)＝ 2,deg-(v3)＝ 3；
deg(v4)＝ deg+(v4)＝ deg-(v4)＝ 0；
deg(v5)＝ 1,deg+(v5)＝ 0,deg-(v5)＝ 1；
例：
Guoyongfang.2006@yahoo.com.cn
定理定理
1.在无向图 G＝ <V,E>中,则所有结点的度数的总和等于边数的两倍,即：；m2)vd e g (
Vv
，m)v(d e g)v(d e g
VvVv
2,在有向图 G＝ <V,E>中，则所有结点的出度之和等于所有结点的入度之和，所有结点的度数的总和等于边数的两倍，即：
。m2)v(d e g)v(d e g)vd e g (
VvVvVv
Guoyongfang.2006@yahoo.com.cn
定理定理 在图 G＝ <V,E>中，其 V＝ {v1,v2,v3,…,vn},E＝
{e1,e2,……,em}，度数为奇数的结点个数为偶数。
证明 V1＝ {v|v?V且 deg(v)＝奇数 },V2＝ {v|v?V且
deg(v)＝偶数 }。显然,V1∩V 2＝ Φ，且 V1∪V 2＝ V，于是有：
。m2)vd e g ()vd e g ()vd e g (
21 VvVvVv
由于上式中的 2m和偶度数结点度数之和均为偶数，因而也为偶数。于是 |V1|为偶数 (因为 V1中的结点 v之 deg(v)
都为奇数 )，即奇度数的结点个数为偶数。■
Guoyongfang.2006@yahoo.com.cn
三、完全图定义 在图 G＝ <V,E>中，若所有结点的度数均有相同度数 d，则称此图为 d次正则图。
定义 一个 (n,m)(n?2)的简单无向图，若它为 n-1次正则图，则称该 (n,m)图为 无向简单完全图,简称 完全图,记为 Kn。
有向完全图定理 设无向完全图 G有 n个顶点，则 G有 n(n-1)/2条边。
Guoyongfang.2006@yahoo.com.cn
例：
例,如图 (a),(b),(c),(d)所示，它们分别是无向的简单完全图 K3,K4,K5和有向的简单完全图 K3。
Guoyongfang.2006@yahoo.com.cn
定义 设有图 G＝ <V,E>和图 G1＝ <V1,E1>，若 G和 G1满足
：
若 V1?V,E1?E，则称 G1是 G的 子图,记为 G1?G；
若 G1?G，且 G1?G(即 V1?V或 E1?E)，则称 G1
是 G的 真子图,记为 G1?G；
四、子图和补图
Guoyongfang.2006@yahoo.com.cn
定义 若 V1＝ V,E1?E，则称 G1是 G的 生成子图,记为 G1?G；
定义 设 G＝ <V,E>为具有 n个结点的简单图,从完全图 Kn中删去 G中的所有的边而得到的图称为 G
的 补图 (或 G的 补 ),记为 。
四、子图和补图
G
Guoyongfang.2006@yahoo.com.cn
定义 Ｇ＝ <Ｖ,Ｅ >是图,Ｇ ’ ＝ <Ｖ ’,Ε ’>是
Ｇ的子图,Ｅ,＝Ｅ－Ｅ ’,Ｖ,是Ｅ,中边所关联的所有顶点集合,则Ｇ,＝ <Ｖ,,Ｅ,>称为
Ｇ ’ 关于Ｇ的 相对补图 。
关于完全图的子图的补图称为此子图的绝对补图 。
相对补图
Guoyongfang.2006@yahoo.com.cn
例：
例,在下图中，给出了图 G以及它的真子图 G’和生成子图 G’’。
Guoyongfang.2006@yahoo.com.cn
例：
例,在下图 (a),(b),(c),(d)中,(a)与 (b)
是互为补图； (c)和 (d)是互为补图。
Guoyongfang.2006@yahoo.com.cn
7-2 路与回路一、路定义 给定图 G=〈 V,E〉,设 v0,v1,…,vn∈ V,e1，
e2,…,en∈ E,其中 ei是关联结点 vi-1,vi的边,交替序列 v0e1v1e2… envn称为联结 v0到 vn的路 。
v0,vn分别为该路的起点和终点,统称为路的 端点 。
路中边的条数称为该 路的长度 。
此时,若 v0＝ vn,则该路称为 回路 。
Guoyongfang.2006@yahoo.com.cn
若路中所有边全不相同，则称此路为一条 迹 ；
若路中所有结点全不相同，则称此路为 通路 。
若回路中除 v0＝ vn以外所有结点全不相同，则称此回路 圈。 （闭的通路）
在简单图中一条路 v0e1v1e2… envn，由它的结点序列 v0v1 … vn确定,所以简单图的路,由可由其结点序列 [v0v1 … vn]表示。在有向图中,结点数大于 1的一条路可由边序列 [e1e2 … en ]表示。
续：
Guoyongfang.2006@yahoo.com.cn
定理定理 在一个具有 n个结点的图中，如果从结点 vj到结点 vk存在一条路，则从结点 vj到结点 vk必 存在一条不多于 n-1条边的路。
证明 如果从结点 vj到结点 vk存在一条路,则该路上的结点序列是 [vj… vi… vk],如果在这路上有 l条边,
则序列中必有 l+1个结点,若 l>n-1,则必有结点 vs，
它 在 序 列 中 不 止 一 次 出 现,即 必 有 序 列
[vj… vs… vs… vk],在路中去掉从 vs到 vs的这些边,仍然得到一条从结点 vj到结点 vk的路,但此路比原来的路的边数要少 。 如此重复进行下去,必得到一条从结点 vj到结点 vk不多于 n-1条边的路 。
Guoyongfang.2006@yahoo.com.cn
定理推论 G中，如果从结点 vj到结点 vk
存在一条路，则必存在一条从 vj到 vk而 长度小于 n的通路。
Guoyongfang.2006@yahoo.com.cn
二、无向图的连通性定义 设 G＝ <V,E>是一个图，对 vi,vj?V，从 vi到 vj
如存在一条 路，则称 结点 vi和 vj是连通的 。
定义 设 G＝ <V,E>是一个无向图，若 G中任意两个结点之间都是连通的，则称该无向图 G是一个 无向连通图,否则，则称 G是一个 非连通图 (或 分离图 )。
定义 设 G＝ <V,E>是一个无向图，该无向图 G中的每个连通的划分块称为 G的一个 连通分支,用 W(G)表示 G
中的 连通分支数 。无向图 G＝ <V,E>是连通图当且仅当 W(G)＝ 1。
Guoyongfang.2006@yahoo.com.cn
G1是连通图,W(G1)＝ 1；
G2是非连通图，且 W(G2)＝ 4。
例：
例：
Guoyongfang.2006@yahoo.com.cn
定义 设无向图 G=〈 V,E〉 为连通的,若有结点集
V1是 V的真子集,使得图 G删除了 V1所有结点后,
所得的子图是不连通的,而删除了 V1的任意真子集后,所得的子图仍然是连通图 。 则称集合 V1为图 G的 点割集 。 若某一结点就构成点割集,则称该结点为 割点 。
这样,一个连通图,删除它的一个点割集后,将分成两个或多于两个连通分支 。
割点
Guoyongfang.2006@yahoo.com.cn
若 G不是完全图,我们定义 k(G)=min{| V1 |
|V1是 G的点割集 }为 G的点连通度 (或连通度 )。
连通度 k(G)是为了产生一个不连通图需要删去的点的最少数目 。 于是,一个不连通图的连通度等于 0,存在着割点的连通图的连通数为 1。
完全图 Kp中删去任何 m个 (m＜ p-1)点后仍然连通,
但是删去了 p-1个结点后产生一个平凡图,故定义 k(Kp )= p-1。
割点
Guoyongfang.2006@yahoo.com.cn
定义 设无向图 G=〈 V,E〉 为连通的,若有边集 E1是 E
的真子集,使得图 G删除了 E1所有边后,所得的子图是不连通的,而删除了 E1的任意真子集后,所得的子图仍然是连通图 。 则称集合 E1为图 G的 边割集 。
若某一边构成边割集,则称该边为 割边 (或桥 )。
G的割边也就是 G中的一条边 e使得 W(G-e)＞
W(G)。与点连通度相似，我们定义非平凡图 G的边连通度为,λ (G)=min{| E1 ||E1是 G的边割集 }，边连通度 λ (G)是为了产生一个不连通需要删去边的最少数目。对于 平凡图 λ (G)=0，此外一个不连通图也有
λ (G)=0。
割边
Guoyongfang.2006@yahoo.com.cn
定理 对于任何一个图 G =〈 V,E〉,有
k(G)≤λ(G)≤δ(G)
证明 若 G不连通,则 k(G)=λ(G)=0,故上式成立 。
若 G连通,
① 证明 λ(G)≤δ(G)。 若 G是平凡图,则 λ(G)=0≤δ(G),若
G是非平凡图,则因每一结点的所有关连边必含一个边割集,故 λ(G)≤δ(G)。
定理
Guoyongfang.2006@yahoo.com.cn
② 再证 k(G)≤λ(G)
.设 λ(G)=1,即 G有一割边,显然此时 k(G)=1,上式成立 。
.设 λ(G)≥2,则必可删去某 λ(G)条边,使 G不连通,而删除 λ(G)-1条边,它仍然连通,而且有一条桥 e=(u，
v)。 对 λ(G)-1条边中每一条边都选取一个不同于 u，
v的端点,将这些端点删去必至少删去 λ(G)-1条边 。
若这样产生的图是不连通的,则 k(G)≤λ(G)-1≤λ(G)，
若这样产生的图是连通的,则 e=(u,v)仍然是桥,
此时再删去 u,v,就必产生一个不连通图,故
k(G)≤λ(G)。
由此得 k(G)≤ λ (G)≤ δ (G)。
续：
Guoyongfang.2006@yahoo.com.cn
定理 一个连通无向图 G =〈 V,E〉 的某一点 v是图 G的割点的充分必要条件是存在两个结点 u
和 w,使得结点 u和 w的每一个路都通过结点
v。
定理
Guoyongfang.2006@yahoo.com.cn
三、有向图的连通性三、有向图的连通性定义 设 G＝ <V,E>是一个有向图，对 vi,vj?V，从
vi到 vj如存在一条 路，则称 结点 vi到 vj是可达的。
在有向图中，如从 vi到 vj可达，但从 vj到 vi则不一定是可达的。
为此，若将可达性看成是图 G＝ <V,E>的结点集合 V上的二元关系的话,对有向图来说，该可达性关系仅是自反的、传递的关系,但不一定是对称的关系、
也不一定是反对称的关系。
Guoyongfang.2006@yahoo.com.cn
定义定义 在图 G＝ <V,E>中，对?vi,vj?V，如果从 vi
到 vj存在路，则称长度最短的路为从 vi到 vj的 短程线,从 vi到 vj的短程线的长度称为从 vi到 vj的 距离,记为 d(vi,vj)。
d(vi,vj)满足下列性质：
d(vi,vj)?0；
d(vi,vi)＝ 0；
d(vi,vk)+d(vk,vj)? d(vi,vj)；
d(vi,vj)＝? (当 vi到 vj不存在路时 )。
Guoyongfang.2006@yahoo.com.cn
在 (a)中有：
d(v2,v1)＝ 1,d(v1,v2)＝ 2，
d(v3,v1)＝ 2,d(v1,v3)＝ 4；
在 (b)中有：
d(v1,v3)＝ 2,d(v3,v7)＝ 3,d(v1,v7)＝
4。
例：
例：
Guoyongfang.2006@yahoo.com.cn
定义
设 G＝ <V,E>是一个有向图，若略去 G中所有有向边的方向后所得到的无向图 G1是一个无向连通图，则称该有向图 G是一个 弱连通图 ；
设 G＝ <V,E>是一个有向图，若 G中任意两个结点之间至少单方向可达的，则称该有向图 G是一个 单侧连通图 ；
设 G＝ <V,E>是一个有向图，若 G中任意两个结点之间都是相互可达的，则称该有向图 G是一个 强连通图 。
定义
Guoyongfang.2006@yahoo.com.cn
G1是弱连通图；
G2是单侧连通图 (当然它也是弱连通图 )；
G3是强连通图 (当然它也是弱连通图、单向连通图 )。
例：
例：
Guoyongfang.2006@yahoo.com.cn
定理定理 一个有向图 G是强连通图当且仅当 G中有一个回 路，它至少包含每一个结点一次。
证明,,?” G中有一个回路，它至少包含每个结点，则
G中任何两个结点间都是相互可达的，故 G为强连通图。
,?” G是强连通图，则任意两个结点之间都是相互可达的，设 G＝ <V,E>,V＝ {v1,v２,v３,…,vｎ }，则 v1到 v2可达，
v2到 v3可达,v3到 v4可达,……,vｎ -１ 到 vｎ 可达,vn到 v1可达，
由此可得到一条回路 (v1,v２,v３,……,vｎ,v1)，它至少包含每个结点一次。■
Guoyongfang.2006@yahoo.com.cn
定义定义 设 G＝ <V,E>是一个有向图,G1＝ <V1，
E1>是 G的子图,若 G1是弱连通图 (单侧连通图，强连通图 )，且没有包含 G1的更大的子图是弱连通图 (单侧连通图，强连通图 )，
则称 G1是 极大弱连通子图 (极大单侧连通子图，极大强连通子图 )或称为 弱分图 (单侧分图，强分图 )。
Guoyongfang.2006@yahoo.com.cn
例,如上图 (a)所示，有：
例：
由 {v２ },{v６ },{v1,v３,v４,v５,v７ }所导出的子图构成了该图的强分图；
由 {v1,v２,v３,v４,v５,v7},{v1,v３,v４,v5,v６,v７ }所导出的子图构成了该图的单侧分图；
(a)图本身就是一个弱分图。
Guoyongfang.2006@yahoo.com.cn
例：
如上图 (b)所示，有：
由 {v1},{v２ },{v3},{v4},{v5,v6,v７ }所导出的子图构成了该图的强分图；
由 {v1,v２,v３ },{v1,v3,v4},{v５,v６,v７ }所导出的子图构成了该图的单侧分图；
由 {v1,v２,v３,v４ },{v５,v６,v７ }所导出的子图构成了该图的弱分图。
Guoyongfang.2006@yahoo.com.cn
定理
在有向图 G＝ <V,E>，它的每一个结点必然位于且仅位于一个强分图中。
定理
Guoyongfang.2006@yahoo.com.cn
证：
①,对?v?V，令 S是 G中所有与 v相互可达的结点集，则有 v?S，由于 v与 S中的一切结点相互可达，所以，由可达性具有传递性知,S
中的一切结点之间是相互可达的，即 S是 G的一个强分图，所以,v
位于一个强分图中；
②,设 v还位于另一个强分图 T中，则由 S中的每个结点都与 v相互可达，且 T中的每个结点也都与 v相互可达，所以，由可达性具有传递性知,S中的一切结点与 T中的一切结点之间是相互可达的，即由
S∪T 就构成了一个更大的强连通的子图，这就与 S,T都是两个强分图矛盾，故 G的每个结点仅位于一个强分图中。■
Guoyongfang.2006@yahoo.com.cn
7-3 图的矩阵表示一,邻接矩阵设 G＝ <V,E>是一个简单图,V＝ {v1,v2,…,vn}，
E＝ {e1,e2,…,en}，则 n阶方阵 A(G)＝ (aij)n?n称为 G
的 邻接矩阵 。其中：
EvvEvv0
EvvEvv1
a
jiji
jiji
ij ），或（，，
），或（，，
由邻接矩阵的定义知：其矩阵的元素是一个二值元素，所以，又称该矩阵为 位矩阵 或 布尔矩阵 。
Guoyongfang.2006@yahoo.com.cn
例：
邻接矩阵,。，
0100
1100
0101
0110
)G(A
0011
0110
1101
1010
)G(A 21
例：
Guoyongfang.2006@yahoo.com.cn
性质设 G＝ <V,E>是一个简单图，则有：
1) 如 aii＝ 1,则结点 vi有环,否则 vi无环。 (i?{1,2,3,…,n})
2) 如 aij＝ 1,则从结点 vi到结点 vj有边。 (i,j?{1,2,3,…,n})
3) 如对?i,j?{1,2,3,…,n},都有 aij＝ 0，则此时图 G是一个零图 。
4) 如对?i,j?{1,2,3,…,n},都有 aij＝ 1(i?j),aii＝ 0，则此时图 G是一个完全图。
5) 如 G是一个无向简单图,则对任意 vi?V，都有：
，
n
k
ki
n
k
iki aav
11
)d e g (
n
i
n
k
ik
n
i
n
i
n
k
iki aav
1 11 1 1
)()d e g ( ；
Guoyongfang.2006@yahoo.com.cn
性质如 G是一个有向简单图，则对任意 vi?V，都有：
，）（，）（
n
1k
kii
n
1k
iki avd e gavd e g
，）（）（）（）（
n
1k
kiik
n
1k
ki
n
1k
ikiii aaaavd e gvd e gvd e g；）（）（
n
1i
n
1i
n
1k
kiiki aavd e g
Guoyongfang.2006@yahoo.com.cn
性质
6) 令 B＝ (bij)＝ A2＝ A× A＝ (aij(2))n?n，则有：
n
1k
kjik
)2(
ijij aaab
此时,bij表示从 vi到 vj长度为 2的路数目，如 bij＝
0，则无长度为 2的路，而 bii给出了经过 vi的长度为 2的回路数目；
Guoyongfang.2006@yahoo.com.cn
性质
7) 令 C＝ (cij)＝ Am＝ A× A× … × A＝ (aij(m))n?n，
则有：
n
1k
kj
)1m(
n
1k
)1m(
ik
)m(
ij aaaaac ikkjij
此时,cij表示从 vi到 vj长度为 m的数目，如 cij＝ 0，
则无长度为 m的路，而 cii给出了经过 vi的长度为 m
的回路数目。
Guoyongfang.2006@yahoo.com.cn
性质如下图,V＝ {v1,v2,v3,v4,v5}，其邻接矩阵 A,A2、
A3,A4
。，
，，
3303
3303
0090
3303
A
0030
0030
3303
0030
A
1101
1101
0030
1101
A
0010
0010
1101
0010
A
43
2
上面图中结点的度数和两结点间长度为 k的路的条数。
Guoyongfang.2006@yahoo.com.cn
定理定理 设 A(G)为图 G的邻接矩阵,则 (A(G))l中的 i
行 j列元素等于 G中联结 vi与 vj的长度为 l的路的数目 。
Guoyongfang.2006@yahoo.com.cn
定理例,给定一图 G=〈 V,E〉 如图所示 。
从下面的矩阵中我们可以看到一些结论,
如 v1与 v2之间有两条长度为 3的路,结点 v1与 v3之间有一条长度为 2的路,在结点 v2有四条长度为 4的回路 。
10000
01000
00101
00020
00101
01000
10000
00010
00101
00010
2
AA
10000
01000
00202
00040
00202
01000
10000
00020
00202
00020
43
AA
Guoyongfang.2006@yahoo.com.cn
二、可达性矩阵设 G＝ <V,E>＝ (n,m)是一个简单图,V＝
{v1,v2,v3,…,vn}，定义,Rn＝ (rij)n*n＝ A
+A2+A3+…… +An，
则 rij表明了从结点 vi到 vj长度为 1至 n的所有路数目之和。
rij＝ 0，则表明从结点 vi到 vj是不可达的；
rij?0，则表明从结点 vi到 vj至少有长度为 m(1?m
n)的通路，即此时从结点 vi到 vj是可达的。
Guoyongfang.2006@yahoo.com.cn
二、可达性矩阵
，否则的通路至少存在一条非零长度到，
0
vv1
p jiij (i,j＝ 1,2,3,……,n)
则称矩阵 P为图 G的 可达性矩阵 。
定义 设 G＝ <V,E>＝ (n,m)是一个简单图,V＝ {v1,v2,v3,…,vn}，定义一个 n阶方阵 P＝ (pij)n*n，其中：
Guoyongfang.2006@yahoo.com.cn
图的矩阵表示由矩阵 Rn可知,如 rij＝ 0，则表明从结点 vi
到 vj是不可达的；
rij?0，则表明从结点 vi到 vj至少有长度为
m(1?m?n)的路，即此时从结点 vi到 vj是可达的。
所以有：
pij＝ 0? rij＝ 0，
pij＝ 1? rij?0，
(i,j＝ 1,2,3,……,n)。
Guoyongfang.2006@yahoo.com.cn
例,
，，
0010
1111
1012
1100
A
0001
1011
1100
0010
A 2
。，
1012
3233
3222
1121
A
1100
2122
1121
1012
A 43
，
2123
7477
6455
3253
AAAAR 4324 。
1111
1111
1111
1111
P
Guoyongfang.2006@yahoo.com.cn
利用布尔求乘和布尔求和的运算直接求可达性矩阵
P＝ A?A(2)?A(3)?...?A(n)
A(m)＝ A?A?A?...?A (m＝ 1,2,3,… n)
利用布尔求乘和布尔求和的运算直接求可达性矩阵
Guoyongfang.2006@yahoo.com.cn
例：
例,利用邻接矩阵的布尔运算求可达性矩阵。
，,）（
0010
1111
1011
1100
A
0001
1011
1100
0010
A 2
，,）（）（
1011
1111
1111
1111
A
1100
1111
1111
1011
A 43
。）（）（）（
1111
1111
1111
1111
A......AAAP n32
Guoyongfang.2006@yahoo.com.cn
三：完全关联矩阵三：完全关联矩阵定义 给定无向图 G,令 v1,v2,…,vp和 e1,e2,…,eq分别记为 G的结点和边,则矩阵 M(G)=(mij),其中称 M(G)为完全关联矩阵。
ji
ji
ij ev
ev
m 不关联若关联若
,0
,1
Guoyongfang.2006@yahoo.com.cn
例：
Guoyongfang.2006@yahoo.com.cn
性质从关联矩阵中可以看出图形的一些性质：
⑴图中每一边关联两个结点，故 M(G)的每一列只有两个 1。
⑵每一行元素的和数对应于结点的度数。
⑶一行中的元素全为 0，其对应的结点为孤立点。
⑷两个平行边其对应的两列相同。
⑸同一图当结点或边的编序不同，其对应 M(G)仅有行序、列序的差别。
Guoyongfang.2006@yahoo.com.cn
定义定义 给定简单有向图
G=〈 V,E〉,V={v1,v2,… vp},E={e1,e2,… eq},
p× q阶矩阵 M(G)=(mij),其中称 M(G)为 G的完全关联矩阵 。
ji
ji
ji
ij
evG
evG
evG
m
不关联中在的终点是中在的起点是中在
,0
,1
,1
Guoyongfang.2006@yahoo.com.cn
例：
Guoyongfang.2006@yahoo.com.cn
7-4 Euler图与 Hamilton图一,Euler图哥尼斯堡七桥问题：
Guoyongfang.2006@yahoo.com.cn
例 (蚂蚁比赛问题 )
解,仅有两个度数为奇数的结点 b,c,因而存在从 b到 c的欧拉路,蚂蚁乙走到 c只要走一条欧拉路,边数为 9条 。 而蚂蚁甲要想走完所有的边到达 c,至少要先走一条边到达 b,再走一条欧拉路,因而它至少要走 10条边才能到达 c,所以乙必胜 。
甲、乙两只蚂蚁分别位于如下图 中的结点 a,b处，并设图中的边长度是相等的。甲、乙进行比赛：从它们所在的结点出发，走过图中的所有边最后到达结点 c处。如果它们的速度相同，
问谁先到达目的地？
Guoyongfang.2006@yahoo.com.cn
1.无向的 Euler图定义 给定 G是一个无孤立结点的无向图,若存在一 条路 (回路 ),经过图中每边一次且仅仅一次,
则称此路 (回路 )为该图的一条 欧拉路 (回路 )。 具有欧拉回路的图称为 欧拉图 。
如何判断一个图是否是欧拉图或存在欧拉路呢？
Guoyongfang.2006@yahoo.com.cn
判断欧拉图及欧拉路的方法定理无向图 G＝ <V,E>具有一条欧拉路当且仅当 G
是连通的，且仅有零个或者两个奇度数结点。
无向图 G＝ <V,E>是欧拉图当且仅当 G是连通的，且 G的所有结点的度数都为偶数。
Guoyongfang.2006@yahoo.com.cn
证明
1)、若 G＝ (1,0)是一个平凡图，则定理显然成立。
下面讨论 G是非平凡图的情况。
“?”设 G具有一条 Euler路 L。
① 设该欧拉路 L＝ v0e1v1e2v2e3…… ekvk。即从 v0出发，经过结点 v1，
v2,…… vk-1，边 e1,e2…… ek到达 vk，其中的结点可以重复出现，
但边不重复，并且 L中的边是包括了 G中所有的边。由于 G中无孤立结点，因而 L经过了 G中的所有结点，所以 G是连通的。
② 对于欧拉路 L的任意非端点的结点 vi，在 L中每出现 vi一次，都关联着 G中的两条边，而当 vi又重复出现时，它又关联着 G中的另外的两条边，由于在通路 L中边不可能重复出现，因而 vi每出现一次，
都将使得结点 vi的度数增加 2度，若 vi在路中重复出现 j次，则
deg(vi)＝ 2j。
Guoyongfang.2006@yahoo.com.cn
证明 (续 1)
。
若端点 v0?vk，设 v0,vk在通路中作为非端点分别出 现
j1次和 j2次,v0,vk每出现一次，都将使得结点 v0,vk的度数增加 2度，而 v0,vk作为端结点时，仅仅只出现一次，且在其
v0,vk的度数上只增加 1度，则 v0,vk的总度数分别是：
deg(v0)＝ 2j1+1，
deg(vk)＝ 2j2+1。
综上所述，即 G仅仅只有两个奇度数结点，即两个端结点 v0,vk的度数为奇数。
若端点 v0＝ vk，则 G中的所有结点在通路中都可看成为非端点，由上可知，每个结点的度数都是偶数，即 G中仅有零个奇度数结点。
Guoyongfang.2006@yahoo.com.cn
“?”构造性证明 。
证明 (续 2)
若有两个奇度数结点 。 则我们从两个度数为奇数的结点之一开始构造一条欧拉路,以每条边最多经过一次的方式通过图中的边 。
对于度数为偶数的结点,通过一条边进入这个结点,总可以通过一条未经过的边离开这个结点,因此,这样的构造过程一定以到达另一个度数为奇数的结点而告终 (若无度数为奇数的结点,则以回到原出发点而告终 )。 如果图中所有的边已用这种方式经过了,显然这就是所求的欧拉路 。 如果这个图中不是所有的边都经过了,我们将去掉已经过的边,得到一个由剩余的边组成的子图,这个子图的所有结点的度数均为偶数 。 因为原来的图是连通的,因此,这个子图必与我们已经过的路在一个或多个结点相接 。
Guoyongfang.2006@yahoo.com.cn
证明 (续 3)
由这些结点中的一个开始我们再通过边构造路,因为结点的度数全为偶数，因此，这条路一定最终回到起点。我们将这条回路加到已构造好的路中间组合成一条路。如有必要，
这一过程重复下去，直到我们得到一条通过图中的所有边的路，
即欧拉路。
上述过程即可。
2)、该结论直接是 1)的推广。■
Guoyongfang.2006@yahoo.com.cn
例由定理容易看出,a) 是欧拉图；
b) 不是欧拉图，但存在欧拉路；
c) 即不是欧拉图，也不存在欧拉路。
Guoyongfang.2006@yahoo.com.cn
2.一笔画问题对于上图，有 图 (a)是能一笔画并且能回到出发点的，
图 (b)也能一笔画但不能回到出发点的。
Guoyongfang.2006@yahoo.com.cn
3.有向的 Euler图定义 给定 G是一个无孤立结点的有向图，若存在一 条单向路 (回路 )，经过图中每边一次且仅仅一次，则称此单向路 (回路 )为该图的一条 单向欧拉路 (回路 )。具有单向欧拉回路的图称为 欧拉图 。
如何判断一个有向图是否是欧拉图或存在单向欧拉路呢？
Guoyongfang.2006@yahoo.com.cn
判断欧拉图及欧拉通路的方法定理有向图 G＝ <V,E>具有一条单向欧拉路当且仅当 G是连通的，且除了两个结点以外，其余结点的入度等于出度，而这两个例外的结点中，一个结点的入度比出度大 1，另一个结点的出度比入度大 1。
有向图 G＝ <V,E>具有一条欧拉回路 (即是欧拉图 )当且仅当 G是连通的，且 G的所有结点的入度都等于出度。
Guoyongfang.2006@yahoo.com.cn
例图 a)存在一条单向的欧拉路,v3v1v2v3v4v1；
图 (b)中存在单向欧拉回路 v1v2v3v4v1v3v1，因而 (b)是欧拉图；
图 (c)中有单向欧拉回路 v1v2v3v4v5v6v7v8v2v4v6v8v1因而 (c)
是欧拉图。
Guoyongfang.2006@yahoo.com.cn
已知 a,b,c,d,e五个人中，会讲的语言分别是：
a,英语、汉语、德语 b,俄语、英语
c,汉语、英语、法语
d：汉语、俄语 e,德语、法语请问怎样将他们的作为安排在圆桌旁，使得每个人都能与他身边的人交谈？
Guoyongfang.2006@yahoo.com.cn
二、哈密尔顿图周游世界问题定义 给定 G是一个无孤立结点的无向图，若存在一条路
(回路 )，经过图中每个结点一次且仅仅一次，则称此路 (回路 )为该图的一条 哈密尔顿路
(回路 )。具有哈密尔顿回路的图称为 哈密尔顿图 。
Guoyongfang.2006@yahoo.com.cn
哈密尔顿图的判定定理 (必要条件 ) 若图 G=〈 V,E〉 具有汉密尔顿回路，
则对于结点集 V的每一个非空子集 S均有 W(G－ S)≤|S|
成立。其中 W(G－ S)是 G－ S中连通分支数。
Guoyongfang.2006@yahoo.com.cn
哈密尔顿图的判定证明 设 C是 G的一条汉密尔顿回路,则对于 V
的任何一个非空子集 S在 C中删去 S中任一结点
a1,则 C－ a1是连通非回路,若删去 S中的另一个结点 a2,则 W(C－ a1－ a2)≤2,由归纳法得知 W(C－ S)≤|S|
同时 C－ S是 G－ S的一个生成子图,因而 W(G
－ S)≤W(C－ S)
所以 W(G－ S)≤ |S|
Guoyongfang.2006@yahoo.com.cn
例在图 (a)中，虽然对任意的结点集合 V1,都满足 W(G-V1)?|V1|，
但它仍然不是哈密尔顿图。
在图 (b)中，任意两个结点的度数之和为 4，结点数为 6，即有 4?6，，但它仍然是 哈密尔顿图。
Guoyongfang.2006@yahoo.com.cn
哈密尔顿图的判定定理 (充分条件 ) 设 G具有 n个结点的简单图，如果 G中每一对结点的度数之和大于等于 n-
1，则在 G中存在一条汉密尔顿路。
Guoyongfang.2006@yahoo.com.cn
哈密尔顿图的判定证明 我们首先证明 G是连通的。若 G有两个或更多互不连通的分图，设一个分图有 n1个结点，任取一个结点 v1，设另一个分图有 n2个结点，任取一个结点 v2，
因为 d(v1)≤n1－ 1,d(v2)≤n2－ 1，故 d(v1)+ d(v2)
≤n1+ n2－ 2＜ n－ 1，这表明与题设矛盾，故 G必连通。
其次，我们从一条边出发构成一条路，证明它是汉密尔顿路。
Guoyongfang.2006@yahoo.com.cn
哈密尔顿图的判定设在 G中有 p－ 1条边的路,p＜ n，它的结点序列为 v1，
v2,…,vp。如果有 v1或 vp邻接于不在这条路上的一个结点，我们可立即扩展这条路，使它包含这一个结点，从而得到 p条边的路。否则,v1和 vp都只能邻接于这条路上的结点，我们证明在这种情况下，存在一条回路包含结点 v1,v2,…,vp。若 v1邻接于
vp，则 v1,v2,…,vp,v1即为所求的回路。假设与 v1邻接的结点集是 {vl,vm,…,vj,…,vt}(k个 )，这里 2≤l,m,…,
t≤p-1，如果 vp是邻接于 vl-1,vm-1,…,vj-1,…,vt-1中之一，
譬如说 vj-1，如图 (a)所示,v1v2v3… vj-1vpvp-1… vjv1是所求的包含结点的回路 v1,v2,…,vp。
Guoyongfang.2006@yahoo.com.cn
哈密尔顿图的判定如果 vp不邻接于 vl-1,vm-1,…,vj-1,…,vt-1中任一个，则
vp至少邻接于 p－ k－ 1个结点,deG(vp)≤p-k-1,deG(v1) ≤k，
故 deG(vp)＋ deG(v1) ≤p-k-1+ k= p- 1＜ n-1，即 v1与 vp度数之和至多为 n-2，得到矛盾。
至此,我们有包含所有结点 v1,v2,…,vp的一条回路,因为 G
是连通的,所以在 G中必有一个不属于该回路的结点 vx与 v1，
v2,…,vp中的某一个结点 vk邻接,如图 (b)所示,于是就得到一条包括 p条边的路 (vx,vk,vk+1,vj-1,vp,vp-1,vj,v1,v2，
vk-1)。 如图 (c)所示,重复前述的构造方法,直到得到 n-1条边的路 。
Guoyongfang.2006@yahoo.com.cn
哈密尔顿图的判定
Guoyongfang.2006@yahoo.com.cn
哈密尔顿图的判定定理 (充分条件 ) 设图 G是具有 n个结点的简单图，如果
G中每一对结点的度数大于等于 n，则在 G中存在一条汉密尔顿回路。
证明 由上面定理可知必有一条汉密尔顿路,设为 v1v2… vn，
如果 v1与 vn邻接,则定理得证 。
如果 v1与 vn不邻接，假设 v1邻接于 {vi1,vi2,…,vik},
2≤ ij≤ n-1，可以证明 vn必邻接于 vi1-1,vi2-1,…,vik-1中之一。如果不邻接于中的任意一点，则 vn至多邻接于 n-k-1个结点，因而 d(vn)≤ n－ k－ 1，而 d(v1)= k，故 d(v1)+ d(vn) ≤ n
－ k－ 1+ k= n-1，与题设矛盾，所以必有汉密尔顿回路
v1v2… vj-1vnvn-1… vjv1，如图所示。
Guoyongfang.2006@yahoo.com.cn
哈密尔顿图的判定
Guoyongfang.2006@yahoo.com.cn
例判断图 (a),(b)所示的图中，是否存在哈密尔 顿回路或路。
Guoyongfang.2006@yahoo.com.cn
解
(a)、若图 (a)中存在哈密尔顿回路，则该回路 组成的图中任何结点的度数均为 2。而结点 1,2,3,4,5所关联的边均在回路中，于是在结点 a,b,c,d,e处均应将不与 1、
2,3,4,5关联的边删除，而要删除与结点 a,b,c,d、
e关联的其他边，这样一来，图就不连通了，因而图中不存在哈密尔顿回路。
(b)、在图 (b)中，任取一结点如 1用 A标记，所有与它邻接的结点用 B标记。继续不断地用 A标记所有邻接于 B的结点，
用 B标记所有邻接于 A的结点，直到所有结点都标记完为止。
如果图中有一条哈密尔顿路，那么它必交替地通过结点 A和结点 B，故而或者结点 A与结点 B数目相同，或者两者相差 1个。
然而图 (b)中有 3个结点标记为 A,5个结点标记为 B，它们相差两个，所以该图不存在哈密尔顿路。
Guoyongfang.2006@yahoo.com.cn
7-5 平面图例们三个分成一组，一元件组中的每一个元件都用导线与另一组之每个元件相接，如下图所示。 (其中：元件 ——
结点，边 ——导线 )
Guoyongfang.2006@yahoo.com.cn
1.平面图定义 设 G是一个无向图，若经过某种改画，能把
G
中的所有结点和边都画在一个平面上,使得任何两边除公共结点以外没有其他交叉点,则称 G为平面图 ；若 G无论如何改画,它们的边之间总有交叉现象出现,则称 G为 非平面图 。
Guoyongfang.2006@yahoo.com.cn
2．平面区域与图的面定义 设 G是一个连通的平面图，由图中的边所包围的其内部不包含图的结点和边的区域，称为 G
的一个 面,常常把面记为,r”；包围该面的诸边所构成的回路称为这个面的 边界,面 r的边界的回路的长度称为该面的 次数,记为 deg(r)。
称该面为 有限面,否则称该面为 无限面 。
一个平面图有且仅有一个无限面 。
Guoyongfang.2006@yahoo.com.cn
例如下图所示，该图中有六个结点，九条边，它们把平面图分成了五个面,
Guoyongfang.2006@yahoo.com.cn
定理一个有限平面图，面的次数之和等于其边数的两倍。
Guoyongfang.2006@yahoo.com.cn
欧拉公式定理 G＝ <V,E>是一个连通的平面图。
1) 若它有 v个结点,e条边,r个面，则有：
v-e+r＝ 2 (平面图的欧拉公式 )。
Guoyongfang.2006@yahoo.com.cn
证明
1)、对边 m进行归纳。
1．当 m＝ 1时，则仅有下面两种连通的平面图：
(a) (b)
对情况 (a)，有,m＝ 1,n＝ 2,r＝ 1，所以有,n-m+r＝ 2；
对情况 (b)，有,m＝ 1,n＝ 1,r＝ 2，所以有,n-m+r＝ 2；
2．设 m＝ k-1时成立，即有,nk-1-mk-1+rk-1＝ 2； (其中,nk-1,rk-1分别为对应的结点数和面数,mk-1＝ k-1。 )
3．当 m＝ k时，此时可将其看成是在 k-1条边的连通平面图上增加一条边，使她仍为连通平面图，此时有两种增加方法：
Guoyongfang.2006@yahoo.com.cn
证明 (续 1)
(a)、加一个新的结点 v，使得结点 v与图中的某一点
vj相连，此时有：
nk＝ nk-1+1； mk＝ mk-1+1； rk＝ rk-1。
所以有,nk-mk+rk＝ (nk-1+1)-(mk-1+1)+rk-1＝ 2。
(b)、若增加的一条边是连接的图中的两个结点 vi,
vj，此时有：
nk＝ nk-1； mk＝ mk-1+1； rk＝ rk-1+1。
所以有,nk-mk+rk＝ nk-1-(mk-1+1)+(rk-1+1)＝ 2。
右图给出了上述两种情况。
Guoyongfang.2006@yahoo.com.cn
证明 (续 2)
所以，当 m＝ k时，仍然成立。
由数学归纳法知：对任意一个 (n,m)连通平面图，都有,n-m+r＝ 2。
Guoyongfang.2006@yahoo.com.cn
定理设 G是一个有 v个结点 e条边的连通简单平面图，若 v大于等于 3，则 e小于等于 3v-6。
Guoyongfang.2006@yahoo.com.cn
以上定理可以用来证明某些图不是平面图。
证明 K5不是平面图。
证明对于 K5的任意边 e,K5 -e是平面图。
Guoyongfang.2006@yahoo.com.cn
设 G 为连通的简单平面图，结点数为 v，
面数为 r，证明：
（ 1）若 v≥3，则 r≤2v-4；
Guoyongfang.2006@yahoo.com.cn
K3,3图不是平面图，但 K3,3-e是平面图证明：在 6个结点 12条边的平面简单图中，
每个面用 3条边围成。
Guoyongfang.2006@yahoo.com.cn
与平面图有密切关系的一个图论的应用是图形的着色问题，这个问题最早起源于地图的着色，
一个地图中相邻的国家着以不同的颜色，那么至少需要多少种颜色？
一百多年前，英国格色里提出了用四种颜色即可对地图着色的猜想,1879年肯普给出了这个猜想的第一个证明，但到 1890年希伍德发现肯普证明是错的，但指出肯普的方法虽然不能证明地图着色用四种颜色就够了，但可证明用五种颜色就够了，此后四色猜想一直成为数学家感兴趣而未能解决的难题。
7-6对偶图与着色
Guoyongfang.2006@yahoo.com.cn
直到 1976年美国数学家阿佩尔和黑肯宣布：
他们用电子计算机证明了四色猜想是成立的。所以从 1976年以后，四色猜想就成了四色理论。
7-6对偶图与着色
Guoyongfang.2006@yahoo.com.cn
对偶图的概念定义 给定平面图 G＝ 〈 V,E〉,它有面 F1,F2,…,
Fn,若有图 G*＝ 〈 V*,E*〉 满足下述条件：
⑴ 对于图 G的任一个面 Fi,内部有且仅有一个结点
vi*∈ V*。
⑵ 对于图 G的面 Fi,Fj的公共边 ek,存在且仅存在一条边 ek*∈ E*,使 ek*＝ (vi*,vj*),且 ek*和 ek相交 。
⑶ 当且仅当 ek只是一个面 Fi的边界时,vi*存在一个环
ek*和 ek相交,则图 G*是图 G的对偶图 。
从这个定义看出,G*是 G的对偶图,则 G也是 G*的对偶图 。 一个连通平面图的对偶图也必是平面图 。
Guoyongfang.2006@yahoo.com.cn
图的同构五、图的同构例,如下图 (a),(b),(c),(d)所示，
图 (a)、图 (b)、图 (c)和图 (d)所表示的图形实际上都是一样的。
Guoyongfang.2006@yahoo.com.cn
定义定义 设有图 G＝ <V,E>和图 G1＝ <V1,E1>,如果存在双射函数 g:V→ V 1,使得 对 于任 意的 边 e＝ (vi,vj )
E(或 <vi,vj>?E)当且仅当 e1＝ (g(vi),g(vj))
E1(或 <g(vi),g(vj)>?E1) 则称 G和 G1同构,记为 G≌G 1。
同构的充要条件,两个图的结点和边分别存在一一对应，且保持关联关系。
Guoyongfang.2006@yahoo.com.cn
例：
例,如图 (a),(b)所示的两个图 G＝ <V,E>和 G1＝
<V1,E1>，证明 G≌G 1。
解,显然，定义函数 g,V→V 1，满足 g(vi)＝ vi’（ i＝ 1，
2,3,4,5），可以验证 g一定是一个满足定义的双射，
所以 G≌G 1。
Guoyongfang.2006@yahoo.com.cn
必要条件两个图同构的必要条件：
结点数目相同；
边数相同；
度数相同的结点数相同。
注意,这三个条件并不是充分条件。例如下面两个图满足这三个条件，但它们不同构。
Guoyongfang.2006@yahoo.com.cn
对偶图与着色定义 如果图 G的对偶图 G*同构于 G,则称 G是自对偶的 。
图 G的 正常着色 (或简称为着色 )是指对它的每一个结点指定一种颜色,使得没有两个相邻的结点有同一种颜色 。 如果图 G在着色时用 n种颜色,我们称 G为 n-色 的 。
对于图 G着色时,需最少颜色数称为 着色数,记作 x(G)。
Guoyongfang.2006@yahoo.com.cn
对偶图与着色可用 韦尔奇 ·鲍威尔法 (Welch Powell)对图 G进行着色,
其方法是：
⑴ 将图 G的结点按照度数的递减次序进行排列 。 (这种排列可能并不是唯一的,因为有些点有相同的度数 )。
⑵ 用第一种颜色对第一点进行着色,并且按排列次序,
对与前面着色点不邻接的每一点着上同样的颜色 。
⑶ 用第二种颜色对尚未着色的点重复 ⑵,用第三种颜色继续这种做法,直到所有的点全部着上色为止 。
Guoyongfang.2006@yahoo.com.cn
对偶图与着色例,用韦尔奇 ·鲍威尔法对图着色 。
解 ⑴ 根据递减次序排列各点 A5,A3，
A7,A1,A2,A4,A6,A8。
⑵ 第一种颜色对 A5着色,并对不相邻的结点 A1也着第一种颜色 。
⑶ 对 A3结点和它不相邻的结点 A4,A8着第二种颜色 。
⑷ 对 A7结点和它不相邻的结点 A2,A6着第三种颜色 。
因此图 G是三色的 。 注意图 G不可能是二色的,因为 A1,A2,A3相互邻接,故必须用三种颜色 。 所以 x(G)＝ 3。
Guoyongfang.2006@yahoo.com.cn
对偶图与着色定理 对于 n个结点的完全图 Kn，有 x(Kn)＝ n。
证明 因为完全图每一个结点与其它各结点都相邻接，故 n个结点的着色数不能少于 n，又 n个结点的着色数至多为 n，故有 x(Kn)＝ n。
Guoyongfang.2006@yahoo.com.cn
对偶图与着色定理 设 G至少有三个结点的；连通平面图，则 G中必有一个结点 u，使得 deg(u)≤5。
证明 设 G＝ 〈 V,E〉,若 G的每一个结点 u,都有
deg(u)≥6,但因故 2e≥ 6v,所以 e≥ 3v＞ 3v－ 6,与前边的定理矛盾 。
ev
v
i
i 2
1
)(d e g
Guoyongfang.2006@yahoo.com.cn
7-8 根树及其应用定义 7-8.1 如果一个有向图在不考虑边的方向时是一棵树,那么这个有向图称为有向树,
Guoyongfang.2006@yahoo.com.cn
定义 7-8.2 一棵有向树,如果恰有一结点的入度为 0,
其余所有结点的入度都为 1,则称为根树,入度为 0
的结点称为根,出度为 0的结点称为叶,出度不为 0
的结点称为分枝点或内点,
1为根 ;2,4,7,8为分枝点；
3,5,6,9,10,11为树叶。
1处在第零层，层数为 0；
2,3,4处在第一层，层数为 1；
5,6,7,8同处在第二层，层数为 2；
9,10,11同处在第三层，层数为 3。
该根树的高为 3。
1
8
9 10 11
42 3
65
7
Guoyongfang.2006@yahoo.com.cn
定义：在根树中，从树根到任何一结点的通路长度叫做该结点的层数，称层数相同的结点在同一层上；所有结点中层数最大值称为根树的高。
可用家族关系形象的表示根树中各结点间的关系：
Guoyongfang.2006@yahoo.com.cn
定义：在根树中，若从 vi到 vj可达，则称 vi是 vj的祖先,vj是 vi的后代；又若 <vi,vj>是根树中的有向边，则称 vi是 vj的父亲,vj是 vi的儿子；如果两个结点是同一个结点的儿子，则称这两个结点是兄弟。
在一个家族关系中，兄弟之间是有大小顺序的，
由此引入有序树的概念。
定义：如果在根树中规定了每一层上结点的次序，
这样的根树称为有序树。
Guoyongfang.2006@yahoo.com.cn
有序二叉树的每个结点至多有两个儿子，分别称为左儿子和右儿子；且至多有两棵子树，分别称为左子树和右子树。
Guoyongfang.2006@yahoo.com.cn
定义 7-8.3 根树包含一个或多个结点,这些结点中某一个称为根,其他所有结点被分成有限个子根树,
定义 7-8.4 在根树中,若每一个结点的出度小于或等于 m,则称这棵树为 m叉树,如果每一个结点的出度恰好等于 m或零,则称这棵树为完全 m叉树,若其所有树叶层次相同,称为正则 m叉树,当 m=2时,称为二叉树,
Guoyongfang.2006@yahoo.com.cn
例,M和 E两人进行网球比赛,如果一人连胜两盘或共胜三盘就获胜,比赛结束,(用二叉 树表示,)
E M
M
M
M
M
MM
M
M
E
E
E E
E
E
E
E
Guoyongfang.2006@yahoo.com.cn
任何一棵有序树都可以把它改写为一棵对应的二叉树,( 为左儿子,为右儿子,)
(a)
B
A
O
D
C
k H J
E F G
(b)
B
A
O
D
C
k H J
E
F
G
Guoyongfang.2006@yahoo.com.cn
(c)
O
B
A
D
C
k
H
J
E
F
G
Guoyongfang.2006@yahoo.com.cn
定理 7-8.1 设有完全 m叉树,其树叶数为 t,分枝点数为 i,则 (m-1)i=t-1.
证明,由假设可知,该树有 i+t个结点,由树的定义可知,该树的边数为 i+t-1.因为所有结点的出度之和等于边数,所以根据完全 m叉树的定义可知,
有 m*i=i+t-1
即 (m-1)i=t-1
Guoyongfang.2006@yahoo.com.cn
例,设有 28盏电灯,公用一个电源插座,问需用多少块具有四插座的接线板,
解,将电源插座看作根,四插座接线板看作分枝点,电灯看作树叶,则有
(4-1)i=28-1
得 i=9
需要九块四插座接线板,
Guoyongfang.2006@yahoo.com.cn
定义 7-8.5 在根树中,一个结点的通路长度,
就是从树根到此结点的通路中的边数,我们把分枝点的通路长度称为内部通路长度,树叶的通路长度称为外部通路长度,
定理 7-8.2 若完全二叉树有 n个分枝点,且各分枝点的层数之和为 I,各树叶的层数之和为 E,则
E=I+2n.
Guoyongfang.2006@yahoo.com.cn
例,验证定理 7-8.2
n=4,
I=0+1+1+2=4,
E=2+2+2+3+3=12,
I+2n=4+2*4=12=E
Guoyongfang.2006@yahoo.com.cn
定义 7-8.6 在带权二叉树中,若带权为
wi的树叶,其通路长度为 L(wi),我们把
w(T)=∑称为该带权二叉树的权,在所有带权 w1,w2,,wt,的二叉树中,w(T)最小的那棵树,称为最优树,
t
i=1
最优树问题
Guoyongfang.2006@yahoo.com.cn
我们假设 w1≤w2≤…≤wt。 1952年哈夫曼给出了求最优二叉树的方法。
最优树算法具体步骤如下：
1.初始令 s={w1,w2,,wt};
2.从 s中取出两个最小的权 wi,wj，画结点
vi，带权 wi，画结点 vj，带权 wj。画 vi和 vj
的父亲 v，连接 vi与 v,vj与 v，令带权
wi+wj;
3.令 s=(s-{wi,wj})U{wi+wj};
4.判断 s是否只含一个元素：若是，则停止。
否则转第 2步。
Guoyongfang.2006@yahoo.com.cn
例：用机器分辨一些币值为 1分,2分,5分的硬币，假设各种硬币出现的概率为 0.5,0.4，
0.1，问如何设计一个分硬币的算法，使所需时间最少？
解：利用哈夫曼算法答案如下
1
0.10.4
0.50.5
是否为 1分
1分是否为 2分
2分 5分是否否是
Guoyongfang.2006@yahoo.com.cn
定理 7-8.3 设 T为带权 w1≤w2≤…≤wt的最优树,则
(a)带权 w1,w2的树叶 vw1,vw2是兄弟,
(b)以树叶 vw1,vw2为儿子的分枝点,其通路长度最长,
定理 7-8.4 设 T为带权 w1 ≤w2 ≤ … ≤wt的最优树,若将以带权 w1和 w2的树叶为二子的分枝点改为带权 w1+w2的树叶,得到一棵新树 T’,
则 T’也是最优树,
Guoyongfang.2006@yahoo.com.cn
例,给定权 1,4,9,16,25,36,49,64,81,100:
(a)构造一棵最优二叉树 ;
(b)构造一棵最优三叉树 ;
(c)说明如何构造一棵最优 t叉树 ;
Guoyongfang.2006@yahoo.com.cn
(a) 1,4,9,16,25,36,49,64,81,100
1 4
5 9
14 16
5564
2530
100119
385
219
8185
4936
166
Guoyongfang.2006@yahoo.com.cn
(b) 1,4,9,16,25,36,49,64,81,100
0 1
5 9
4
30
16
91
3625
194
816449
100
385
Guoyongfang.2006@yahoo.com.cn
(c)要构造一棵最优 t叉树，可以如下进行：首先找出
t个最小的 w的值，设为 w1,w2,…,wt然后对 n-t+1
个权 w1+w2+… +wt,wt+1,…,wn求作一棵最优 t
叉树，并且将这棵最优树中的结点
w1+w2+… +wt 代之以 。
依次类推，由构造过程可知，除根外其它分枝点恰有 t个儿子。如果构造出来的树，根恰有 t个儿子，那么这棵树就是最优 t叉树。如果构造出来的树，根的儿子数目 k<t，那么在原来 n个权
w1,w2,…,wn中添加 (t-k)个 0，对于权 0,0,…,
0,w1,w2,…,wn按上法重新构造 t叉树，它能保证每个分枝点都有 t个儿子，这是最优 t叉树。
…w1 w2 wt
Guoyongfang.2006@yahoo.com.cn
定义 7-8.7 给定一个序列的集合,若没有一个序列是另一个序列的前缀,该序列集合称为前缀码,
定理 7-8.5 任意一棵二叉树的树叶可对应一个前缀码,
定理 7-8.6 任何一个前缀码都对应一棵二叉树,
前缀码问题
Guoyongfang.2006@yahoo.com.cn
例：图（ a）给出了与前缀码 {000,001,01,1}
对应的完全二叉树。图（ b）是删剪后得到的对应二叉树。
0 1
1
1 1
000 001
01
1
1 1 1000
0
0
0
(a) (b)
设有二进制序列 00010011011101001可译为,000,1,001,1,01,1,1,01,001。
