第八章 图论
李春利
中国民航学院
本章内容
8-1. 图的基本概念
8-2.路与回路
8-3. 图的矩阵表示
8-4. *带权图的最短路
8-5. 欧拉图与汉密尔顿图
8-6. *二部图 Bipartite Graph
8-7. 平面图 Plane Graph
8-8. *着色与对偶图
8-9. 树与生成树
8-10.根树及其应用
小结
习题
图论是个应用十分广泛而又极其有趣数学分支, 物理、
学、生物、经济、管理科学、信息论、计算机等各个领
域都可以找到图论的足迹.
历史上很多数学家对图论的形成作出过贡献, 特别要提
到的欧拉 (Euler)、基尔霍夫(Kirchhoff)与凯莱(Cayley).
欧拉在1736年发表了第一篇图论的论文, 解决了著名的
七桥问题. 拓扑学中著名的欧拉公式,也是图论中的重要
公式.
基尔霍夫对电路网络的研究(基尔霍夫定律)以及凯莱在
有机化学计算中应用了树和生成树等概念.
很多有趣的数学游戏也促进了图论的发展,如汉米尔顿
周游世界游戏, 四色定理等, 都促进了图论的发展.
8-1. 图的基本概念
例1. 多用户操作系统中的进程状态变换图:
(进程:一个业务可以分成若干个阶段,每个阶段看成一个进程. 一个进程有三种状态.)
就绪状态:进程具备执行条件,因CPU少,要排队等待分配
CPU.
进程调度
请求I/O
I/O完成
执行状态:进程已经分配到CPU,它的程序正被执行.
等待状态:进程等待某事件(如I/O完成),此时就是给它CPU
也不能执行..
例2.“七桥问题” 十八世纪,哥尼斯堡城内有一条河----普雷
格尔河,河中有两个岛屿,河面架有七座桥,使得岛屿与两
岸之间互相贯通.
人们茶余饭后经常到桥上散步,从而提出这样问题:是否
可以从某地出发，每座桥都走一次,再回到出发点. 很多
人试图找出这样的路径, 都没有找到. 后来欧拉证明这样
的路径根本不存在.
此图可以抽象为上边右图.
V={A,B,C,D} E={e1, e2, e3, e4, e5 e6, e7}
例3. 在机械加工中,经常需要在一块金属薄板上钻若干孔
如何确定钻孔的次序,使之加工的时间最短.
(或者是机械手在印刷电路板上安装电子元件)如图所示:
这个问题可以抽象为在一个图上求从某一个结点出发,经过所有结点一次, 使得此路径最短. 如何找到此路径.
这样钻孔显然是不合适的：
类似的: 旅行最优问题, 工程最优
问题, 成本(费用)最低. …...
一. 图的概念
一个图 G=<V(G),E(G)>, 其中
V(G): 是G的结点的非空集合. (V(G)≠Φ),简记成V.
E(G): 是G的边的集合. 有时简记成E.
结点(Vertices): 用 表示, 旁边标上该结点的名称.
边(Edges):
有向边: 带箭头的弧线. 从u到v的边表示成 <u,v>
无向边:不带箭头的弧线. u和v间的边表示成 (u,v)
在图中, 结点的相对位置不同, 边的曲直、长短无关紧要.
邻接点: 与一边关联的两个结点. u v a b
e2
G:
邻接边: 关联同一个结点的两条边.
e1
v
环:只关联一个结点的边.
平行边:在两个结点之间关联的多条边.
二. 有向图与无向图
有向图:只有有向边的图.
无向图:只有无向边的图.
三. 零图与平凡图
孤立结点:不与任何边关联的结点. u
零图:仅由一些孤立结点构成的图. a
即此图的边的集合E=Φ b c
平凡图:仅由一个孤立结点构成的零图.|V(G)|=1,|E(G)|=0
四. 简单图与多重图
简单图:不含有环和平行边的图.
多重图: 含有平行边的图.
五. 无向图结点v的度(degree):
1.定义:G是个无向图, v∈V(G), 结点v所关
联边数,称之为结点v的度. 记作 deg(v).(或d(v)).
deg(a)=3 deg(b)=5 deg(c)=4 deg(d)=2
一个环给结点的度是2.
2.无向图的结点度序列:
令G=<V,E>是无向图, V={v1,v2,v3,…,vn}, 则称:
(deg(v1), deg(v2),deg(v3), …,deg(vn)) 为图G的结点度序列.
例如上图的结点度序列为:(3,5,4,2)
3.图的最大度Δ(G)与最小度δ(G) :G=<V,E>是无向图,
Δ(G) =max{deg(v)|v∈G} δ(G) =min{deg(v)|v∈G}
右图中Δ(G)=5 δ(G)=2
4. 定理 每个无向图所有结点度总
和等于边数的2倍.即
∑deg(v)=2|E|
v∈V
∑deg(v) + ∑deg(v) =2|E|
v∈V1 v∈V2
证明:因为图中每条边关联两个结点,因此每条边给予它所
关联的两个结点的度各是1, 即一条边对应的度数是2, 所
以整个图的度数总和为边数的2倍.
定理(握手定理)每个无向图中,奇数度的结点必为偶
数个.(一次集会中,与奇数个人握手的人,必是偶数个.)
证明:令G=<V,E>是无向图,将V分成两个子集V1 和V2,
其中 V1 ---是度数是奇数的结点集合,
V2 ---是度数是偶数的结点集合
六. k-正则图:一个无向简单图G中,如果Δ(G)=δ(G)=k
则称G为k-正则图.
课堂练习:
1.下面哪些数的序列,可能是一个图的度数序列?
如果可能,请试画出它的图. 哪些可能不是简单图?
a) (1,2,3,4,5)
b) (2,2,2,2,2) c) (1,2,3,2,4)
d) (1,1,1,1,4) e) (1,2, 2,4,5)
2.已知无向简单图G中,有10条边,4个3度结点,其余结点的
度均小于或等于2,问G中至少有多少个结点?为什么?
a) (1,2,3,4,5) b) (2,2,2,2,2) c) (1,2,3,2,4)
d) (1,1,1,1,4) e) (1,2, 2,4,5)
解:a)不是, 因为有三个数字是奇数.
b) c) d)是.
e) 不是简单图,因为它有5个结点, 有一个结点度为5, 必然有环或平行边.
2.解:已知边数|E|=10, ∑deg(v)=2|E|=20
其中有4个3度结点, 余下结点度之和为: 20-3×4=8
因为G是简单图, 其余每个结点度数≤2, 所以至少还有4
个结点. 所以G中至少有8个结点.
七. 有向图结点的出度和入度:(in degree out degree)
G=<V,E>是有向图,v∈V
v的出度: 从结点v射出的边数.
记作deg+(v) 或 dego(v)
v的入度: 射入结点v的边数. 记作deg-(v) 或 degi(v)
degi(a)=2 degi(b)=2 degi(c)=1 degi(d)=1
dego(a)=2 dego(b)=3 dego(c)=1 dego(d)=0
定理 G=<V,E>是有向图, 则G的所有结点的出度之和
等于入度之和.
证明: 因为图中每条边对应一个出度和一个入度. 所以所
有结点的出度之和与所有结点的入度之和都等于有向边
数. 必然有所有结点的出度之和等于入度之和.
八. 完全图
1.无向完全图
定义:G是个简单图, 如果每对不同结点之间都有边相连
则称G是个无向完全图. 如果G有n个结点, 则记作Kn.
证明: 因为Kn中每个结点都与其余n-1个结点关联, 即每
个结点的度均为n-1, 所以Kn的所有结点度数总和为
n(n-1), 设边数为|E|, 于是n(n-1)=2|E| 所以|E|=
定理: 有n个结点的有向简单完全图有边数为n(n-1).
证明: 显然它的边数是Kn边数的2倍.所以是n(n-1).
2).有向完全图(有向全图) (它与完全关系图一致)
G是个有向图如果任何两个结点之间都有相互可达的边,
则称它是有向完全图.
其图形如下:
2. 有向图的完全图 (注:这里的定义与教材不同)
1).有向简单完全图:G是个有向简单图,如果任何两个不
同结点之间都有相互可达的边,则称它是有向简单完全图.
例如:
所以有n个结点的有向完全图, 有边数 n2.
九.子图和生成子图
1.子图:设G=<V,E>是图,如果G’=<V’,E’>且V’V,
V’≠Φ, E’E, 则称G’是G的子图.
可见G1,G2,G3都是K5的子图.
2. 生成子图
设G=<V,E>是图, G’=<V’,E’>, G’是G的子图,如果V’=V,
则称G’是G的生成子图.
上例中, G1是K5的生成子图.
十. 补图
由G的所有结点和为使G变成完全图,所需要添加的那些
边组成的图, 称之为G相对完全图的补图,简称G的补图,
记作 .
十一. 图的同构
设G=<V,E>和G’=<V’,E’>是图,如果存在双射f:VV’ 且
任何vi,vj∈V,若边(vi,vj)∈E,当且仅当 边(f(vi),f(vj))∈E’,
(或若边<vi,vj>∈E,当且仅当 边<f(vi),f(vj)>∈E’),则称G与
G’同构,记作G≌G’. (同构图要保持边的“关联”关系)
例如:右边所示的两个图:
G=<V,E> G’=<V’,E’>
构造映射f:VV’
两个图同构的必要条件: 1.结点个数相等. 2.边数相等.
3.度数相同的结点数相等. 4. 对应的结点的度数相等.
下面是同构的图:
右面两个图不同构:
左图中四个3度结点
构成四边形,而右图,
则不然.
课堂练习:请画出K4的所有不同构的生成子图.
练习:请画出K4的所有不同构的生成子图.
本节要求:准确掌握如下基本概念和定理:
1.有向边,无向边,孤立结点,平行边,环.
2.有向图,无向图,零图,平凡图,简单图,多重图,完全图,子图,生成子图,补图,相对补图
3.四个定理(关于结点度,以及结点度与边数关系)
4.图的同构 (会判断).
作业: P279 (1) (2) (4) (5)
8-2.路与回路
在实际应用中,比如在市内乘出租车去参观一个博览会,
一定要司机选一条最短的路. 到博览会后, 最好选一条这
样到路径,使得每个展台都参观一次后,再回到原来存包
处. 这就是路与回路的问题.
一. 路的概念
1.路的定义: 给定图G=<V,E >
设v0 ,v1,v2,,…,vn∈V, e1,e2,,…,en∈E
其中ei是关联vi-1 ,vi的边, 则称结点和边的交叉序列
v0 e1v1 e2v2…envn是连接v0到vn的路. v0是此路的起点,vn是
此路的终点. 路中含有的边数 n称之为路的长度.
例如上图中: v0 e2v3 e6v2是一条长度为2的路.
如果图是个简单图, 则路可以只用结点序列表示.
如右图中, 路:abcad
如果图是个有向图, 则路可以
只用边序列表示.
如有向图中 e1 e5e2e3 e6 是一条路.
2. 回路:如果一条路的起点和终点是一个结点,则称此路是
一个回路.
如右图中的 L1=v0 e1v1 e5v3 e6v2e4v0
L2= v0 e1v1 e5v3e2v0
3. 迹与闭迹
如果一条路中,所有边都不同,则称此路为迹.
如果一条回路中,所有边都不同,则称此回路为闭迹.
4. 通路与圈
如果一条路中,所有结点都不同,则称此路为通路.
如果一条回路中,除起点和终点外,其余结点都不同,则称
此回路为圈.
例如右图中:
L1=v0 e1v1 e5v3 e6v2e4v0
L2= v0 e1v1 e5v3e2v0
L3=v0 e1v1 e5v3 e2v0 e3v3 e6v2e4v0
L1和L2是闭迹, 也是圈.
L3是闭迹,而不是圈.
定理 在一个有n个结点的图中,如果从结点vi到vj存在
一条路,则从vi到vj必存在一条长度不多于n-1的路.
*证明: 设vi到vj存在一条路: vivi+1vi+2,…,vj ,
设此路的长度为k.
假设k>n-1, 则此路中有 k+1个结点, k+1>n, 而G中只有n
个结点, 所以此路中必有两个结点相同, 假设vs=vt, (t>s)
于是此路为:
从图看出,此路中有一个从vs到vt的回路, 此回路中,有t-s条
边( t-s>1), 如果删去这个回路, 就得到一条vi到vj更短的路.
如果新的路长度还大于n-1, 说明此路中还有回路,再删去
回路, 如此进行下去. 最后必可找到长度小于n-1的路.
补充应用题:摆渡人Ferryman,狼Wolf,羊Sheep,干草Hay过河问
题 .如何摆渡使得它们不能互相伤害.
实际上,这是个在图上
找一条路的问题.
二. 无向图的连通性
1.两个结点是连通的: 在无向图中,结点u和v之间如果存在
一条路, 则称u与v是连通的.
我们规定: 对任何结点u, u与u是连通的.
2.结点之间的连通关系是个等价关系.
令G=<V,E>是无向图, R是V上连通关系, 即
R={<u,v>|u和v是连通的}
显然R具有自反、对称和传递性.
于是可以求商集V/R.
例1. 给定图G1如右上图所示:
V/R={{a,b,g},{c,d,e,f},{h}}
例2.给定图G2如右下图所示:
V/R={{1,3,5},{2,4,6}}
3.连通分支:令G=<V,E>是无向图, R是V上连通关系, 设R
对V的商集中有等价类V1,V2,V3,…, Vn ,这n个等价类构成
的n个子图分别记作G(V1),G(V2),G(V3),…, G(Vn),并称它
们为G的连通分支. 并用W(G)表示G中连通分支数.
下边例中 W(G1)=3 W(G2)=2 W(G3)=1
G1
G2
G3
4.连通图: 如果一个图G只有一个连通分支(W(G)=1),则称G是连通图.
W(G3)=1 , G3是连通图
定理 图G=<V,E>是连通的,当且仅当 对V的任何分
成V1、V2的划分,恒存在一条边, 使得它的两个端点分别
属于V1和V2.
*证明:必要性. 已知G是连通的. 令{V1,V2}是V的一个划分.
任取v1∈V1, v2∈V2, 由于G是连通的,
必存在一条路 v1 ……. v2,
在此路上必存在结点u和v,
使得u∈V1, v∈V2 ,且(u,v)是此路中
的一条边.
充分性:已知对V的任何分成V1、V2的划分,恒存在一条边,
(反证法)假设G不是连通的. 则G至少有两个连通分支G1、
G2,令V1 =V(G1) V2=V-V(G1), 根据连通分支定义知, 不存
在端点分别属于V1和V2的边, 与已知矛盾. 所以G是连通
的.
三. 割集 (Cut Set)
割集在图论中是个重要概念, 在图论的理论和应用中,
都具有重要地位.
比如有交通图:
结点u, 边e就是
至关重要的.
割集就是使得原来连通的图, 变成不连通, 需要删去的
结点集合或边的集合.
1.点割集与割点:令G=<V,E>是连通无向图, 结点集合V1 ,
V1V, 如果删去V1中所有结点后,G就变得不连通了, 而删
去V1的任何真子集中的所有结点,得到的子图仍然连通.则
称V1是G的一个点割集. 如果点割集V1中只有一个结点,
则称此结点为割点.
右图中:{b,f}, {b,g}, {f,k},{k,g}以及{a,d,i,l}是点割集.
不存在割点.
2. 点连通度:若G不是完全图, 定义:
k(G)=min{ | V1 | | V1是G的点割集} 为G的点连通度.
点连通度k(G)是表示使G不连通,至少要删去的结点数.
上例中 k(G)=2
具有割点图的点连通度 k(G)=1
定理 一个连通图中结点v是割点的充分且必要条件
是存在两个结点u和w, 使得从u到w的任何路都通过 v .
证明:略
上边是通过删去结点的办法使连通图变得不连通的.
也可以通过删去边的办法使连通图变得不连通.
3. 边割集与割边(桥)
令G=<V,E>是连通无向图, 边的集合E1,E1E, 如果删去
E1中所有边后,G就变得不连通了, 而删去E1的任何真子集
中的所有边,得到的子图仍然连通.则称E1是G的一个边割
集. 如果边割集E1中只有一条边, 则称此边为割边, 也称之
为桥.
右图中, e就是桥.
4.边连通度:若G不是平凡图, 定义:
λ(G)=min{ |E1| | E1是G的边割集}为图G的边连通度.
边连通度λ(G)是表示使G不连通,至少要删去的边数.
显然,如果G不是连通图, 则 k(G)=λ(G)=0
四. 有向图的连通性
1.结点间的可达性: G=<G,E>是有向图, u,v∈V, 如果从
u到v有一条路, 则称从u到v可达.
右图中: a可达b和d, 但是a不可达c.
显然结点间的可达关系,具有自反性和传递性.
2. 结点u到v的距离: 如果u可达v, 可能从u到v有多条路,其中最短的路的长度,称之为从u到v的距离.记作d<u,v>.
上例中 d<a,b>=1 d<a,d>=2 d<a,a>=0 d<b,c>=∞
3. 可达性的性质:
1). d<u,v>≥0 2) d<u,u>=0
3) d<u,v> + d<v,w>≥d<u,w> (如上图的c,a,b)
4) 如果从u到v不可达,则d<u,v>=∞ (如b,c)
5) 如从u可达v,从v也可达u, 但d<u,v>不一定等于d<v,u>
(如a,d)
4. 图的直径: G是个有向图, 定义
为图G的直径.
上图中, 图的直径D=∞ (因为d<b,c>=∞)
5. 强连通、单侧连通和弱连通
在简单有向图G中,如果任何两个结点间相互可达, 则称
G是强连通. 如果任何一对结点间, 至少有一个结点到另
一个结点可达, 则称G是单侧连通. 如果将G看成无向图后
(即把有向边看成无向边)是连通的,则称G是弱连通.
(a)有回路adbca,强连通.
(b)a到d, d到a, 都不可达
是弱连通.
(c)单侧连通.
D=max{d<u,v>}
u,v∈V
定理 一个有向图G是强连通的,当且仅当G中有一个
回路, 此回路至少包含每个结点一次.
证明:充分性: 显然成立. 因为如果G中有一个回路, 它至少
包含每个结点一次, 就使得任何两个结点间相互可达, 所
以G是强连通的.
必要性:如果G是强连通的,则任何两个结点间相互可达.
所以可以构造一个回路经过所有结点. 否则必有一个回路
不包含某个结点v, 所以v与回路上的各结点都不相互可
达.这与G是强分图矛盾. 所以G必有回路至少包含每个结
点一次.
所以可以应用此定理判断G是否为强连通, 就是看它是否
有包含每个结点的回路.
6. 强分图、单侧分图和弱分图
在简单有向图中,具有强连通的最大子图,称为强分图.具
有单侧连通的最大子图,称为单侧分图. 具有弱连通的最
大子图,称为弱分图.
这些分图用结点的集合表示.
例如,给定有向图G,如图所示:
求它的强分图、单侧分图和
弱分图.
解: 强分图:由{a,g,h}{b}{c} {d}{e}{f}导出的子图.
单侧分图:由{a,g,h,b,f,d,e}{b,c,f,d,e}导出的子图.
弱分图:G本身是弱分图.
在有向图中,每个结点必位于一个且只位于一个强分图中。
定理 在有向图中,每个结点必位于一个且只位于一个
强分图中.
证明:令G=<V,E>是有向图, 任取结点v∈V, 令S是所有与v
相互可达的结点集合, 当然v∈S ∴S≠Φ, 而S是一个强分
图, 所以v必位于一个强分图中.
如果v位于两个不同的强分图S1、S2中, 于是 v与S1中每
个结点相互可达, v也与 S2中每个结点相互可达, 所以S1中
每个结点都与S2中每个结点通过v相互可达, 这说明S1与S2
是一个强分图, 与已知S1、S2是两个不同的强分图矛盾.
所以每个结点必位于一个且只位于一个强分图中.
在给定的简单有向图中找强分图----回路中的结点构成
一个强分图, 不在回路中的结点,自己构成一个强分图.
作业 P286 (3) (5) (8)
8-3. 图的矩阵表示
图的矩阵表示不仅是给出图的一种表示方法, 还可以通过
这些矩阵讨论有关图的若干性质, 更重要的是可以用矩阵
形式将图存入计算机中, 在计算机中对图作处理.
这里主要讨论图的三种矩阵.
一. 邻接矩阵
这是以结点与结点之间的邻接关系确定的矩阵.
1.定义:设G=<V,E>是个简单图,V={v1,v2,v3,…,vn }, 一个
n×n阶矩阵A=(aij)称为G的邻接矩阵. 其中:
例如, 给定无向图G1和有向图G2如图所示:
2.从邻接矩阵看图的性质:
无向图: 每行1的个数=每列1的个数=对应结点的度
有向图: 每行1的个数=对应结点的出度
每列1的个数=对应结点的入度
3.邻接矩阵的乘积
在(A(G1))2 中a342 =2 表示从v3到v4有长度为2的路有2条:
在(A(G1))3中a233 =6 表示从v2到v3有长度为3的路有6条:
v2v1v2v3 , v2v4v2v3 , v2v3v2v3 , v2v3v1v3 , v2v3v5v3 , v2v4v5v3 .
G1
v3 v2v4 , v3 v5v4
定理设G=<V,E>是简单图,令V={v1,v2,v3,…,vn}, G的
邻接矩阵(A(G))k中的第 i行第j列元素aijk=m, 表示在图G
中从vi到vj长度为k的路有m条.
可以用归纳法证明.(见教材P290)
在实际应用中,有时只关心从一个结点到另一个结点是否
有路,而不关心路有多长,比如电话网络. 这就促使我们定
义可达矩阵.
二.可达性矩阵
1.定义:设G=<V,E>是个简单图,V={v1,v2,v3,…,vn }, 一个
n×n阶矩阵P=(pij)称为G的可达性矩阵. 其中:
2.求可达矩阵
可以根据邻接矩阵A求可达矩阵. 设|V(G)|=n
令A(k)是将Ak中的非0元素都写成1,而得到的只含有0和
1的0-1矩阵.于是可达矩阵P为:
P=A∨A(2)∨A(3)∨...∨A(n) 其中∨是逻辑或.
有两种方法求P
方法1. 按照矩阵相乘分别求出A(k) (k≥2), 然后再∨.
方法2.用求传递闭包的Warshall算法,见P124.
例如,G2如图所示, 求它的
可达矩阵P.
A(5)=A(3)
P=A∨A(2)∨A(3)∨A(4)∨A(5)
3.用可达矩阵求强分图.
以G2为例,
从图看出有两个强分图:{v1,v3}和{v2,v4,v5}
下面看怎样用P求强分图.
先将P=(pij)转置得PT=(pTij), 如果vi与vj相互可达,则
pij= pTij =1
对P∧PT进行初等变换, 第2行与第3行交换,再第2列与第3
列交换, 最后得两个强分图:{v1,v3}和{v2,v4,v5}
三.完全关联矩阵
此矩阵是按照结点与边之间的关联关系确定的矩阵.
1.无向图的完全关联矩阵
1.无向图的完全关联矩阵
1).定义:设G=<V,E>是个无向图,V={v1,v2,v3,…,vm },
E={e1,e2,e3,…,en },一个m×n阶矩阵M=(mij)称为G的完全
关联矩阵. 其中:
mij ={
1 vi与ej关联
0 否则
2)从关联矩阵看图的性质:
a)每列只有二个1.
(因为每条边只关联两个结点)
b)每行中1的个数为对应结点
的度数.
c)如果两列相同,则说明对应的
两条边是平行边.
2.有向图的完全关联矩阵
1).定义:设G=<V,E>是个简单有向图,V={v1,v2,v3,…,vm },
E={e1,e2,e3,…,en },一个m×n阶矩阵M=(mij)称为G的完全
关联矩阵. 其中:
2).从关联矩阵看图的性质:
a)每列只有一个1和一个-1.
(每条边有一个起点一个终点)
b)每行中1的个数为对应结点
的出度 -1个数是结点入度
本节重点掌握:
图的三个矩阵的求法
由图的矩阵,看图的性质.
作业 P300 (3)
*8-4.带权图的最短路
在实际应用中,一些图的边上标有数字, 用以表示两结点
间的距离、或路费等等. 然后求两点间的最短路径.这是
很有意义的问题.
一.带权图(赋权图)
1.定义:设G=<V,E,W>,是个图,如果G的每条边e上都标有
实数c(e) (c(e)∈W),称这个数为边e的权, 称此图为带权图.
规定: u,v∈V, 边(u,v)的权记作 c(u,v)
1) c(u,u)=0
2) 如果结点u与v之间无边相连,则 c(u,v)=∞
2.带权图的路长:结点u与v之间的路长是指该路所包含的
各边权的总和.
例如右图中
v1 v2v3 v6 的路长为12.
3.带权图的两点间距离:
结点u与v之间的 最短路的长
称为结点u与v之间的距离. 记作d(u,v).
如果G是有向带权图,称为结点u到v的距离,记作d<u, v>
例如上图中 d(v2,v5)=2
4.带权图中求一个结点到各点的最短路的算法:
此算法是于1959年由提出的.
基本思想:若使 (u0,u1,u2,…,un-1,un)最短, 就要使
(u0,u1,u2,…,un-1)最短, 即保证从u0到以后各点的路都是最
短的.
令图G=<V,E,W>, 集合SiV Si’=V-Si , 令|V|=n
Si={u|从u0到u的最短路已求出}
Si’={u’|从u0到u’的最短路未求出}
Dijkstra(迪克斯特拉)算法:(求从u0到各点u的最短路长)
第一步. 置初值: d(u0,u0)=0 d(u0,v)=∞ (其中v≠ u0)
i=0 S0={u0} S0’=V-S0 ,
第二步.若 i=n-1 则停. 否则转第三步
第三步. 对每个u’∈Si’
计算 d(u0,u’)=min{d(u0,u’), d(u0,ui)+c(ui,u’)}
ui ∈Si
u’∈Si’
计算 min{d(u0,u’)}
并用ui+1记下达到该最小值的那个结点u’
置Si+1 =Si∪{ui+1} i=i+1 Si’=V-Si , 转第二步.
例.求右图中从v1到v6的
最短路
1.置初值: u0=v1
d(u0,u0)=0
d(u0,v2)=d(u0,v3)=d(u0,v4)=d(u0,v5)=d(u0,v6)=∞
. i=0 S0={v1} S0’={v2,v3,v4,v5,v6}
d(u0,v2)=min{d(u0,v2), d(u0,u0)+c(u0,v2)}=min{∞,0+3}=3
d(u0,v3)=min{d(u0,v3),d(u0,u0)+c(u0,v3)}=min{∞,0+∞}=∞
d(u0,v4)=min{d(u0,v4), d(u0,u0)+c(u0,v4)}=min{∞,0+5}=5
d(u0,v5)=min{d(u0,v5),d(u0,u0)+c(u0,v5)}=min{∞,0+∞}=∞
d(u0,v6)=min{d(u0,v6),d(u0,u0)+c(u0,v6)}=min{∞,0+∞}=∞
min{3,∞,5, ∞,∞}=3
ui+1 =u1=v2 ,
实际已求出d(u0,v2)=3, 路是u0v2
i=1 S1={v1, v2}
S1’={v3,v4,v5,v6}
u1=v2
d(u0,u1)=3
d(u0,v3)=min{d(u0,v3),d(u0,u1)+c(u1,v3)}=min{∞,3+6}=9
d(u0,v4)=min{d(u0,v4), d(u0,u1)+c(u1,v4)}=min{5,3+1}=4
d(u0,v5)=min{d(u0,v5),d(u0,u1)+c(u1,v5)}=min{∞,3+∞}=∞
d(u0,v6)=min{d(u0,v6),d(u0,u1)+c(u1,v6)}=min{∞,3+∞}=∞
min{9,4,∞,∞}=4
ui+1 =u2=v4 , 实际已求出d(u0,v4)=4, 路是u0v2v4
i=2 S2={v1, v2 ,v4}
S2’={v3,v5,v6}
u2=v4
d(u0,u2)=4
d(u0,v3)=min{d(u0,v3), d(u0,u2)+c(u2,v3)}=min{9 ,4+3}=7
d(u0,v5)=min{d(u0,v5), d(u0,u2)+c(u2,v5)}=min{∞,4+1}=5
d(u0,v6)=min{d(u0,v6), d(u0,u2)+c(u2,v6)}=min{∞,4+∞}=∞
min{7,5,∞}=5
ui+1 =u3=v5 , 实际已求出d(u0,v5)=5, 路是u0v2v4 v5
i=3 S3={v1, v2 ,v4 ,v5}
S3’={v3,v6}
u3=v5
d(u0,u3)=5
d(u0,v3)=min{d(u0,v3),d(u0,u3)+c(u3,v3)}=min{7 ,5+3}=7
d(u0,v6)=min{d(u0,v6),d(u0,u3)+c(u3,v6)}=min{∞,5+6}=11
min{7,11}=7
ui+1 =u4=v3 , 实际已求出d(u0,v3)=7, 路是u0v2v4 v3
i=4 S3={v1, v2 ,v4 ,v5, v3} S3’={v6} u4=v3 d(u0,u4)=7
d(u0,v6)=min{d(u0,v6),d(u0,u4)+c(u4,v6)}=min{11,7+3}=10
min{10}=10
ui+1 =u5=v6 , 实际已求出d(u0,v6)=10, 路是u0v2v4 v3 v6
i=5 (n-1) 时 算法停止.
8-5. 欧拉图与汉密尔顿图
这里主要讨论图的遍历问题,一个是遍历过程中要求经过
的所有边都不同;一个是遍历过程中要求经过的所有结点
都不同.
欧拉在1736年发表了第一篇关于图论的论文, 就是就七
桥问题.
一.欧拉图:
1.欧拉路:在无孤立结点的图G中,如果存在一条路,它经
过图中每条边一次且仅一次, 称此路为欧拉路.
2.欧拉回路:在无孤立结点的图G中,若存在一条回路,它
经过图中每条边一次且仅一次,称此回路为欧拉回路.
称此图为欧拉图,或E图.(Euler)
G1
G2
在G2中:有欧拉回路:
v1v2v3v4v5v2v4v6v5v3v1
下面两个个图中是否有欧拉
路,或有欧拉回路?如何判断？
在G1中:有欧拉路:
acbefgdcfh
3.有欧拉路与有欧拉回路的判定:
定理:无向图G具有欧拉路,当且仅当G是连通的,且有
零个或两个奇数度的结点.
证明:必要性:设G有欧拉路.设此路为v0 e1v1 e2v2…vi… envk.
其中的结点可能重复，但边不重复，因为G无孤立结点，
此路又包含了G的所有边，所以此路必包含了G的所有结
点, 所以图G是连通的。
因为对此路中任何非端点的结点vi，每当它出现一次,必
关联两条边，故它虽可重复出现，但始终deg(vi) 是偶数。
对于端点v0和vk:
如果v0= vk ,则 deg(v0)是偶数。则G中无奇数度结点。
如果v0≠ vk , 则deg(v0)为奇数， deg(vk)也为奇数。则G中
有两个奇数度结点。
充分性：(证明的过程就是一个构造欧拉路的过程)
如果G有两个奇数度结点:就从一个奇数度结点出发,每
当到达一个偶数度结点,必然可以再经过另一条边离开此
结点,如此重复下去, 经过所有边后到达另一个奇数度结
点。如果G无奇数度结点,则可以从任何一个结点出发,去
构造一条欧拉路.
推论:无向图G具有欧拉回路,
当且仅当G是连通的,且所有结点的度都是偶数.
从此推论得知,七桥问题的图不是欧拉图.
4.求欧拉回路的算法:
N
选结点v
以v为起点找闭迹E1
Y
打印 E1
在G-E1中找一个闭迹E2 使 E1与 E2至少有一个公共点
N
以某公共点为起、末点,对
E1∪E2中的边重新排序得
新的闭迹C
E1:=C
Y
用上述算法求右图中欧拉回路.
此图中所有结点度均为偶数,
所以有欧拉回路.
a)选以1为起点的闭迹E1:1261
1
6
2
5
3
4
b) E1不包含所有边.
c) 在G- E1中找新闭迹E2: 6356 ( 6是E1与E2的公共点)
d)以公共点6为起点,对E1∪E2中的边排序:C=6356126
e) E1 := C
f) E1不包含所有边.
g) 在G- E1中找新闭迹E2: 52345 ( 5是E1与E2的公共点)
h)以公共点5为起点,对E1∪E2中的边排序:
C=52345612635
i) E1 := C
j) E1包含所有边. k)打印E1 =52345612635 l)停止.
欧拉路与欧拉回路问题, 也称一笔画问题.
二. 汉密尔顿图(H图) (Hamilton图)
Hamilton是英国数学家,在1959年,他提出Hamilton回路.
H图起源于一种游戏,这个游戏就是所谓周游世界问题.
例如,某个城市的街道如图所示:
该城市的所有交叉路口都有形象各
异的精美的雕塑,吸引着许多游客,
人人都想找到这样的路径:游遍各
个景点再回到出发点----H回路.
1.定义:设G=<V,E>是个无向有限图,
汉密尔顿路:通过G中每个结点恰好一次的路.
汉密尔顿回路(H回路):通过G中每个结点恰好一次的回
路.
汉密尔顿图(H图):具有汉密尔顿回路(H回路)的图.
例如右图中,就是H图,因为它有H回路:1234561
2.汉密尔顿图的判定:
到目前为止并没有判定H图的充分和必要条件.
定理 (充分条件):G是完全图,则G是H图.
证明:略
定理(充分条件)设G是有n个结点的简单图,若对G中
每对结点度数之和大于n-1(n),则G有一条H路(H回路)
证明: 先证明G是连通的.(反证法) 见书P307
再构造H路(H回路)
在图G1中, 满足充分条件Δ(G)=4 δ(G)=2
任意两个结点度数之和大于5,所以是H图.
注意:上述条件只是充分条件,而不是必要条件, 即不满足
这个条件的, 也可能有H路.
例如:在图G2中, 并不满足任意两个结点度数之和大于3,
但是却有H路.
G1
定理:(必要条件) 若图G=<V,E>有H回路,则对V的任
何非空子有限集S, 均有W(G-S)≤|S|, 其中W(G-S)是从G
中删去S中所有结点及与这些结点关联的边所得到的子图
的连通分支数.
证明:设C是图G的一条H回路,则对于V的任何非空子集S,
在C中删去S中任意一个结点v1后, 则C-{v1}仍是连通的路,
若再删去S中的另一个结点v2, 则W(C-{v1,v2})≤2, 若|S|=n
则删去S中的n个结点, 有W(C-{v1,v2,…,vn})≤n, 所以
W(C-{v1,v2,…,vn})≤|S| . 因为C是H回路, 所以它包含了G
的所有结点, 即C是G的生成子图. 所以C-S 也是G-S 的生
成子图, 故 W(G-S)≤|S|.
用此定理可以判断一个图不是H图.
如右图G, 取 S={c} 不满足 W(G-S)≤|S|.
3.用“最邻近法”求H回路
如果已经确定图G有H回路.
a). 任选初始结点u,找一个最邻近的(边的权最小)结点x.
b). 设x是新加入到这条路的结点, 再从不在此路上的结点
中找到一个与 x邻近的(边的权最小)结点,加到此路中.
c).重复b), 直到G中所有结点都在此路上.
d).最后再回到起点, 构成回路. 就是H回路.
例如右图
初始结点为a,
逐渐选邻近结点c,e,d,b,a.
得H回路acedba. 此回路的总权为:20
但是对带权图来说,此方法求的H回路不一定是最短的.
例如,实际上此图最短的H回路是 acebda 总权为17
本节重点掌握:
欧拉路及欧拉回路的判定,
能求欧拉路和欧拉回路,
H路及H回路的判定, 能求H路和H回路.
以及欧拉图和汉密尔顿图的应用.
作业 P311 (1) (2) (6)
*8-6 二部图 Bipartite Graph
在实际应用中,有些如对策、二人对弈、工作分配等问
题, 例如有A,B,C,D四个人,有a,b,c,d,e五种工作,如果某人
可以做某种工作,则它们之间连一直线.
请给他们安排工作.
1.定义:令G=<V,E>是无向图,
如果可以将V划分成两个子集V1,V2,
使得任何边(vi,vj)∈E, vi∈V1, vj∈V2, 则称G是二部图,也
称二分图. 并称V1,V2是G的互补的结点子集.
2.完全二部图:令G=<V,E>是以V1,V2为互补的结点子集的
二部图,如果V1中的每个结点都与V2中每个结点相邻接,则
称G是完全二部图. 如果|V1|=m, |V2|=n 则G记作Km,n
下面的图是否可以画成二部图？
下面两个图, 是否可以画成二部图？
V1={1,3} V2={2,4}， V1={1,4} V2={2,5}
边(2,4)如何画？ 结点3放哪里？边(2,3)(3,4)？
什么样的图可以画成二部图？
再看看前面三个图：
3.二部图的判定:
定理 G=<V,E>是二部图 当且仅当它的所有回路的长
度都是偶数.
证明:必要性: 假设G是个以V1,V2为互补的结点子集的二
部图, 设任意长度为n的回路: vi0vi1vi2,…,vin-1vi0,
假设 vi0vi2vi4,…,vin-2∈V1, vi1vi3vi5,…,vin-1∈V2 ,
可见n-1是奇数, 所以n是偶数.
充分性: 设G的每个回路长度均为偶数,
a)设G是连通的. 定义结点集合:
V1= {vi | vi和某个固定结点v之间的距离为偶数}
V2=V- V1={vi | vi和某个固定结点v之间的距离为奇数}
下面证明E中任何边, 其端点分别属于V1和V2.
(用反证法)假设有一条边(vi, vj)∈E, 使得vi∈V1 , vj∈V1
由V1的定义可知:结点 v到vi有最短路长为m(是偶数),v到
vj有最短路长为n(是偶数), 所以再加上边(vi,vj), 就得到一
条长度为(m+n+1)的回路, 可是此回路长为奇数, 与已知条
件矛盾. 所以vi和vj不能属于同一个结点子集.
类似地,假设有一条边(vi, vj)∈E,
使得vi∈V2 , vj∈V2,
由V2的定义可知:结点 v到vi有最短路长为m(是奇数),v到
vj有最短路长为n(是奇数), 所以再加上边(vi,vj), 就得到一
条长度为(m+n+1)的回路, 可是此回路长为奇数, 与已知条
件矛盾. 所以vi和vj不能属于同一个结点子集.
G是个以V1,V2为互补的结点子集的二部图,
b)如果G不是连通图时, 可以对G的每个分图,重复上述证
明,得到同样结论. 最后得, G必是二部图.
vi
vj
8-7 平面图 Plane Graph
在实际应用中,如高速公路设计、印刷电路设计,都要求
线路不交叉,这就是平面图, 一个图能否画在一个平面上,
且任何边都不交叉, 这就是图的平面化问题. 这个问题在
近些年来, 特别是大规模集成电路的发展进一步促进了对
平面图的研究.
1. 定义
设G是无向图, 如果能将G的所有结点和边都画在一个
平面上,且使得任何两条边除了端点外没有其它交点, 则
称G是个平面图。 一个图表面上是个非平面图, 如果通过
改变边的位置就变成平面图, 称此图是可平面化的。
例如右图.就是
可平面化的图.
下面是两个
重要的非平面图:
K5和K3,3
2. 平面图的面、边界及面的次数
设G是个平面图, 图中边围成的
区域,其内部不含有结点, 也不含
有边,称这样区域为G的一个面.
面的边界:围成一个面r的所有
边构成的回路,称之为这个r面的边界. 此回路中的边数,称
之为r面的次数,记作deg(r).
有限面与无限面: 面的面积有限称为有限面, 反之称为无
限面. 所有平面图的外侧都有一个无限面.
例如,上图中 r1 : 边界:ABCDFDA deg(r1)=6
r2 : 边界:ABCA deg(r2)=3
r3 : 边界:ACDA deg(r3)=3
r4 : 边界:ADA deg(r4)=2
3.欧拉公式
定理 G是个连通的平面图, 设v、e、r分别表示G中
结点数、边数、面数, 则有 v-e+r=2. 称此式为欧拉公式.
证明: (对面数r归纳证明)
⑴当r=1 时, 此时图是连通无回路的, 如果有两个结点,则
图的图形如右图. 以后每加一条边,也加一个
结点, 所以总是有 e=v-1, 于是
v-e+r=v-(v-1)+1=2 结论成立.
⑵假设当G有r≤k-1个面时, 结论成立.
⑶当G有r=k 个面且是连通图时, 当k≥2 时, 至少有一个
回路, 所以去掉此回路中的一条边后得到子图G’, G’中有
k-1个面, 结点数同G中结点数, 由⑵得v-(e-1)+(k-1)=2
整理得 v-e+k=2 即 v-e+r=2 定理得证.
4.平面图的判定
*定理(必要条件) 设G是有v 个结点、
e条边的连通简单平面图, 若v≥3, 则 e≤3v-6.
证明:⑴ 当e=2 时, 因为G是简单连通图, 所以v=3, 显然有
2≤3×3-6 即e≤3v-6
⑵当e>2时, (通过计算每个面的边界来证明)
设G有r个面, 因为G是简单图, 所以每个面至少由三条边
围成, 所以r个面的总边界数≥3r, 另外由于每条边在两个
面的边界中出现, 所以所有面的边界总数=2e, 所以有:
用此定理可以判定一个图不是平面图, 例如证明K5不是
平面图: K5中有v=5 e=10 3v-6=3×5-6=9 不满足e≤3v-6,
所以K5不是平面图.
上面定理是判定平面图的必要条件,而不是充分条件. 即
如果一个图 满足e≤3v-6, 它不一定是平面图. 例如, K3,3中
v=6 e=9 9≤3×6-6 满足e≤3v-6,
但它不一定是平面图.
下面要介绍一个判定一个平面图的
充分且必要条件, 即Kuratowski(库拉托斯基)定理. 在此之
前先介绍一个新概念----在2度结点内同构(同胚).
在一个图中有2度结点, 则这些结点不影响平面的面数, 例如下面两个图:
我们称这两个图是在
2度结点内同构的图.
定义:如果G1和G2是同构的,或者通过反复插入或删去度
数为2的结点, 使得它们变成同构的图, 称G1和G2 是在2度
结点内同构.
例如右边3个图就是
在2度结点内同构.
定理 (Kuratowski定理)一个图是平面图的充分且必
要条件是它不含有任何与K5、K3,3在2度结点内同构的子
图. (此定理证明略.) 判断下面彼得森(Peterser)图:
本节要求掌握:
平面图的概念, 平面图的边界,
欧拉公式及其应用
平面图的判定.
作业: P317 (1) (3) (5) (7)
*8-8 着色与对偶图
着色问题起源于对地图着色, 使得相邻(不是如
图所示)国家用不同颜色,需要多少种不同的颜色?
1852年英国数学家格色里(Guthrie)提出了“四色猜想”, 这一猜想在图论发展史上曾起过巨大的推动作用.
1879年肯普(Kempe)
给出了这个猜想的第一个证明.
但是到1890年,希伍德(Hewood)发现肯普的证明是错误的, 可是他指出肯普的方法,虽然不能证明地图着色用四种颜色,但可以证明五种颜色就够了.
直到1976年美国伊利诺斯(Illinois)大学的阿佩尔()和黑肯()把四色问题归结为2000个不同的组合结构图形,利用三台高速IBM360计算机对这些图形进行分析用了1200机时,近百亿次逻辑判断, 证明了“四色定理”.
一.对偶图(偶图)的定义:
给定平面图G=<V,E>, 具有平面F1,F2,F3,…,Fn. 如果有
图G*=<V*,E*>, 满足下面条件:
⑴对于G的任意平面Fi 的内部有且仅有一个结点vi*∈V*.
⑵对于图G的面Fi与 Fj的公共边界ek ,有且仅有一条边
ek*∈E* ,使得 ek*=(vi*,vj*), 且ek*与ek相交.(vi*在Fi内, vj*在Fj内)
⑶当且仅当ek只是一个面Fi的边界时,
vi*上有一个环ek* 与ek相交.
则称图G*是G的对偶图.
可见G*中的结点数等于
G中的面数.
二. 自对偶图:如果图G对偶图G*与G同构,则称G是自对偶
图. (如下图)
三.对偶图与平面图着色的关系:
对平面图面相邻面用不同颜
色的着色问题,可以归结到对
其对偶图的相邻接的结点着
不同颜色.
四. 图G的正常着色(简称着色):
1. 对G的每个结点指定一种颜色,使得相邻接的两个结点
着不同颜色. 如果G着色用了n种颜色,称G是 n-色的.
2.对G着色时,需要的最少颜色数,称为G的着色数,记作
x(G) .
3.对G着色方法:(下面介绍韦尔奇.鲍威尔法)
3.对G着色方法:(介绍韦尔奇.鲍威尔法 )
⑴将G中的结点按照度数递减次序排序,(此排序可能不唯
一,因为可能有些结点的度数相同)
⑵用第一种颜色对第一个结点着色,并按照排序,对与前面
着色点不邻接的每一个点着上相同颜色.
⑶用另一种颜色对尚未着色的点, 重复执行⑵和⑶,直到
所有结点都着上颜色为止.
例如:结点排序:A,B,E,F,H,D,G,C
结点度数:5, 5, 4,4,4, 4, 3, 3
注意：在给A进行着色时，
与A不邻接的结点有C,D，但是
由于C与D邻接，所以D不能与A
着同一种颜色。
五. 应用举例
安排期末考试(学分制), 不能使一个学生在同一个时间
参加两门课的考试.
设有七门课程,分别记作A,B,C,D,E,F,G. 如果两门课程
有共同的学生在读, 就在两门课程之间连一直线.得到图:
结点度数递减排序:
B,C,D,G,A,E,F
对图正常着色后, 标有同一种颜色的
课,可以同时考试.安排考试日程:
周一: A 周二: B,F
周三:C,E 周四: D,G
作业 P321 (1) (3) (7)a)b)
8-9 树与生成树
树是一种特殊的图, 它是图论中重要的概念之一, 它有着广泛的应用.在计算机科学中有如判定树、语法树、分类树、搜索树、目录树等等.
一.树 (Tree)
1.树的定义:一个连通无回路的
无向图T,称之为树. 如(a)
2.叶结点:度数为1的结点, 称为叶结点.
3.分支结点(内结点):度数大于1的结点.
4.森林:一个无向图的每个连通分支都是树.如(b)
(a)
(b)
5.与树定义等价的几个命题
定理给定图T, 以下关于树的定义是等价的.
⑴ 无回路的连通图.
⑵ 无回路且e=v-1 其中e是T的边数,v是T的结点数.
⑶ 连通的且e=v-1.
⑷ 无回路但添加一条新边则得到一条仅有的回路.
⑸ 连通的,但删去任一条边,T便不连通.
⑹ 每对结点之间有一条且仅有一条路.
证明:⑴⑵:已知T是连通无回路图,通过不断地增加T中
的结点数,归纳证明.
当 v=2时, T如右图所示,e=1 显然e=v-1.
以后对T在保证连通又无回路的前提下每增加一个结点,
也增加一条边. 设最后T有v个结点e条边, 所以 e=v-1.
⑵⑶: 已知T是无回路的,且e=v-1.(推出T是连通的)
假设T不是连通的,设T有k个连通分支, T1,T2,...,Tk,(k≥2)
因为它的每个连通分支都是连通无回路的,所以都是树,
设Ti有结点数vi,边数ei, 所以边数 ei =vi-1
设T有v个结点,e条边. 所以
v= v1+v2+v3+…+vk
e= e1+e2+e3+…+ek=(v1 -1)+(v2 -1)+(v3 -1)+…+(vk -1)
=(v1+v2+v3+…+vk)-k=v-k
但是已知 e=v-1 所以 k=1 所以T是连通图.
⑶⑷:已知T是连通的且e=v-1(推出T无回路,且加一新
边,得到仅有一条回路)假设T有回路C1,从C1中删去一条边
以后T仍然连通性,如果还有回路C2,再从C2中删去一条边,
如此下去.假设共删去k条边,就无回路了,得到树T’,设T’有
边e’, ∴e’=v-1, ∴ e-k=v-1 又已知 e=v-1 ∴k=0 即T无回路
再证明:加一新边,得到仅有一条回路
假设加一条新边(u,v),如果u与v是邻接点,那么新边与原来
(u,v)边构成平行边,自成一个回路. 如果u与v不邻接, 由于
T是连通的,u间v必有一条路径P,加上新边(u,v)后,就与P
构成回路, 且此回路必是唯一的.因为如果回路不唯一, 则
删去(u,v)边后,还有回路, 与上面证出的T无回路矛盾.
⑷⑸:已知T无回路,且加一条边得到仅有的一条回路.
(推出T是连通的,且删去一条边后T就不连通了)
假设T不是连通的,则存在两个结点vi与vj之间无路, 于是
加上边(vi,vj)不会产生回路, 这与已知矛盾. 故T树连通的.
因T是连通无回路的, 故删去任何一条边后,T就不连通了.
⑸⑹:已知T是连通的,且删去一条边后T就不连通了.
(推出每对结点之间有且仅有一条路)
由T是连通图,则任何两个结点间都有一条路. 如果有两个
结点间有多于一条的路, 那么T必有回路, 则删去回路中的
一条边后,T仍然是连通的. 与已知矛盾.
⑹⑴:已知T每对结点间有且仅有一条路(推出T连通无
回路)
因为T 每对结点之间有一条路,所以T是连通的.若T
有回路,则回路上任何两个结点间有两条路,与已知矛盾.
二. 生成树
在图论的应用中,找出一个连通图的所有不同的生成树,以
及找出最小生成树是很有意义的.
1.定义:如果图G的生成子图是树,则称此树为G的生成树.
2.弦:图G中,不在其生成树里的边,称作弦. 所有弦的集合,
称为该生成树的补.
定理 连通图至少有一棵生成树.
证明:如果G中无回路, 则G本身就是树.
如果G中有回路,可以通过反复删去回路
中的边,使之既无回路,又连通.就得到生成树.
思考题:设G是有n个结点,m条边的连通图, 问要删去多少
条边,才得到一棵生成树?
三.赋权图的最小生成树
1.定义:一棵生成树中的所有边的权之和称为该生成树的
权. 具有最小权的生成树,称为最小生成树.
最小生成树很有实际应用价值.例如结点是城市名,边的权
表示两个城市间的距离, 从一个城市出发走遍各个城市,
如何选择最优的旅行路线.又如城市间的通信网络问题,如
何布线,使得总的线路长度最短.
例如:右图所示
2.求最小生成树算法
---Kruskal算法:
(避圈法)
(克鲁斯卡尔)
Kruskal算法(克鲁斯卡尔 ): 设G是有n个结点,m条边(m≥n-1)
的连通图.
S=Φ i=0 j=1
将所有边按照权升序排序:
e1, e2, e3,… ,em
j=j+1
i=i+1
ai=ej
S=S∪{ai}
j=j+1
输出S
Y
N
Y
N
|S|=n-1, 说明是树
最后S={a1, a2, a3,… ,an-1}
边按升序排序:边(vi, vj)记成eij
v1
v5
v4
v2
v3
v8
v6
v7
本节要掌握：
树的6个定义,
会画生成树和最小生成树.
作业 p327 (2)(3)(6)
8-10. 根树及其应用
下面讨论有向树,它的应用很广泛.在计算机科学中有如判定树、语法树、分类树、搜索树、目录树等等.
一.有向树
1.定义:如果G是个有向图,且在不考虑边的方向时(即看成无向图时),是一棵树,则称G是有向树.
例如:
二.根树:如果一棵有向树,恰有一个结点的入度为0,其余所
有结点的入度均为1,则称此树为根树.
1.树根:入度为0的结点.
2.叶:出度为0的结点.
3.分支结点(内结点):出度不为0的结点.
4.父结点与子结点:如果<vi,vj>是根树中
的一条边,则称vi是vj的父结点, vj是vi的子结点.
5.祖先结点与后裔结点: 在根树中,如果从vi到vj有路,则称
vi是vj的祖先结点, vj是vi的后裔结点.
6.根树结点的层次:从根结点到某个结点的路径的长度,称为该结点的层次. 同一层次的结点称为兄弟结点.
7.树高:从树根到各个叶结点的路径中, 最长路径的长度,
称为该树的高度(树高).
三.举例:
a)语法树
b)算术表达式树
((a+b)÷c)×(d－e)
c)判定树:有四枚金币a,b,c,d,已知道三个是真的,最多一个
是假的,它们的外表完全相同,只是重量有点差别.给你一
架天平找出假币.
你有8个一样大小的球，其中7个的重量是一样的，另一个比较重。怎样能够用天平仅称两次将那个重一些的球找出来。
d)搜索树:八数码游戏:
搜索策略:
宽度优先,
深度优先,
启发式搜索,….
开始结点
目标结点
…………………..
…………………..
四.有序树
如前面的算术表达式树, 家谱树,都是有序树, 即同一层
的结点是有次序的, 如家谱树,最左边是老大,其次是老二,
依此类推.
定义:在有向树中,如果规定了每一层上的结点的次序,称
之为有序树.
算术表达式树:
((a+b)÷c)×(d－e)
五.m叉树与完全m叉树
叉树:在根树中,如果每个结点的出度最大是m, 则称此
树是m叉树.
2.完全m叉树:在根树中,如果每个结点的出度都是m或者
等于0, 则称此树是完全m叉树.
3. 正则m叉树:在完全m叉树中,如果所有树叶的层次相同,
则称之为正则m叉树.
定理 T是棵完全m叉树, 有t个叶结点, i个分支结点,
则(m-1)i=t -1 .
证明:T的所有结点的出度总和为 mi. 入度总和(i-1)+t. 故
mi=i-1+t 所以(m-1)i=t-1
六. 二叉树的存贮
二叉树便于在计算机内存贮, 设有算术表达式;
(3－(2×x))+((x-2)÷(3+x)
存贮时,每个结点含有三个信息:
left-----是左指针,指向左子结点.
data----数据
right---右指针, 指向右子结点.
表达式的存贮树:
(3－(2×x))+((x-2)÷(3+x)
如果使用矩阵表示此树,需要13×13的矩阵, 需要169
单元存贮空间,而且矩阵中有很多0. 显然冗余太多.
我们用三个一维数组构成的序列表示这棵树:
head
0 表示无左(右)子结点
只用了42个存贮单元,
可见节省内存.
七. m叉有序树转化成二叉树
因为二叉树便于存贮, 也便于处理, 所以通常可以将多叉
树化成二叉树.方法是:
1.每个结点保留左儿子结点, 剪掉右边其分支. 被剪掉
的结点如下处理(重新嫁接).
2.同一个层次的结点, 从左到右依次画出(被剪掉的结点 嫁接到它的哥哥结点上).
八.遍历二叉树
在二叉树的一些应用中, 常常要在树中查找具有某些
特征的结点,或者对所有结点逐一进行某种处理, 这就提
出了遍历二叉树问题. 即按照一定规律巡访树中每个结点
一次.
由于二叉树是一个非线性结构, 每个结点都可能在左右
两棵子树上, 为此要寻找一种规律, 以便使二叉树上结点
的信息排成一个线性队列上, 从而便于遍历.
有三种遍历方式
1.先序遍历
2.中序遍历
3.后序遍历
1.先序遍历
⑴ 访问根结点.
⑵ 先序遍历左子树
⑶ 先序遍历右子树
结果:＋－3×2－x2÷x＋3x
2.中序遍历
⑴ 中序遍历左子树
⑵ 访问根结点.
⑶ 中序遍历右子树
结果:3－2×x－2＋x÷3＋x
3.后序遍历
⑴ 后序遍历左子树
⑵ 后序遍历右子树
⑶ 访问根结点. 后序遍历:32x2－×－x3x＋÷＋
九. 最优树(哈夫曼树 Huffman)
问题的提出: 数据通讯时,需要将信息编码, 即用二进制
符号串表示信息.
例如要传送的报文为:“ABACCDA” , 只有4个基本符号,
只要二位二进制符号就可以分辨. 设A,B,C,D的编码分别
是“00,01,10,11”. 这样上述报文“ABACCDA”可翻译成
“00010010101100”, 译文含有14个符号.
这种编码各个符号的编码是等长等. 当然这样的编码在
报文的接收端容易译码.
但是在发送报文时,总是希望报文最短, 节约开支. 所以
等长的编码不是最优的, 因为在报文中各个符号出现的频
率是不同的. 所以考虑用不等长的编码, 应该使得在报文
中出现频率最高的符号编码最短.
比如A,B,C,D的编码分别为: 0,00,1,01. 这样此报文的译
文为:“000011010”, 译文的长度是短了,只有9个符号, 但是
在报文的接收端如何翻译成原文呢?比如译文中的“0000”
是“AAAA”还是“BB”,还是“”ABA”, 无法翻译.
产生这个问题的原因是:有的符号的编码是另一个符号编
码的前缀. 比如A的编码“0”,是B编码“00”的前缀.这样就
无法翻译报文.
二叉树的一个重要应用就是最优树.
1.带权二叉树的定义:设有一组权值:w1, w2, w3,… , wm,不
仿设w1≤w2≤w3≤…≤wm, 设有一棵二叉树有m片叶子,
分别带有权值w1, w2, w3,… , wm,称此树为带权二叉树.
例如:下边是有叶结点a,b,c,d, 分别带有权7,5,2,3的二叉树:
2. 带权树T的权W(T):
W(T)=
其中L(wi)是标有权wi的叶结点的从根到该叶结点的路长.
上例中: W(T1)=7×2＋5×2＋2×2＋3×2=34
W(T2)=3×2＋7×3＋5×3＋2×1=44
W(T3)=7×1＋5×2＋2×3＋3×3=32
由此看出W(T3)是比较小的.
3.最优树: 带权树中,权数最少的二叉树.
4.画最优树的算法---哈夫曼算法:
⑴ 先将权按照升序排序,设为w1≤w2≤w3≤…≤wm.
⑵ 以w1和w2为儿子结点, 构造它们的父结点,且其权为 w1+w2 , 并从权的序列中去掉w1和w2 。
⑶ w1+w2再与其余权一起排序, 再从此队列中取出前面两个权值为儿子结点, 同⑵的方法构造它们的父结点.
依此类推, 直至最后. 即得到最优树.
例如,给定一组权:2,3,5,7,11,13,17,19,23. 构造一棵最优树.
5
7
17
5,5,7,11,13,17,19,23
2,3,5,7,11,13,17,19,23
7,10,11,13,17,19,23
11,13,17,17,19,23
17,17,19,23,24
19,23,24,34
24,34,42
42,58
100
5. 最优树的应用举例
⑴用于程序设计
例如编写一个将百计分a转换成五计分的程序,如果这样:
if a<60
then b=“不及格”
else if a<70
then b=“及格”
else if a<80
then b=“中等”
else if a<90
then b=“良好”
else b=“优秀”
上述程序是正确的,但不是最优的,.
衡量一个程序是否优化:
a)空间复杂性:一个是看它在运行时需要使用的存贮空间
的大小,
b)时间复杂性:还要看它运行时间的长短.
显然在分数正态分布情况下,上述程序运行的时间,不是最
优的. 设分数的分布如下:
分数: 0-59 60-69 70-79 80-89 90-100
比例(%): 5 15 40 30 10
可见在分数正态分布的情况下,上述程序中,有80%的分数,
至少要比较3次(因为 80%的分数>70分)才得出结果.
那么如何设计这个程序才合理呢?就是按最优树来设计.
分数: 0-59 60-69 70-79 80-89 90-100
比例(%): 5 15 40 30 10
设权序列为: 5,10,15,30,40 构造最优树:
为了使得判断框内只比较一次,流程图可以改成下面框图:
在分数正态分布下,按照这个流程图,编制程序,比较合理.
⑵前缀码(哈夫曼编码)
a) 问题的提出: 数据通讯时,需要将信息编码, 即用二进制
符号串表示信息.
例如要传送的报文为:“ABACCDA” , 只有4个基本符号,
只要二位二进制符号就可以分辨. 设A,B,C,D的编码分别
是“00,01,10,11”. 这样上述报文“ABACCDA”可翻译成
“00010010101100”, 译文含有14个符号.
这种编码各个符号的编码是等长等. 当然这样的编码在
报文的接收端容易译码.
但是在发送报文时,总是希望报文最短, 节约开支. 所以
等长的编码不是最优的, 因为在报文中各个符号出现的频
率是不同的. 所以考虑用不等长的编码, 应该使得在报文
中出现频率最高的符号编码最短.
比如A,B,C,D的编码分别为: 0,00,1,01. 这样此报文的译
文为:“000011010”, 译文的长度是短了,只有9个符号, 但是
在报文的接收端如何翻译成原文呢?比如译文中的“0000”
是“AAAA”还是“BB”,还是“”ABA”, 无法翻译.
产生这个问题的原因是:有的符号的编码是另一个符号编
码的前缀. 比如A的编码“0”,是B编码“00”的前缀.这样就
无法翻译报文.
直接促使我们设计前缀码.
b)前缀码的定义:一个符号的编码不是另一个符号编码的
前缀.
c)前缀码的设计:
每棵二叉树对应一组前缀码. 在
二叉树的边上,将每个结点下面的
两条边分别标上0和1, 然后从根到
叶,把这个路径的边上所标的0-1符
号串写下来,就是这个叶结点对应的前缀码.
反之,任何一组前缀码也对应一棵二叉树.
例如有一组前缀码{1,01,001,000},因为中最长的编码000,
有3位,可以画一棵高度为3的二叉树,如图:
现在再回到前面的问题,对报文“ABACCDA”设计编码.
先计算各个符号在报文中出现的频率:A,B,C,D的频率分
别是:43%,14%,29%,14% . 分别表示成权(43,14,29,14)
对权排序:14,14,29,43
画最优树:
编码是: A, B, C, D
0, 100, 11, 101.
原报文“ABACCDA”译文:
“0100011111010”有13位.
那么在接收端如何译码呢?
就是将译文中符号从头读,
顺着这棵最优树,反复从根到叶找前缀码.
比如有如下报文“01110110111100111100100”
原文是“AC D D C B C CAAB ”
作业 P337 (1), (2), (3), (5)a) b) , (6), (8)
图 论 小 结
一.图的概念
图的定义, 有向边,无向边,平行边,环
邻接点,邻接边, 孤立结点
有向图, 无向图,简单图,混合图,零图,平凡图,多重图,
完全图,子图, 生成子图,补图,
结点的度, 结点的出度, 结点的入度,
图的最大度Δ(G),最小度δ(G),
深入了解图所有结点度数总和与边的关系, 出度和与入度和关系
掌握图的同构的概念，并会判定同构的图。
定理 每个无向图所有结点度总和等于边数的2倍.
定理(握手定理)每个无向图中,奇数度的结点必为偶数个.
定理 G=<V,E>是有向图, 则G的所有结点的出度之和等于入度之和.
定理 无向完全图Kn, 有边数n(n-1)/2.
定理 有n个结点的有向简单完全图有边数为n(n-1).
二.路与回路
路,回路,迹,闭迹,通路,圈
无向图的连通性:
连通图,连通分支,连通分支数W(G),点割集,割点,点连通度k(G),
边割集,割边(桥),边连通度λ(G)
结点间的距离, 图的直径
有向图的连通性:可达性,强连通,单侧连通,弱连通, 强分图,单侧分图,弱分图.(会求这些分图)
定理 在一个有n个结点的图中,如果从结点vi到vj存在一条路,则从vi到vj必存在一条长度不多于n-1的路.
定理 图G=<V,E>是连通的,当且仅当 对V的任何分成V1、V2的划分,恒存在一条边, 使得它的两个端点分别属于V1和V2.
定理 一个连通图中结点v是割点的充分且必要条件
是存在两个结点u和w, 使得从u到w的任何路都通过 v .
定理 一个有向图G是强连通的,当且仅当G中有一个
回路, 此回路至少包含每个结点一次.
定理 在有向图中,每个结点必位于一个且只位于一个
强分图中.
三.图的矩阵
*邻接矩阵A:结点与结点之间的邻接关系矩阵.
根据邻接矩阵判断:各结点的度, 有向图结点出,入度.
由Ak可以求一个结点到另一个结点长度为k的路条数.
可达矩阵P:结点u到结点v的可达性的矩阵.
用P可以判定:各结点的度. 有向图的强分图.
关联矩阵M:是结点与边的关联关系矩阵.
用M判定:各结点的度
定理设G=<V,E>是简单图,V={v1,v2, v3,…,vn}, G的邻接矩阵(A(G))k中的第 i行第j列元素aijk=m, 表示在图G中从vi到vj长度为k的路有m条.可以用归纳法证明.(见教材P290)
可达矩阵P为:
方法1. 按照矩阵相乘分别求出A(k) (k≥2), 然后再∨.
方法2.用求传递闭包的Warshall算法,见P124.
四.欧拉图与汉密尔顿图(会判定)
欧拉路,欧拉回路,欧拉图.
判定:有欧拉路的充要条件:无或有两个奇数度的结点.
有欧拉回路的充要条件:所有结点度数均为偶数.
汉密尔顿路,汉密尔顿回路,汉密尔顿图
汉密尔顿图的判定:
必要条件:V的任何非空子集S,有W(G-S)≤|S|
充分条件:每对结点的度数和≥|V| =n
定理 无向图G具有欧拉路,当且仅当G是连通的,且有零个或两个奇数度的结点.
定理 (充分条件):G是完全图,则G是H图.
定理(充分条件)设G是有n个结点的简单图,若对G中每对结点度数之和大于n-1(n),则G有一条H路(H回路).
定理 (必要条件) 若图G=<V,E>有H回路,则对V的任何非空子有限集S, 均有W(G-S)≤|S|, 其中W(G-S)是从G中删去S中所有结点及与这些结点关联的边所得到的子图的连通分支数.
五.二部图 作为一般了解, 但要掌握K3,3 。
六.平面图
平面图的定义,平面的边界,
* 欧拉公式: v-e+r=2
判定:必要条件: e≤3v-6
*充要条件:G不含与K5或K3,3在2度结点内同构子图.
七.对偶图与着色
会画对偶图, 会对图正常着色（韦尔奇.鲍威尔法 ）
定理 G=<V,E>是二部图 当且仅当它的所有回路的长度都是偶数.
定理 G是个连通的平面图, 设v、e、r分别表示G中结点数、边数、面数, 则有 v-e+r=2. 称此式为欧拉公式.
定理(必要条件) 设G是有v 个结点、
e条边的连通简单平面图, 若v≥3, 则 e≤3v-6.
定理 (Kuratowski定理)一个图是平面图的充分且必要条件是它不含有任何与K5、K3,3在2度结点内同构的子图.
*八.树与生成树
树的定义:6个定义,其中最主要的是连通无回路, e=v-1
分支结点, 叶结点, 会求最小生成树
*九. 根树
m叉树,完全 m叉树, (m-1)i=t-1
m叉树变成二叉树
会画最优树, 会设计前缀码
Kruskal算法(克鲁斯卡尔 )
定理 T是棵完全m叉树, 有t个叶结点, i个分支结点,则(m-1)i=t -1 .
定理给定图T, 以下关于树的定义是等价的.
⑴无回路的连通图.
⑵无回路且e=v-1 其中e是T的边数,v是T的结点数.
⑶连通的且e=v-1.
⑷无回路但添加一条新边则得到一条仅有的回路.
⑸连通的,但删去任一条边,T便不连通.
⑹每对结点之间有一条且仅有一条路.
习 题 课
P279(1)证明任何有向简单完全图中,所有结点的入度平方
之和等于所有结点出度平方之和. (设图有n个结点)
证明: 因有向简单完全图中每个结点v:
degi(v) =dego(v) =n-1
故,所有结点的入度平方之和等于所有结点出度平方之和.
或者∑(degi(v))2 -∑(dego(v))2 = ∑[(degi(v))2 -(dego(v))2]
= ∑{[(degi(v))+(dego(v))] [(degi(v)) -(dego(v))]}
= 2(n-1)∑{[(degi(v)) -(dego(v))]}
=2(n-1) {∑degi(v) -∑dego(v)}=2n(n-1)0=0
所以∑(degi(v))2 =∑(dego(v))2
(2)画出右图的补图.
(4)证明下面两个图是同构的.
再验证边之间的对应关系.
(5)一个图与它的补图同构,称为自补图.
c).一个图是自补图,其对应的完全图的边数是偶数.
证明:此命题显然成立,因为一个图与其补图同构,则它们
的边数相等, 于是它们对应完全图的边数为它们边数的和
所以该完全图的边数是偶数.
a).给出5个结点的自补图.
b)是否有3个结点或6个结点的自补图.
解:不存在.因为K3与K6 的边数分别是3和15.
P287(3)证明如果图G是不连通的,则它的补图 是连通的.
证明:任取u,v∈V(G),
如果u与v在G中不邻接,则在 中有边(u,v),所以在
中 u与v是连通的.
如果在G中u与v邻接, 则u与v在G的同一个连通分支,
例如 u,v∈V1(G)(即由结点集合V1构成的连通分支G(V1)),
由于G是不连通的,所以G必有另一个连通分支G(V2), 设
结点w∈V2(G), 于是在 中必有边(u,w),(w,v),于是在 中
必有路uwv, 所以 是连通的.
(5)分析右图,求
a)从A到F的所有通路.
通路:路中结点不同.
ABCF ABEF ADEF ABECF ABCEF ADECF
ADEBCF
b)从A到F的所有迹.
迹:路中边不同.
ABCF ABEF ADEF ABECF ABCEF ADECF
ADEBCF ADEBCEF
c) A和F之间的距离.
距离:就是最短的路长.
A和F之间的距离为3.
(8)求右图的图G的强分图,单侧分图和弱分图.
解:找强分图:在回路中的结点构成
一个强分图,其余结点自己构成各自
的强分图.
强分图有:{1,2,3},{4},{5},{6}各自导出的子图.
单侧分图:{1,2,3,4,5,6}导出的子图.
弱分图: G本身.
P300(3)求右图的邻接矩阵,可达矩阵和距离矩阵.
解:
P=A∨A(2)∨A(3)∨A(4)∨A(5)
距离矩阵D: 将各个Ai中非0元素取最小的i;
主对角线为0;
在P中主对角线以外的0变成∞.
定理―3设G是任一(n,m)无向简单图,ω是其分图个数,则
证 先证n-ω≤m。对m作归纳。
m=0时,G是零图,ω=n,命题成立。设m-1时成立,现证明m时也成立。我们从G上删去一条边得G′,G′有两种可能:
(i)有n个顶点,ω个分图,m-1条边,根据归纳假设n-ω≤m-1,显然在G中成立n-ω≤m。
(ii) 有n个顶点,ω+1个分图,m-1条边,根据归纳假设n-(ω+1)≤m-1,显然在G中成立n-ω≤m。
P311(1)判定下面图是否能一笔画.
因为这两个图中,都只有两个奇数度的结点, 有欧拉路, 所
以可以一笔画.
(2)构造一个欧拉图,使得结点数 v和边数e满足:
a)v,e奇偶性一样. b)v,e奇偶性相反.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
(3) n取何值时,完全图Kn是个欧拉图.
解: 因为Kn有n个结点, 每个结点的度数是n-1, 要使n-1为
偶数, 必使n=3,5,7,…等奇数.
(6)a)画一个有一条欧拉回路和一条汉密尔顿回路的图.
b画一个有一条欧拉回路但没有一条汉密尔顿回路的图.
c)画一个没有一条欧拉回路但有一条汉密尔顿回路的图.
P 317(6)证明：在6个结点12条边的连通平面简单图中，
每个面由3条边围成.
证明:因为G中所有面的边界长总和为边数的2倍. 即
∑deg(r)=2×12=24, 由欧拉公式得;r=2-v+e=2-6+12=8
而G中无环和平行边, 24/8=3 所以每个面由3条边围成.
(1)证明:若G是每一个面至少由k(k≥3)条边围成的连通平
面图,则, ,这里v,e分别是G的结点数和边数.
证明:设G中有r个面,因为G中所有面的边界长总和为边数
的2倍. 所以 2e≥kr, 所以r≤ ,代入欧拉公式得:
v-e+ ≥2
(5)如果可能, 把下面画成平面图,否则说明它包含一个与
K5或K3,3在2度结点内同构子图.
(7)证明a)对于K5中任何边e, K5 -e 是平面图.
b).对于K3,3中任何边e, K3,3 -e 是平面图.
P321(1)画出下面各图的对偶图.
(3)用韦尔奇.鲍威尔法,对下面各图着色. 求图的着色数.
(a)图课堂已作.
(b)结点按照度数降序排序:
F,B, A,C,E,G,D,H
可见此图是4色的.
(7)a)一个完全图K6 的边涂上红色或者蓝色,证明对于任何
一种随意涂边的方法,总有一个完全图K3 的所有边被涂上
红色,或者涂上蓝色.
证明:因为K6中任何结点都有5条边与之关联, 这5条边图
上红色或者蓝色, 那么必有要么3边是红色,要么3边是蓝
色, 如图所示.我们假设
3条边涂上红色,而这3条
边的另一端的3个结点之
间3条边构成一个三角形,
下面考察这3条边涂的颜色, 如果至少有一条边是涂红色,
则与上边两条红色边构成一个红色的三角形.如果没有一
条涂红色,那么这个下面的三角形就是全是蓝色的边.
对于开始时3边都涂蓝色,类似证明结论成立.
b)证明6个人的人群中,或者有3个人相互认识,或者有3个
人彼此陌生.
证明:以6个人为结点画一个K6图,如果两个相互认识就把
相应边涂上红色,如果彼此陌生就涂上蓝色. 由a)的结论得
必有三个人它们构成的三角形的三条边要么都涂上红色,
要么都涂上蓝色.
P327(3)一棵树T有n2个结点度数为2,n3个结点度数为3,…
nk个结点度数为k,问它有多少个度数为1的结点?
解:设有n1个度数为1的结点, 又令T有v个结点,e条边.于是
v= n1+n2+…+nk
T的所有结点度数总和= n1+2n2+…+knk=2e
因e=v-1 ∴ n1+2n2+…+knk=2(n1+n2+…+nk -1)
∴ n1= n3+2n4+…+(k-2)nk+2
(2).一棵树T有两个结点度数为2,一个结点度数为3,三个结
点度数为4,问它有多少个度数为1的结点?
解:设有n1个度数为1的结点, 又令T有v个结点,e条边.于是
v= n1+2+1+3= n1+6
T的所有结点度数总和=n1+2×2+1×3+3×4=n1+19=2e
因e=v-1 ∴ n1+19=2(n1+6-1) ∴ n1=9
(6).给定图G如图所示,用Kruskal算法,求G的一棵最小生
成树.
P337(1)从简单有向图的邻接矩阵如何判定它是否为根
树?如果是根树,如何判定树根和树叶.
解:先看个例子:
根:入度为0----列为0的结点 叶:出度为0----行为0的结点
(2)求出右图的二叉树.
(3). 证明完全二叉树T中,边的总数等于2(nt -1),其中nt是叶
结点数.
证明:由完全m叉树公式 (m-1)i=t-1
这里t=nt , ∴(2-1)i=nt -1, ∴ i=nt -1,
∴T中总的结点数v为:
v=i+nt =(nt -1)+nt=2nt -1
T的边数e=v-1= 2nt -1-1= 2nt -2
=2(nt -1)
(5)给定一组权:1,4,9,16,25,36,49,64,81,100
a)构造一棵最优完全二叉树.
b)构造一棵最优完全三叉树.
c)构造一棵最优完全m叉树.
1,4,9,16,25,36,49,64,81,100
5,9,16,25,36,49,64,81,100
14,16,25,36,49,64,81,100
25,30,36,49,64,81,100
36,49,55,64,81,100
55,64,81,85,100
81,85,100,119
100,119,166
166,219
9
16
25
100
81
64
385
解:a)权: 1,4,9,16,25,36,49,64,81,100
b)权: 1,4,9,16,25,36,49,64,81,100
注意:在画最优三叉树时要考虑是否补充权为0的结点:先
在前面取3个结点,以后的结点每两个一组,看分到最后是
否还是两个元素,如果最后只有一个元素,则要补充一个权
为0的结点,以确保三叉.
100
0,1,4,9,16,25,36,49,64,81,100
5,9,16,25,36,49,64,81,100
25,30,36,49,64,81,100
49,64,81,91,100
91,100,194
385
c).为构造最优m叉树, 要事先看一看是否需要补充权:
权排序后,从前面分出m个,再把余下的每m-1 个分成一
组,看看最后是否有m-1个, 如果最后只有k(k<m-1)个,则
要在权序列的前面补充m-1-k个0, 以后再按照画m叉最优
树的方法画最优树.
(8)给出公式(P∨(P∧Q))∧((P∨Q)∧R)的根树表示.
谢谢大家！
