总 结
第八章 图论
8.1 图的基本概念
8.1.1 图
定义8.1―1 一个图G 是一个三重组〈V (G ), E (G ), ΦG 〉, 其中V (G ) 是一个非空的结点(或叫顶点) 集合, E (G ) 是边的集合, ΦG 是从边集E 到结点偶对集合上的函数。一个图可以用一个图形表示。 定义中的结点偶对可以是有序的, 也可以是无序的。若边e 所对应的偶对〈a , b 〉是有序的, 则称e 是有向边。有向边简称弧, a 叫弧e 的始点, b 叫弧e 的终点, 统称为e 的端点。称e 是关联于结点a 和b 的, 结点a 和结点b 是邻接的。若边e 所对应的偶对(a , b ) 是无序的, 则称e 是无向边。无向边简称棱, 除无始点和终点的术语外, 其它术语与有向边相同 每一条边都是有向边的图称为有向图。每一条边都是无向边的图称为无向图。 有向图和无向图也可互相转化。例如, 把无向图中每一条边都看作两条方向不同的有向边, 这时无向图就成为有向图。又如, 把有向图中每条有向边都看作无向边, 就得到无向图。这个无向图习惯上叫做该有向图的底图。
在图中, 不与任何结点邻接的结点称为弧立结点。全由孤立结点构成的图称为零图。关联于同一结点的一条边称为自回路。
在有向图中, 两结点间(包括结点自身间) 若同始点和同终点的边多于一条, 则这几条边称为平行边。在无向图中, 两结点间(包括结点自身间) 若多于一条边, 则称这几条边为平行边。两结点a 、b 间互相平行的边的条数称为边［a , b ］的重数。仅有一条时重数为1, 无边时重数为0。
定义8.1―2 含有平行边的图称为多重图。非多重图称为线图。无自回路的线图称为简单图。仅有一个结点的简单图称为平凡图。
定义 8.1―3 赋权图G 是一个三重组〈V , E , g 〉或四重组〈V , E , f , g 〉, 其中V 是结点集合, E 是边的集合, f 是定义在V 上的函数, g 是定义在E 上的函数。
8.1.2 结点的次数
定义 8.1―4 在有向图中, 对于任何结点v , 以v 为始点的边的条数称为结点v 的引出次数(或出度) , 记为deg +(v ); 以v 为终点的边的条数称为结点v 的引入次数(或入度) , 记为deg -(v ); 结点v 的引出次数和引入次数之和称为结点v 的次数(或度数) , 记作deg (v ) 。在无向图中, 结点v 的次数是与结点v 相关联的边的条数, 也记为deg (v ) 。孤立结点的次数为零。 定理8.1―1 设G 是一个(n , m ) 图, 它的结点集合为V ={v 1, v 2,…,v n},则
n deg(υi ) =2m i =1定理8.1―2 在图中, 次数为奇数的结点必为偶数个。
定义8.1―5 各结点的次数均相同的图称为正则图, 各结点的次数均为k 时称为k ―正则图。 ∑
8.1.3 图的同构
定义8.1.6 设G =〈V , E 〉和G ′=〈V ′, E ′〉是两个图, 若存在从V 到V ′的双射函数
Φ, 使对任意a 、b ∈V , ［a , b ∈E 当且仅当［Φ(a ), Φ(b ) ］∈E ′, 并且［a , b ］和［Φ(a ), Φ(b ) ］有相同的重数, 则称G 和G ′是同构的。 8.1.4 图的运算
定义8.1―7 设图G 1=〈V 1, E 1〉和图G 2=〈V 2, E 2〉。
(1)G 1与G 2的并, 定义为图G 3＝〈V 3, E 3〉, 其中V 3=V 1∪V 2, E 3=E 1∪E 2, 记为G 3=G 1∪G 2。
(2)G 1与G 2的交, 定义为图G 3＝〈V 3, E 3〉, 其中V 3=V 1∩V 2, E 3=E 1∩E 2, 记为G 3=G 1∩G 2。
(3)G 1与G 2的差, 定义为图G 3＝〈V 3, E 3〉, 其中E 3=E 1-E 2, V 3=(V 1-V 2) ∪{E 3中边所关联的顶点},记为G 3=G 1-G 2。
(4)G 1与G 2的环和, 定义为图G 3＝〈V 3, E 3〉, G 3=(G 1∪G 2)-(G 1∩G 2), 记为G 3=G 1 G 2。
除以上4种运算外, 还有以下两种操作:
(1) 删去图G 的一条边e ;
(2) 删去图G 的一个结点v 。它的实际意义是删去结点v 和与v 关联的所有边。
8.1.5 子图与补图
定义8.1―8 设G =〈V , E 〉和G ′=〈V ′, E ′〉是两个图。 (1) 如果V ′⊆V 和E ′⊆E , 则称G ′是G 的子图。如果V ′⊆V 和E ′⊆E , 则称G ′≠G 的真子图。(注意:“G ′是图”已隐含着“E ′中的边仅关联V ′中的结点”的意义。)
(2) 如果V ′=V 和E ′⊆E , 则称G ′为G 的生成子图。
(3) 若子图G ′中没有孤立结点, G ′由E ′唯一确定, 则称G ′为由边集E ′导出的子图。
(4)若在子图G ′中, 对V ′中的任意二结点u 、v , 当［u , v ］∈E 时有［u , v ］∈E ′, 则G ′由V ′唯一确定, 此时称G ′为由结点集V ′导出的子图。
定义8.1―9在n 个结点的有向图G =〈V , E 〉中, 如果E =V ×V , 则称G 为有向完全图; 在n 个结点的无向图G =〈V , E 〉中, 如果任何两个不同结点间都恰有一条边, 则称G 为无向完全图, 记为Kn 。
定义8.1―10 设线图G =〈V , E 〉有n 个顶点, 线图H =〈V , E ′〉也有同样的顶点, 而E ′是由n 个顶点的完全图的边删去E 所得, 则图H 称为图G 的补图, 记为 H = G 显然, G = G 。
8.2 路径和回路
8.2.1 基本概念
定义8.2―1在有向图中, 从顶点v 0到顶点vn 的一条路径是图的一个点边交替序列（v 0e 1v 1e 2v 2…envn ）, 其中vi -1和vi 分别是边ei 的始点和终点, i =1,2,…,n 。在序列中, 如果同一条边不出现两次, 则称此路径是简单路径, 如果同一顶点不出现两次, 则称此路径是基本路径(或叫链) 。如果路径的始点v 0和终点vn 相重合, 即v 0=vn , 则此路径称为回路, 没有相同边的回路称为简单回路, 通过各顶点不超过一次的回路称为基本回路。
定义8.2―2 路径P 中所含边的条数称为路径P 的长度。长度为0的路径定义为单独一个顶点。(但注意习惯上不定义长度为0的回路。)
定理8.2―1 在一个具有n 个结点的简单图G =〈V , E 〉中, 如果从v 1到v 2有一条路径, 则从v 1到v 2有一条长度不大于n -1的基本路径。
定理8.2―2 在一个具有n 个结点的简单图G =〈V , E 〉中, 如果经v 1有一条简单回路, 则经v 1有一条长度不超过n 的基本回路。
定义8.2―3 在图G =〈V , E 〉中, 从结点vi 到v j 最短路径的长度叫从vi 到v j 的距离, 记为
d (vi , v j) 。若从vi 到v j 不存在路径, 则d (vi , v j)=∞。
注意, 在有向图中, d (vi , v j) 不一定等于d (v j, vi ), 但一般地满足以下性质:
(1) d (vi , v j) ≥0;
(2) d (vi , vi )=0;
(3) d (vi , v j)+d (v j, v k) ≥d (vi , v k) 。
8.2.2 图的连通度
定义8.2―4设G =〈V , E 〉是图, 且vi 、v j ∈V 。如果从vi 到v j 存在一条路径, 则称v j 从vi 可达。vi 自身认为从vi 可达。
定义8.2―5在无向图G 中, 如果任两结点可达, 则称图G 是连通的; 如果G 的子图G ′是连通的, 没有包含G ′的更大的子图G ″是连通的, 则称G ′是G 的连通分图(简称分图) 。
一个无向图或者是一个连通图, 如图8.2―2(a ) 所示, 或者是由若干个连通分图组成, 如图
8.2―2(b ) 所示。
图 8.2―2
定理8.2―3 设G 是任一(n , m ) 无向简单图, ω是其分图个数, 则
1 n -ω≤m ≤(n -ω)(n -ω+1) 2
定义8.2―11在有向图中, 如果在任两结点偶对中, 至少从一个结点到另一个结点是可达的, 则称图G 是单向连通的; 如果在任两结点偶对中, 两结点都互相可达, 则称图G 是强连通的; 如果它的底图是强连通的, 则称图G 是弱连通的。
显然, 强连通的也一定是单向连通和弱连通的, 单向连通的一定是弱连通的, 但其逆均不真。在图8.2―3中,(a ) 是强连通的,(b ) 是单向连通的,(c ) 是弱连通的。
图 8.2―3
定义8.2―12 在有向图G =〈V , E 〉中, G ′是G 的子图, 若G ′是强连通的(单向连通的, 弱连通的), 没有包含G ′的更大子图G ″是强连通的(单向连通的, 弱连通的), 则称G ′是G 的强分图(单向分图, 弱分图) 。
在图8.2―4中, 强分图集合是:
{〈{1,2,3},{e 1, e 2, e 3}〉, 〈{4},φ〉, 〈{5},φ〉, 〈｛6｝, φ〉, 〈｛7,8｝,{e 7, e 8}〉｝
单向分图集合是:
{〈{1,2,3,4,5},{e 1, e 2, e 3, e
4,
e 5}〉, 〈{6,5},{e 6}〉, 〈｛7,8｝,{e 7, e 8}〉｝
弱分图集合是:
{〈{1,2,3,4,5,6},{e 1, e 2, e 3, e 4, e 5, e 6}〉, 〈｛7,8｝,{e 7, e 8}〉｝
图 8.2―4
8.2.3 赋权图中的最短路径
设G =〈V , E , W 〉是个赋权图, W 是从E 到正实数集合的函数, 边［i , j ］的权记为W (i , j ), 称为边的长度。若i 和j 之间没有边, 那么W (i , j )=∞。路径P 的长度定义为路径中边的长度之和, 记为W (P ) 。图G 中从结点u 到结点v 的距离记为d (u , v ), 定义为
min{W (P )|P 为G 中从u 到v 的路径}
∞ 当从u 到v 不可达时
本小节主要讨论在一个赋权的简单连通无向图
G =〈V , E ,W 〉中, 求一结点a (称为源点) 到其它结点x 的最短路径的长度, 通常称它为单源问题。下面介绍1959
年迪克斯特拉(E .W.Dijkstra) 提出的单源问题的算法, 其要点如下:
(1) 把V 分成两个子集S 和T 。初始时,S={a },T =V -S 。
(2) 对T 中每一元素t 计算D (t ), 根据D (t ) 值找出T 中距a 最短的一结点x, 写出a 到x 的最短路径的长度D (x ) 。
(3)置S 为S ∪{x },置T 为T -{x },若T = , 则停止, 否则再重复2。
8.2.4 欧拉路径和欧拉回路
哥尼斯堡(Konig s berg , 现加里宁格勒) 位于普雷格尔(Prege l) 河畔, 河中有两岛。城市的各部分由7座桥接通, 如图8.2―8(a ) 所示。古时城中居民热衷于一个问题:游人从任一地点出发, 怎样才能做到穿过每座桥一次且仅一次后又返回原出发地。1736年欧拉用图论方法解决了此问题, 写了第一篇图论的论文, 从而成为图论的创始人。
不难看出, 如果用结点代表陆地, 用边代表桥, 哥尼斯堡七桥问题就等价在于图8.2―8(b ) 中找到这样一条路径, 它穿程每条边一次且仅一次。
穿程于图G 的每条边一次且仅一次的路径, 称为欧拉路径。穿程于图G 的每条边一次且仅一次的回路, 称为欧拉回路, 具有欧拉回路的图称为欧拉图。
显然, 具有欧拉路径的图除孤立结点外是连通的, 而孤立结点不影响欧拉路径的讨论。因此, 下边讨论欧拉路径有关问题时均假定图是连通的。
图 8.2―8
定理8.2―10无向连通图G 具有一条欧拉路径当且仅当G 具有零个或两个奇数次数的顶点。
定理8.2―11一个有向连通图具有欧拉回路, 当且仅当它的每个顶点的引入次数等于引出次数。一个有向连通图具有欧拉路径, 当且仅当它的每个顶点的引入次数等于引出次数, 可能有两个顶点是例外, 其中一个顶点的引入次数比它的引出次数大1, 另一个顶点的引入次数比它的引出次数小1。
8.2.5 哈密尔顿路径与哈密尔顿回路
在无向图G =〈V , E 〉中, 穿程于G 的每个结点一次且仅一次的路径称为哈密尔顿路径。穿程于G 的每个结点一次且仅一次的回路称为哈密尔顿回路。具有哈密尔顿回路的图称为哈密尔顿图。
哈密尔顿, 爱尔兰数学家,1859年他首先提出这一类问题。它的问题如下:
如何沿12面体的棱线, 通过每个角一次且仅一次?(称为环游全世界游戏。)
定理8.2―12 若G =〈V , E 〉是哈密尔顿图, 则对V 的每个非空真子集S 均成立:
ω(G -S ) ≤｜S ｜
这里|S |表示S 中的顶点数, ω(G -S ) 表示G 删去顶点集S 后得到的图的连通分图个数。 应用本定理可以判定某些图不是哈密尔顿图, 例如, 图8.2―12所示的图, 删去其中3个黑点, 即知此图不符合必要条件, 因而不是哈密尔顿图。但一般要考察多个真子集, 应用不方便, 例4给出了一种较简便的否定一个图是哈密尔顿图的方法, 但也不是通用的。
例4 证明图8.2―13(a ) 中的图没有哈密尔顿路径。
证用A 标记顶点a , 所有与A 邻接的顶点标记为B 。继续不断地用A 标记所有邻接于B 的顶点, 用B 标记所有邻接于A 的顶点, 直到所有顶点标记完, 得到如图8.2―13(b ) 所示的图, 图中有3个顶点标A 和5个顶点标B , 标号A 和B 崐相差2个, 因此不可能存在一条哈密尔顿路径。
图 8.2―13
定理8.2―6中的条件不是充分的, 图8.1―5中给出的彼得森图, 它对任意SV 都满足ω(G -S ) ≤|S |,但不是哈密尔顿图。
定理8.2―13设G =〈V , E 〉是具有n 个顶点的简单无向图, 若在G 中每一对顶点的次数之和大于等于n , 则在G 中存在一条哈密尔顿回路。 1≥推论8.2―13在简单无向图中, 若每一顶点的度数 n (n ≥ 3) , 则该图是哈密尔顿图。 2在有向图中, 也可类似地定义出哈密尔顿有向回路和哈密尔顿有向路径。
8. ３ 图的矩阵表示
定义8.3―1设G =〈V , E 〉是有向线图, 其中V ={v 1, v 2,…,vn },并假定各结点已经有了从v 1到vn 的次序。定义一个n ×n 的矩阵A , 其中各元素a ij 为
:
⎧1a ij v i ,
v j ∈E j ∉E
零图的邻接矩阵的元素全为零, 称为零矩阵。每一顶点都有自回路而无其它边的图的邻接矩阵是单位矩阵。设有向线图G =〈V , E 〉的邻接矩阵是A , 则G 的逆图的邻接矩阵是A 的转置矩阵, 记A 。
定义8.3―2设G =〈V , E 〉是有向线图, 其中｜V ｜=n , 并假定各结点是有序的, 定义一个n ×n 的矩阵P , 它的元素
⎧1 , 当vi 到vj 至少存在一条非零长度的路径0 P ij =⎨ ⎩ 0 , 当vi 到vj 不存在一条非零长度的路径
称矩阵P 为图G 的可达性矩阵。 T
8.5 二部图
定义8.5―1若无向图G =〈V , E 〉的顶点集合V 可以划分成两个子集X 和Y , 使G 中的每一条边e 的一个端点在X 中, 另一个端点在Y 中, 则称G 为二部图或偶图。二部图可记为G =〈X, E,Y 〉,X 和Y 称为互补结点子集。 定义8.5―2二部图G =〈X, E , Y 〉中, 若X 的每一顶点都与
Y 的每一顶点邻接, 则称G 为完全二部图, 记为Km , n , 这里m =｜X ｜, n =｜Y ｜。
图8.5―1给出K 2,4和K 3,3的图示。
图8.5―1
定理8.5―1无向图G =〈V , E 〉为二部图的充分必要条件为G 中所有回路的长度均为偶数。
定义8.5―3给定一个二部图G =〈X, E , Y 〉, 如果E 的子集M 中的边无公共端点, 则称M 为二部图G 的一个匹配。含有最多边数的匹配称为G 的最大匹配。如果二部图G 中的一条链由不属于匹配M 的边和属于M 的边交替组成, 且链的两端点不是M 中边的端点, 那么称此链为G 中关于匹配M 的交替链。
例如, 图8.5―2中的(x 2, y 1, x 3, y 4) 是交替链。最短的交替链是由一条边组成, 该边的两端点不是M 中边的端点。
交替链可用标记法找出, 标记法的过程如下:
首先把X 中所有不是M 的边的端点用()加以标记, 然后交替进行以下所述的过程Ⅰ和Ⅱ。 Ⅰ. 选一个X 的新标记过的结点, 比如说xi , 用(xi ) 标记不通过在M 中的边与xi 邻接且未标记过的Y 的所有结点。对所有X 的新标记过的结点重复这一过程。
Ⅱ. 选一个Y 的新标记过的结点, 比如说y i , 用(yi ) 标记通过M 的边与y i 邻接且未标记过的X 的所有结点。对所有Y 的新标记过结点重复这一过程。
8.6 平面图和图的着色
8.6.1 平面图
定义8.6―1一个无向图G =〈V , E 〉, 如果能把它图示在一平面上, 边与边只在顶点处相交
的图叫
平面图。
图8.6―1所示的是非平面图, 而图8.6―2所示的都是平面图的例子。
8.6.2 欧拉公式
欧拉1750年提出任何一个凸多面体的顶点数n , 棱数m 和面数k 满足公式:
n -m +k =2
参看图8.6―3
为了介绍平面图的欧拉公式, 我们首先介绍什么是平面图的面。我们在平面上画一个平面图, 用小刀沿着边切下, 则这平面将分割成几块, 这种块就称为图的面, 即一个平面图的面定义为平面的一块, 它用边作界线, 并且不再分为子块。例如图8.5―4(a ) 有3个图, 如图8.5―4(b ) 所示。注意沿边a 切, 不再分割面1, 沿边b 和c 切, 也不再分割面3。如果面的面积是有限的, 称该面为有限面, 否则, 称为无限面。显然, 平面图恰有一个无限面。
定理8.6―1 对任何连通平面图恒有
n -m +k =2
即 顶点数-边数+面数=2
定理8.6―2在n ≥3的任何连通平面简单(n , m ) 图中有m ≤3n -6成立。
推论8.6―2 K 5是非平面图。
推论8.6―3 K 3,3不是平面图。
8.6.3 库拉托夫斯基(Kurat ows ki ) 定理
定义8.6―2 K 5和K 3,3称为库拉托夫斯基图。
定义8.6―3两个图G 1和G 2称为在2度顶点内同构的(或称同胚) , 如果它们是同构的, 或者通过反复插入和(或) 除去2度顶点, 它们能变换成同构的图。.
如图8.6―8(a ) 和(b ) 所示。图8.5―8(c ) 中的两个图是在2度顶点内同构的。
定理8.6―4(库拉托夫斯基定理) 一个图是平面图, 当且仅当它不包含任何在2度顶点内和库拉托夫斯基图同构的子图。
8.5.4 对偶图
将平面图G 嵌入平面后, 通过以下手续(简称D 过程):
(1) 对图G 的每个面Di 的内部作一顶点且仅作一顶点v*i;
(2)经过每两个面Di 和Dj 的每一共同边界e*k作一条边e*k=(v *i , vj ) 与ek 相交;
(3)当且仅当ek 只是面Di 的边界时, v *i 恰存在一自回路与ek 相交。
所得的图称为图G 的对偶图, 记为G 。
图8.6―9中, 虚线构成的图是实线构成的图的对偶图。
8.6.6 五色问题
1852年英国一个青年名叫盖思里(Gut h rie ) 提出地图四色问题。在画地图时, 如果规定一条边界分开的两个区域涂不同颜色, 那么任何地图能够只用4种颜色涂色。这个问题成为数学难题, 一百多年来, 许多人的证明都失败了。直至1976年6月美国伊利诺斯大学两位教授阿佩尔(Appe l) 和海肯(Haken ) 利用电子计算机, 计算了1200小时, 证明了四色问题。这件事曾轰动一时。但是用“通常”证明方法来解决四色问题, 至今仍未解决。
引理 在平面连通的简单图中至少有一个顶点v 0, 其次数d (v 0) ≤5。
定理 8.6―7
用
5
种颜色可以给任一平面简单连通图G =〈V , E 〉正常着色。
8.7 树
8.7.1 无向树
定义8.7―1连通而无简单回路的无向图称为无向树, 简称树。树中次数为1的顶点称为树叶。次数大于1的顶点称为分枝点或内部结点。
定义8.7―2一个无向图的诸连通分图均是树时, 称该无向图为森林, 树是森林。 例如图8.7―1(a)、(b)所示的都是树,(c)所示的是森林。
定理8.7―1无向图T 是树, 当且仅当下列5条之一成立。(或者说, 这5条的任一条都可作为树的定义。)
(1)无简单回路且m =n -1。这里m 是边数, n 是顶点数, 下同。
(2) 连通且m =n -1。
(3)无简单回路, 但增加任一新边, 得到且仅得到一条基本回路。
(4)连通但删去任一边, 图便不连通(n ≥2) 。
(5)每一对顶点间有唯一的一条基本路径。(n ≥2) 。
定理8.7―2任一树T 中, 至少有两片树叶(n ≥2时) 。
8.7.2 生成树
定义8.7―3给定一个无向图G , 若G 的一个生成子图T 是树, 则称T 为G 的生成树或支撑树。
图G 的生成树不是唯一的, 如图8.7―2所示, 右侧两个图都是左侧图G 的生成树。
定理8.7―3任何连通无向图至少有一棵生成树。
生成树T 中的边称为树枝, 不在生成树
T
中但属于图
G
的边
, 称为树T 的弦。弦的集合称
为树T 的补。在图8.6―2(a)中, 若生成树取为(b)图, 则e 2, e 6, e 8, e 3是树枝, e 1, e 5, e 7, e 4都是弦,{e 1, e 5, e 7, e 4}是该生成树的补。
设连通图G 有n 个顶点, m 条边, 则G 的任一生成树有n -1条树枝, m -n +1条弦。在图G 中, 给定生成树T 后, 根据定理8.6―1的第(3)条, 每加一条弦, 则得一个基本回路, 例如在图
8.6―2中, 若树的边集是{e 2, e 3, e 6, e 8},则:
加弦e 1, 得基本回路{e 1, e 2, e 6, e 8}。
加弦e 5, 得基本回路{e 5, e 2, e 6}。
加弦e 7, 得基本回路{e 7, e 6, e 3}。
加弦e 4, 得基本回路{e 4, e 8, e 6, e 3}。
因为有m -n +1条弦, 一般地可得m -n +1个基本回路, 此m -n +1个基本回路称为图G 的关于生成树T 的基本回路系统。
从树T 中删去一条枝, 将T 分为两棵树, G 的顶点集划分为两个子集, 连结这两个子集的边集就是对应于这条枝的割集, 称为对应于这条边的基本割集。
定理8.7―4 一条简单回路和任何生成树的补至少有一条共同边。
定理8.7―5 一个割集和任何生成树至少有一条共同边。
定理8.7―6 任一个简单回路和任一个割集有偶数(包括0) 条共同边。
定理 8.7―7 设D ={e 1, e 2, e 3,…,ek }是一个基本割集, 其中e 1是树枝, e 2, e 3,…, ek 是生成树的弦。则e 1包含在对应于e i(i =2,3,…,k ) 的基本回路中, 而不包含在任何其它的基本回路中。
定理8.7―8 对给定的一棵生成树, 设C ={e 1, e 2,…,ek }是一条基本回路, 其中e 1是弦, e 2,…,ek 是生成树的枝, 则e 1包含在对应于ei (i =2,…,k ) 的基本割集中, 而不包含在任何其它的基本割集中。
8.7.3 最小生成树
设图G =〈V , E,W 〉是赋权连通简单无向图, W 是E 到非负实数的函数, 边〈i , j 〉的权记为
(T W (i , j ) 。若T 是G 的生成树, T 中树枝的权之和称为T 的权, 记为 W ) = W ( i , j ) 。
(i , j ) ∈T 所有生成树中具有最小权的生成树称为最小生成树。
定理8.7―9设G 是边权全不相同的连通简单图, C 是一条简单回路, 则C 上权最大的边e 必定不在G 的最小生成树中。
在这个定理的基础上, 建立了克鲁斯克尔(Krusk al) 算法:
设G 有n 个顶点, m 条边, 先将G 中所有的边按权的大小次序进行排列, 不妨设
W (e 1) ＜W (e 2) ＜…＜W (em )
(1) k ←1, A ← ∅ 。
(2)若A ∪{ek }导出的子图中不包含简单回路, 则A ←A ∪{ek }。
(3)若
A 中已有n -1条边, 则算法终止, 否则k ←k +1,转至(2)。
图8.7―5给出了求最小生成树的例子, 要注意带权4和7的边是怎样在一步一步作图的过程中被排除掉。 ∑
8.8 有向树
8.8.1 有向树的定义和性质
定义8.8―1有向树是结点集合非空的, 并符合以下3条的有向图。
(1) 有且仅有一个结点叫树根, 它的引入次数是0。
(2) 除树根外每一结点的引入次数是1。
(3)树的每一结点a , 都有从树根到a 的一条有向路径。 有向树亦称根树, 通常采用根在顶上, 所有弧向下, 弧的箭头略去的图表示。
定义8.8―2设a 和b 是有向树T 的结点, 如果有一弧从a 到b , 那么说a 是b 的父亲, 而b 是a 的儿子。如果从结点a 到结点b 有一有向路径, 那么说a 是b 的祖先, 而b 是a 的后裔; 如果a ≠b , 那么a 是b 的一个真祖先而b 是a 的一个真后裔。由结点a 和它的所有后裔导出的子有向图叫做T 的子树, a 叫子树的根。如果a 不是T 的根, 那么子树是T 的真子树。引出数是0的结点叫树的叶; 一结点若不是叶叫做内部结点(或分枝点) 。从树根r 到一结点a 的路径长度称为a 的路径长度, 亦称a 的层次。树T 中层次的最大值叫做树T 的高度。
定理8.8―1设T 是一棵有向树, 根是r , 并设a 是T 的任一结点, 那么从r 到a 有唯一的有向路径。
推论8.8―1 有向树中的每一有向路径是基本路径。
定理8.8―2有向树没有非零长度的任何回路。
定理8.8―3 有向树成立公式m =n -1这里m 是边数, n 是结点数。
定理8.8―4 有向树的子树是有向树。
定义8.8―3有向树T 的括号表示按以下规则得出:
(1)如果T 只有一个结点, 则此结点就是它的括号表示。
(2)如果T 由根r 和子树T 1, T 2,…,Tn 组成, 则T 的括号表示是:根r , 左括号, T 1, T 2,…,Tn 的括号表示(两子树间用逗号分开),
右括号。
定义8.8―4一个有向图, 如果它的每个连通分图是有向树, 则称该有向图为(有向) 森林; 在森林中, 如果所有树都是有序树且给树指定了次序, 则称此森林是有序森林。
8.8.3 搜索树和决策树
使用二元树作数据结构时, 有时需要周游整个树, 即遍访每一结点。有3个周游算法, 依据根结点被处理的先后不同, 分别称为前序、中序、后序周游算法。设二元树的根为r , 左子树为T 1, 右子树为T 2(但T 1和T 2崐可以不存在),3个周游算法的递归定义如下:
前序:
(1)处理T 的根结点r ,
(2)如果T 1存在, 那么用前序方法处理T 1,
(3)如果T 2存在, 那么用前序方法处理T 2。
中序:
(1)如果T 1存在, 那么用中序方法处理T 1,
(2)处理T 的根结点r ,
(3)如果T 2存在, 那么用中序方法处理T 2。
后序:
(1) 如果T 1存在, 那么用后序方法处理T 1,
(2) 如果T 2存在, 那么用后序方法处理T 2,
(3)处理T 的根结点r 。
例8有8个硬币, 如果恰好有一个硬币是假的且比其它的都重, 要求我们以比较重量的方法用一架天平去找出伪币。
8.9 运输网络
定义8.9―1设G =〈V , E , W 〉是一个连通赋权有向简单图, W 是E 上的非负实函数, 若G 中恰有一个没有引入边的顶点a ,
恰有一个没有引出边的顶点z, 则称G 为运输网络。
定理8.9―1 在给定的运输网络中, 任何流的值小于或等于网络中任何割的容量。
定理8.9―2 (福特—富克逊(Ford ―Ful ke rso n ) 定理) 在任一运输网络中, 从a 到z 的最大流的值等于最小割(P , P ) 的容量。
8.8.2 标记法
1. 标记过程
通常设初始流为0, 标记形式是(+x , Δy ), 表示从顶点x 流到顶点y 的流量可增加Δy , 或(-x , Δy ), 表示从顶点y 流到顶点x 的流量可减少Δy 。
第一步:给源点a 以标记(-,∞) 。表示结点a 流到其它结点的量可以任意。
第二步:选择一个已标记的顶点x , 对于x 的所有未标记的邻接顶点y 按下列规则处理。 (a ) 如果Φ(y , x ) ＞0, 令Δy =min［Φ(y , x ), Δx ］, 给顶点y 以标记(-x , Δy ) 。(即后向边有回流情况。)
(b ) 如果Φ(x , y ) ＜W (x , y ), 令Δy =min［W (x , y )-Φ(x , y ), Δx ］, 给顶点y 以标记(+x , Δy ) 。即前向边未饱和情况。)
(c)除上述两种情况外, 不标记。
第三步:重复第二步直至阱点被标记, 或不再有顶点可以标记为止。如果z 点给了标记, 说明存在一条可增值道路, 转向增值过程。如果z 点不能标记, 而且不存在其它可标记的顶点时算法结束。所得的流便是最大流。
2. 增值过程
第一步:取出z 的标记(+v , Δz ), 令δ=Δz , u =z 。
第二步:若u 的标记为(+v , Δu ), 则
Φ(v , u ) ←Φ(v , u )+δ
若u 的标记为(-v , Δu ), 则
Φ(u , v ) ←Φ(u , v )-δ
第三步:若v =a , 则把全部标记去掉转回标记过程。如v ≠a , 令u =v , 返回第二步。
现实中的运输网络可能有多个源点a 1, a 2,…,an , 和多个阱点z 1, z 2,…,zm , 如图8.8―6(a ) 所示。对于这种情况, 只需添上一个虚设的源点a 和阱点z , 添上容量为∞的a a 1, a 2,…,an
的有
向边和z 1, z 2,…,zm 到z 的有向边, 如图8.8―6(b ) 所示, 即可把问题转化为本节介绍的形式求解, 方法完全一样, 不再举例了。
运输网络的用途不限于解决运输问题。例如求一个二部图G =〈X , E , Y 〉的最大匹配问题, 可转化为运输网络求解。方法是把X 的元素都看作源点, Y 的元素都看
作阱点, 边的方向都是从源点指向阱点, 再用上述方法, 虚设一个源点a 和一个阱点z , 并设所有边的权均为1。对所得的图求得最大流的值就是最大匹配的边数, 最大流通过的属于E 的边集, 就是最大匹配。
总 结
第八章 图论
8.1 图的基本概念
8.1.1 图
定义8.1―1 一个图G 是一个三重组〈V (G ), E (G ), ΦG 〉, 其中V (G ) 是一个非空的结点(或叫顶点) 集合, E (G ) 是边的集合, ΦG 是从边集E 到结点偶对集合上的函数。一个图可以用一个图形表示。 定义中的结点偶对可以是有序的, 也可以是无序的。若边e 所对应的偶对〈a , b 〉是有序的, 则称e 是有向边。有向边简称弧, a 叫弧e 的始点, b 叫弧e 的终点, 统称为e 的端点。称e 是关联于结点a 和b 的, 结点a 和结点b 是邻接的。若边e 所对应的偶对(a , b ) 是无序的, 则称e 是无向边。无向边简称棱, 除无始点和终点的术语外, 其它术语与有向边相同 每一条边都是有向边的图称为有向图。每一条边都是无向边的图称为无向图。 有向图和无向图也可互相转化。例如, 把无向图中每一条边都看作两条方向不同的有向边, 这时无向图就成为有向图。又如, 把有向图中每条有向边都看作无向边, 就得到无向图。这个无向图习惯上叫做该有向图的底图。
在图中, 不与任何结点邻接的结点称为弧立结点。全由孤立结点构成的图称为零图。关联于同一结点的一条边称为自回路。
在有向图中, 两结点间(包括结点自身间) 若同始点和同终点的边多于一条, 则这几条边称为平行边。在无向图中, 两结点间(包括结点自身间) 若多于一条边, 则称这几条边为平行边。两结点a 、b 间互相平行的边的条数称为边［a , b ］的重数。仅有一条时重数为1, 无边时重数为0。
定义8.1―2 含有平行边的图称为多重图。非多重图称为线图。无自回路的线图称为简单图。仅有一个结点的简单图称为平凡图。
定义 8.1―3 赋权图G 是一个三重组〈V , E , g 〉或四重组〈V , E , f , g 〉, 其中V 是结点集合, E 是边的集合, f 是定义在V 上的函数, g 是定义在E 上的函数。
8.1.2 结点的次数
定义 8.1―4 在有向图中, 对于任何结点v , 以v 为始点的边的条数称为结点v 的引出次数(或出度) , 记为deg +(v ); 以v 为终点的边的条数称为结点v 的引入次数(或入度) , 记为deg -(v ); 结点v 的引出次数和引入次数之和称为结点v 的次数(或度数) , 记作deg (v ) 。在无向图中, 结点v 的次数是与结点v 相关联的边的条数, 也记为deg (v ) 。孤立结点的次数为零。 定理8.1―1 设G 是一个(n , m ) 图, 它的结点集合为V ={v 1, v 2,…,v n},则
n deg(υi ) =2m i =1定理8.1―2 在图中, 次数为奇数的结点必为偶数个。
定义8.1―5 各结点的次数均相同的图称为正则图, 各结点的次数均为k 时称为k ―正则图。 ∑
8.1.3 图的同构
定义8.1.6 设G =〈V , E 〉和G ′=〈V ′, E ′〉是两个图, 若存在从V 到V ′的双射函数
Φ, 使对任意a 、b ∈V , ［a , b ∈E 当且仅当［Φ(a ), Φ(b ) ］∈E ′, 并且［a , b ］和［Φ(a ), Φ(b ) ］有相同的重数, 则称G 和G ′是同构的。 8.1.4 图的运算
定义8.1―7 设图G 1=〈V 1, E 1〉和图G 2=〈V 2, E 2〉。
(1)G 1与G 2的并, 定义为图G 3＝〈V 3, E 3〉, 其中V 3=V 1∪V 2, E 3=E 1∪E 2, 记为G 3=G 1∪G 2。
(2)G 1与G 2的交, 定义为图G 3＝〈V 3, E 3〉, 其中V 3=V 1∩V 2, E 3=E 1∩E 2, 记为G 3=G 1∩G 2。
(3)G 1与G 2的差, 定义为图G 3＝〈V 3, E 3〉, 其中E 3=E 1-E 2, V 3=(V 1-V 2) ∪{E 3中边所关联的顶点},记为G 3=G 1-G 2。
(4)G 1与G 2的环和, 定义为图G 3＝〈V 3, E 3〉, G 3=(G 1∪G 2)-(G 1∩G 2), 记为G 3=G 1 G 2。
除以上4种运算外, 还有以下两种操作:
(1) 删去图G 的一条边e ;
(2) 删去图G 的一个结点v 。它的实际意义是删去结点v 和与v 关联的所有边。
8.1.5 子图与补图
定义8.1―8 设G =〈V , E 〉和G ′=〈V ′, E ′〉是两个图。 (1) 如果V ′⊆V 和E ′⊆E , 则称G ′是G 的子图。如果V ′⊆V 和E ′⊆E , 则称G ′≠G 的真子图。(注意:“G ′是图”已隐含着“E ′中的边仅关联V ′中的结点”的意义。)
(2) 如果V ′=V 和E ′⊆E , 则称G ′为G 的生成子图。
(3) 若子图G ′中没有孤立结点, G ′由E ′唯一确定, 则称G ′为由边集E ′导出的子图。
(4)若在子图G ′中, 对V ′中的任意二结点u 、v , 当［u , v ］∈E 时有［u , v ］∈E ′, 则G ′由V ′唯一确定, 此时称G ′为由结点集V ′导出的子图。
定义8.1―9在n 个结点的有向图G =〈V , E 〉中, 如果E =V ×V , 则称G 为有向完全图; 在n 个结点的无向图G =〈V , E 〉中, 如果任何两个不同结点间都恰有一条边, 则称G 为无向完全图, 记为Kn 。
定义8.1―10 设线图G =〈V , E 〉有n 个顶点, 线图H =〈V , E ′〉也有同样的顶点, 而E ′是由n 个顶点的完全图的边删去E 所得, 则图H 称为图G 的补图, 记为 H = G 显然, G = G 。
8.2 路径和回路
8.2.1 基本概念
定义8.2―1在有向图中, 从顶点v 0到顶点vn 的一条路径是图的一个点边交替序列（v 0e 1v 1e 2v 2…envn ）, 其中vi -1和vi 分别是边ei 的始点和终点, i =1,2,…,n 。在序列中, 如果同一条边不出现两次, 则称此路径是简单路径, 如果同一顶点不出现两次, 则称此路径是基本路径(或叫链) 。如果路径的始点v 0和终点vn 相重合, 即v 0=vn , 则此路径称为回路, 没有相同边的回路称为简单回路, 通过各顶点不超过一次的回路称为基本回路。
定义8.2―2 路径P 中所含边的条数称为路径P 的长度。长度为0的路径定义为单独一个顶点。(但注意习惯上不定义长度为0的回路。)
定理8.2―1 在一个具有n 个结点的简单图G =〈V , E 〉中, 如果从v 1到v 2有一条路径, 则从v 1到v 2有一条长度不大于n -1的基本路径。
定理8.2―2 在一个具有n 个结点的简单图G =〈V , E 〉中, 如果经v 1有一条简单回路, 则经v 1有一条长度不超过n 的基本回路。
定义8.2―3 在图G =〈V , E 〉中, 从结点vi 到v j 最短路径的长度叫从vi 到v j 的距离, 记为
d (vi , v j) 。若从vi 到v j 不存在路径, 则d (vi , v j)=∞。
注意, 在有向图中, d (vi , v j) 不一定等于d (v j, vi ), 但一般地满足以下性质:
(1) d (vi , v j) ≥0;
(2) d (vi , vi )=0;
(3) d (vi , v j)+d (v j, v k) ≥d (vi , v k) 。
8.2.2 图的连通度
定义8.2―4设G =〈V , E 〉是图, 且vi 、v j ∈V 。如果从vi 到v j 存在一条路径, 则称v j 从vi 可达。vi 自身认为从vi 可达。
定义8.2―5在无向图G 中, 如果任两结点可达, 则称图G 是连通的; 如果G 的子图G ′是连通的, 没有包含G ′的更大的子图G ″是连通的, 则称G ′是G 的连通分图(简称分图) 。
一个无向图或者是一个连通图, 如图8.2―2(a ) 所示, 或者是由若干个连通分图组成, 如图
8.2―2(b ) 所示。
图 8.2―2
定理8.2―3 设G 是任一(n , m ) 无向简单图, ω是其分图个数, 则
1 n -ω≤m ≤(n -ω)(n -ω+1) 2
定义8.2―11在有向图中, 如果在任两结点偶对中, 至少从一个结点到另一个结点是可达的, 则称图G 是单向连通的; 如果在任两结点偶对中, 两结点都互相可达, 则称图G 是强连通的; 如果它的底图是强连通的, 则称图G 是弱连通的。
显然, 强连通的也一定是单向连通和弱连通的, 单向连通的一定是弱连通的, 但其逆均不真。在图8.2―3中,(a ) 是强连通的,(b ) 是单向连通的,(c ) 是弱连通的。
图 8.2―3
定义8.2―12 在有向图G =〈V , E 〉中, G ′是G 的子图, 若G ′是强连通的(单向连通的, 弱连通的), 没有包含G ′的更大子图G ″是强连通的(单向连通的, 弱连通的), 则称G ′是G 的强分图(单向分图, 弱分图) 。
在图8.2―4中, 强分图集合是:
{〈{1,2,3},{e 1, e 2, e 3}〉, 〈{4},φ〉, 〈{5},φ〉, 〈｛6｝, φ〉, 〈｛7,8｝,{e 7, e 8}〉｝
单向分图集合是:
{〈{1,2,3,4,5},{e 1, e 2, e 3, e
4,
e 5}〉, 〈{6,5},{e 6}〉, 〈｛7,8｝,{e 7, e 8}〉｝
弱分图集合是:
{〈{1,2,3,4,5,6},{e 1, e 2, e 3, e 4, e 5, e 6}〉, 〈｛7,8｝,{e 7, e 8}〉｝
图 8.2―4
8.2.3 赋权图中的最短路径
设G =〈V , E , W 〉是个赋权图, W 是从E 到正实数集合的函数, 边［i , j ］的权记为W (i , j ), 称为边的长度。若i 和j 之间没有边, 那么W (i , j )=∞。路径P 的长度定义为路径中边的长度之和, 记为W (P ) 。图G 中从结点u 到结点v 的距离记为d (u , v ), 定义为
min{W (P )|P 为G 中从u 到v 的路径}
∞ 当从u 到v 不可达时
本小节主要讨论在一个赋权的简单连通无向图
G =〈V , E ,W 〉中, 求一结点a (称为源点) 到其它结点x 的最短路径的长度, 通常称它为单源问题。下面介绍1959
年迪克斯特拉(E .W.Dijkstra) 提出的单源问题的算法, 其要点如下:
(1) 把V 分成两个子集S 和T 。初始时,S={a },T =V -S 。
(2) 对T 中每一元素t 计算D (t ), 根据D (t ) 值找出T 中距a 最短的一结点x, 写出a 到x 的最短路径的长度D (x ) 。
(3)置S 为S ∪{x },置T 为T -{x },若T = , 则停止, 否则再重复2。
8.2.4 欧拉路径和欧拉回路
哥尼斯堡(Konig s berg , 现加里宁格勒) 位于普雷格尔(Prege l) 河畔, 河中有两岛。城市的各部分由7座桥接通, 如图8.2―8(a ) 所示。古时城中居民热衷于一个问题:游人从任一地点出发, 怎样才能做到穿过每座桥一次且仅一次后又返回原出发地。1736年欧拉用图论方法解决了此问题, 写了第一篇图论的论文, 从而成为图论的创始人。
不难看出, 如果用结点代表陆地, 用边代表桥, 哥尼斯堡七桥问题就等价在于图8.2―8(b ) 中找到这样一条路径, 它穿程每条边一次且仅一次。
穿程于图G 的每条边一次且仅一次的路径, 称为欧拉路径。穿程于图G 的每条边一次且仅一次的回路, 称为欧拉回路, 具有欧拉回路的图称为欧拉图。
显然, 具有欧拉路径的图除孤立结点外是连通的, 而孤立结点不影响欧拉路径的讨论。因此, 下边讨论欧拉路径有关问题时均假定图是连通的。
图 8.2―8
定理8.2―10无向连通图G 具有一条欧拉路径当且仅当G 具有零个或两个奇数次数的顶点。
定理8.2―11一个有向连通图具有欧拉回路, 当且仅当它的每个顶点的引入次数等于引出次数。一个有向连通图具有欧拉路径, 当且仅当它的每个顶点的引入次数等于引出次数, 可能有两个顶点是例外, 其中一个顶点的引入次数比它的引出次数大1, 另一个顶点的引入次数比它的引出次数小1。
8.2.5 哈密尔顿路径与哈密尔顿回路
在无向图G =〈V , E 〉中, 穿程于G 的每个结点一次且仅一次的路径称为哈密尔顿路径。穿程于G 的每个结点一次且仅一次的回路称为哈密尔顿回路。具有哈密尔顿回路的图称为哈密尔顿图。
哈密尔顿, 爱尔兰数学家,1859年他首先提出这一类问题。它的问题如下:
如何沿12面体的棱线, 通过每个角一次且仅一次?(称为环游全世界游戏。)
定理8.2―12 若G =〈V , E 〉是哈密尔顿图, 则对V 的每个非空真子集S 均成立:
ω(G -S ) ≤｜S ｜
这里|S |表示S 中的顶点数, ω(G -S ) 表示G 删去顶点集S 后得到的图的连通分图个数。 应用本定理可以判定某些图不是哈密尔顿图, 例如, 图8.2―12所示的图, 删去其中3个黑点, 即知此图不符合必要条件, 因而不是哈密尔顿图。但一般要考察多个真子集, 应用不方便, 例4给出了一种较简便的否定一个图是哈密尔顿图的方法, 但也不是通用的。
例4 证明图8.2―13(a ) 中的图没有哈密尔顿路径。
证用A 标记顶点a , 所有与A 邻接的顶点标记为B 。继续不断地用A 标记所有邻接于B 的顶点, 用B 标记所有邻接于A 的顶点, 直到所有顶点标记完, 得到如图8.2―13(b ) 所示的图, 图中有3个顶点标A 和5个顶点标B , 标号A 和B 崐相差2个, 因此不可能存在一条哈密尔顿路径。
图 8.2―13
定理8.2―6中的条件不是充分的, 图8.1―5中给出的彼得森图, 它对任意SV 都满足ω(G -S ) ≤|S |,但不是哈密尔顿图。
定理8.2―13设G =〈V , E 〉是具有n 个顶点的简单无向图, 若在G 中每一对顶点的次数之和大于等于n , 则在G 中存在一条哈密尔顿回路。 1≥推论8.2―13在简单无向图中, 若每一顶点的度数 n (n ≥ 3) , 则该图是哈密尔顿图。 2在有向图中, 也可类似地定义出哈密尔顿有向回路和哈密尔顿有向路径。
8. ３ 图的矩阵表示
定义8.3―1设G =〈V , E 〉是有向线图, 其中V ={v 1, v 2,…,vn },并假定各结点已经有了从v 1到vn 的次序。定义一个n ×n 的矩阵A , 其中各元素a ij 为
:
⎧1a ij v i ,
v j ∈E j ∉E
零图的邻接矩阵的元素全为零, 称为零矩阵。每一顶点都有自回路而无其它边的图的邻接矩阵是单位矩阵。设有向线图G =〈V , E 〉的邻接矩阵是A , 则G 的逆图的邻接矩阵是A 的转置矩阵, 记A 。
定义8.3―2设G =〈V , E 〉是有向线图, 其中｜V ｜=n , 并假定各结点是有序的, 定义一个n ×n 的矩阵P , 它的元素
⎧1 , 当vi 到vj 至少存在一条非零长度的路径0 P ij =⎨ ⎩ 0 , 当vi 到vj 不存在一条非零长度的路径
称矩阵P 为图G 的可达性矩阵。 T
8.5 二部图
定义8.5―1若无向图G =〈V , E 〉的顶点集合V 可以划分成两个子集X 和Y , 使G 中的每一条边e 的一个端点在X 中, 另一个端点在Y 中, 则称G 为二部图或偶图。二部图可记为G =〈X, E,Y 〉,X 和Y 称为互补结点子集。 定义8.5―2二部图G =〈X, E , Y 〉中, 若X 的每一顶点都与
Y 的每一顶点邻接, 则称G 为完全二部图, 记为Km , n , 这里m =｜X ｜, n =｜Y ｜。
图8.5―1给出K 2,4和K 3,3的图示。
图8.5―1
定理8.5―1无向图G =〈V , E 〉为二部图的充分必要条件为G 中所有回路的长度均为偶数。
定义8.5―3给定一个二部图G =〈X, E , Y 〉, 如果E 的子集M 中的边无公共端点, 则称M 为二部图G 的一个匹配。含有最多边数的匹配称为G 的最大匹配。如果二部图G 中的一条链由不属于匹配M 的边和属于M 的边交替组成, 且链的两端点不是M 中边的端点, 那么称此链为G 中关于匹配M 的交替链。
例如, 图8.5―2中的(x 2, y 1, x 3, y 4) 是交替链。最短的交替链是由一条边组成, 该边的两端点不是M 中边的端点。
交替链可用标记法找出, 标记法的过程如下:
首先把X 中所有不是M 的边的端点用()加以标记, 然后交替进行以下所述的过程Ⅰ和Ⅱ。 Ⅰ. 选一个X 的新标记过的结点, 比如说xi , 用(xi ) 标记不通过在M 中的边与xi 邻接且未标记过的Y 的所有结点。对所有X 的新标记过的结点重复这一过程。
Ⅱ. 选一个Y 的新标记过的结点, 比如说y i , 用(yi ) 标记通过M 的边与y i 邻接且未标记过的X 的所有结点。对所有Y 的新标记过结点重复这一过程。
8.6 平面图和图的着色
8.6.1 平面图
定义8.6―1一个无向图G =〈V , E 〉, 如果能把它图示在一平面上, 边与边只在顶点处相交
的图叫
平面图。
图8.6―1所示的是非平面图, 而图8.6―2所示的都是平面图的例子。
8.6.2 欧拉公式
欧拉1750年提出任何一个凸多面体的顶点数n , 棱数m 和面数k 满足公式:
n -m +k =2
参看图8.6―3
为了介绍平面图的欧拉公式, 我们首先介绍什么是平面图的面。我们在平面上画一个平面图, 用小刀沿着边切下, 则这平面将分割成几块, 这种块就称为图的面, 即一个平面图的面定义为平面的一块, 它用边作界线, 并且不再分为子块。例如图8.5―4(a ) 有3个图, 如图8.5―4(b ) 所示。注意沿边a 切, 不再分割面1, 沿边b 和c 切, 也不再分割面3。如果面的面积是有限的, 称该面为有限面, 否则, 称为无限面。显然, 平面图恰有一个无限面。
定理8.6―1 对任何连通平面图恒有
n -m +k =2
即 顶点数-边数+面数=2
定理8.6―2在n ≥3的任何连通平面简单(n , m ) 图中有m ≤3n -6成立。
推论8.6―2 K 5是非平面图。
推论8.6―3 K 3,3不是平面图。
8.6.3 库拉托夫斯基(Kurat ows ki ) 定理
定义8.6―2 K 5和K 3,3称为库拉托夫斯基图。
定义8.6―3两个图G 1和G 2称为在2度顶点内同构的(或称同胚) , 如果它们是同构的, 或者通过反复插入和(或) 除去2度顶点, 它们能变换成同构的图。.
如图8.6―8(a ) 和(b ) 所示。图8.5―8(c ) 中的两个图是在2度顶点内同构的。
定理8.6―4(库拉托夫斯基定理) 一个图是平面图, 当且仅当它不包含任何在2度顶点内和库拉托夫斯基图同构的子图。
8.5.4 对偶图
将平面图G 嵌入平面后, 通过以下手续(简称D 过程):
(1) 对图G 的每个面Di 的内部作一顶点且仅作一顶点v*i;
(2)经过每两个面Di 和Dj 的每一共同边界e*k作一条边e*k=(v *i , vj ) 与ek 相交;
(3)当且仅当ek 只是面Di 的边界时, v *i 恰存在一自回路与ek 相交。
所得的图称为图G 的对偶图, 记为G 。
图8.6―9中, 虚线构成的图是实线构成的图的对偶图。
8.6.6 五色问题
1852年英国一个青年名叫盖思里(Gut h rie ) 提出地图四色问题。在画地图时, 如果规定一条边界分开的两个区域涂不同颜色, 那么任何地图能够只用4种颜色涂色。这个问题成为数学难题, 一百多年来, 许多人的证明都失败了。直至1976年6月美国伊利诺斯大学两位教授阿佩尔(Appe l) 和海肯(Haken ) 利用电子计算机, 计算了1200小时, 证明了四色问题。这件事曾轰动一时。但是用“通常”证明方法来解决四色问题, 至今仍未解决。
引理 在平面连通的简单图中至少有一个顶点v 0, 其次数d (v 0) ≤5。
定理 8.6―7
用
5
种颜色可以给任一平面简单连通图G =〈V , E 〉正常着色。
8.7 树
8.7.1 无向树
定义8.7―1连通而无简单回路的无向图称为无向树, 简称树。树中次数为1的顶点称为树叶。次数大于1的顶点称为分枝点或内部结点。
定义8.7―2一个无向图的诸连通分图均是树时, 称该无向图为森林, 树是森林。 例如图8.7―1(a)、(b)所示的都是树,(c)所示的是森林。
定理8.7―1无向图T 是树, 当且仅当下列5条之一成立。(或者说, 这5条的任一条都可作为树的定义。)
(1)无简单回路且m =n -1。这里m 是边数, n 是顶点数, 下同。
(2) 连通且m =n -1。
(3)无简单回路, 但增加任一新边, 得到且仅得到一条基本回路。
(4)连通但删去任一边, 图便不连通(n ≥2) 。
(5)每一对顶点间有唯一的一条基本路径。(n ≥2) 。
定理8.7―2任一树T 中, 至少有两片树叶(n ≥2时) 。
8.7.2 生成树
定义8.7―3给定一个无向图G , 若G 的一个生成子图T 是树, 则称T 为G 的生成树或支撑树。
图G 的生成树不是唯一的, 如图8.7―2所示, 右侧两个图都是左侧图G 的生成树。
定理8.7―3任何连通无向图至少有一棵生成树。
生成树T 中的边称为树枝, 不在生成树
T
中但属于图
G
的边
, 称为树T 的弦。弦的集合称
为树T 的补。在图8.6―2(a)中, 若生成树取为(b)图, 则e 2, e 6, e 8, e 3是树枝, e 1, e 5, e 7, e 4都是弦,{e 1, e 5, e 7, e 4}是该生成树的补。
设连通图G 有n 个顶点, m 条边, 则G 的任一生成树有n -1条树枝, m -n +1条弦。在图G 中, 给定生成树T 后, 根据定理8.6―1的第(3)条, 每加一条弦, 则得一个基本回路, 例如在图
8.6―2中, 若树的边集是{e 2, e 3, e 6, e 8},则:
加弦e 1, 得基本回路{e 1, e 2, e 6, e 8}。
加弦e 5, 得基本回路{e 5, e 2, e 6}。
加弦e 7, 得基本回路{e 7, e 6, e 3}。
加弦e 4, 得基本回路{e 4, e 8, e 6, e 3}。
因为有m -n +1条弦, 一般地可得m -n +1个基本回路, 此m -n +1个基本回路称为图G 的关于生成树T 的基本回路系统。
从树T 中删去一条枝, 将T 分为两棵树, G 的顶点集划分为两个子集, 连结这两个子集的边集就是对应于这条枝的割集, 称为对应于这条边的基本割集。
定理8.7―4 一条简单回路和任何生成树的补至少有一条共同边。
定理8.7―5 一个割集和任何生成树至少有一条共同边。
定理8.7―6 任一个简单回路和任一个割集有偶数(包括0) 条共同边。
定理 8.7―7 设D ={e 1, e 2, e 3,…,ek }是一个基本割集, 其中e 1是树枝, e 2, e 3,…, ek 是生成树的弦。则e 1包含在对应于e i(i =2,3,…,k ) 的基本回路中, 而不包含在任何其它的基本回路中。
定理8.7―8 对给定的一棵生成树, 设C ={e 1, e 2,…,ek }是一条基本回路, 其中e 1是弦, e 2,…,ek 是生成树的枝, 则e 1包含在对应于ei (i =2,…,k ) 的基本割集中, 而不包含在任何其它的基本割集中。
8.7.3 最小生成树
设图G =〈V , E,W 〉是赋权连通简单无向图, W 是E 到非负实数的函数, 边〈i , j 〉的权记为
(T W (i , j ) 。若T 是G 的生成树, T 中树枝的权之和称为T 的权, 记为 W ) = W ( i , j ) 。
(i , j ) ∈T 所有生成树中具有最小权的生成树称为最小生成树。
定理8.7―9设G 是边权全不相同的连通简单图, C 是一条简单回路, 则C 上权最大的边e 必定不在G 的最小生成树中。
在这个定理的基础上, 建立了克鲁斯克尔(Krusk al) 算法:
设G 有n 个顶点, m 条边, 先将G 中所有的边按权的大小次序进行排列, 不妨设
W (e 1) ＜W (e 2) ＜…＜W (em )
(1) k ←1, A ← ∅ 。
(2)若A ∪{ek }导出的子图中不包含简单回路, 则A ←A ∪{ek }。
(3)若
A 中已有n -1条边, 则算法终止, 否则k ←k +1,转至(2)。
图8.7―5给出了求最小生成树的例子, 要注意带权4和7的边是怎样在一步一步作图的过程中被排除掉。 ∑
8.8 有向树
8.8.1 有向树的定义和性质
定义8.8―1有向树是结点集合非空的, 并符合以下3条的有向图。
(1) 有且仅有一个结点叫树根, 它的引入次数是0。
(2) 除树根外每一结点的引入次数是1。
(3)树的每一结点a , 都有从树根到a 的一条有向路径。 有向树亦称根树, 通常采用根在顶上, 所有弧向下, 弧的箭头略去的图表示。
定义8.8―2设a 和b 是有向树T 的结点, 如果有一弧从a 到b , 那么说a 是b 的父亲, 而b 是a 的儿子。如果从结点a 到结点b 有一有向路径, 那么说a 是b 的祖先, 而b 是a 的后裔; 如果a ≠b , 那么a 是b 的一个真祖先而b 是a 的一个真后裔。由结点a 和它的所有后裔导出的子有向图叫做T 的子树, a 叫子树的根。如果a 不是T 的根, 那么子树是T 的真子树。引出数是0的结点叫树的叶; 一结点若不是叶叫做内部结点(或分枝点) 。从树根r 到一结点a 的路径长度称为a 的路径长度, 亦称a 的层次。树T 中层次的最大值叫做树T 的高度。
定理8.8―1设T 是一棵有向树, 根是r , 并设a 是T 的任一结点, 那么从r 到a 有唯一的有向路径。
推论8.8―1 有向树中的每一有向路径是基本路径。
定理8.8―2有向树没有非零长度的任何回路。
定理8.8―3 有向树成立公式m =n -1这里m 是边数, n 是结点数。
定理8.8―4 有向树的子树是有向树。
定义8.8―3有向树T 的括号表示按以下规则得出:
(1)如果T 只有一个结点, 则此结点就是它的括号表示。
(2)如果T 由根r 和子树T 1, T 2,…,Tn 组成, 则T 的括号表示是:根r , 左括号, T 1, T 2,…,Tn 的括号表示(两子树间用逗号分开),
右括号。
定义8.8―4一个有向图, 如果它的每个连通分图是有向树, 则称该有向图为(有向) 森林; 在森林中, 如果所有树都是有序树且给树指定了次序, 则称此森林是有序森林。
8.8.3 搜索树和决策树
使用二元树作数据结构时, 有时需要周游整个树, 即遍访每一结点。有3个周游算法, 依据根结点被处理的先后不同, 分别称为前序、中序、后序周游算法。设二元树的根为r , 左子树为T 1, 右子树为T 2(但T 1和T 2崐可以不存在),3个周游算法的递归定义如下:
前序:
(1)处理T 的根结点r ,
(2)如果T 1存在, 那么用前序方法处理T 1,
(3)如果T 2存在, 那么用前序方法处理T 2。
中序:
(1)如果T 1存在, 那么用中序方法处理T 1,
(2)处理T 的根结点r ,
(3)如果T 2存在, 那么用中序方法处理T 2。
后序:
(1) 如果T 1存在, 那么用后序方法处理T 1,
(2) 如果T 2存在, 那么用后序方法处理T 2,
(3)处理T 的根结点r 。
例8有8个硬币, 如果恰好有一个硬币是假的且比其它的都重, 要求我们以比较重量的方法用一架天平去找出伪币。
8.9 运输网络
定义8.9―1设G =〈V , E , W 〉是一个连通赋权有向简单图, W 是E 上的非负实函数, 若G 中恰有一个没有引入边的顶点a ,
恰有一个没有引出边的顶点z, 则称G 为运输网络。
定理8.9―1 在给定的运输网络中, 任何流的值小于或等于网络中任何割的容量。
定理8.9―2 (福特—富克逊(Ford ―Ful ke rso n ) 定理) 在任一运输网络中, 从a 到z 的最大流的值等于最小割(P , P ) 的容量。
8.8.2 标记法
1. 标记过程
通常设初始流为0, 标记形式是(+x , Δy ), 表示从顶点x 流到顶点y 的流量可增加Δy , 或(-x , Δy ), 表示从顶点y 流到顶点x 的流量可减少Δy 。
第一步:给源点a 以标记(-,∞) 。表示结点a 流到其它结点的量可以任意。
第二步:选择一个已标记的顶点x , 对于x 的所有未标记的邻接顶点y 按下列规则处理。 (a ) 如果Φ(y , x ) ＞0, 令Δy =min［Φ(y , x ), Δx ］, 给顶点y 以标记(-x , Δy ) 。(即后向边有回流情况。)
(b ) 如果Φ(x , y ) ＜W (x , y ), 令Δy =min［W (x , y )-Φ(x , y ), Δx ］, 给顶点y 以标记(+x , Δy ) 。即前向边未饱和情况。)
(c)除上述两种情况外, 不标记。
第三步:重复第二步直至阱点被标记, 或不再有顶点可以标记为止。如果z 点给了标记, 说明存在一条可增值道路, 转向增值过程。如果z 点不能标记, 而且不存在其它可标记的顶点时算法结束。所得的流便是最大流。
2. 增值过程
第一步:取出z 的标记(+v , Δz ), 令δ=Δz , u =z 。
第二步:若u 的标记为(+v , Δu ), 则
Φ(v , u ) ←Φ(v , u )+δ
若u 的标记为(-v , Δu ), 则
Φ(u , v ) ←Φ(u , v )-δ
第三步:若v =a , 则把全部标记去掉转回标记过程。如v ≠a , 令u =v , 返回第二步。
现实中的运输网络可能有多个源点a 1, a 2,…,an , 和多个阱点z 1, z 2,…,zm , 如图8.8―6(a ) 所示。对于这种情况, 只需添上一个虚设的源点a 和阱点z , 添上容量为∞的a a 1, a 2,…,an
的有
向边和z 1, z 2,…,zm 到z 的有向边, 如图8.8―6(b ) 所示, 即可把问题转化为本节介绍的形式求解, 方法完全一样, 不再举例了。
运输网络的用途不限于解决运输问题。例如求一个二部图G =〈X , E , Y 〉的最大匹配问题, 可转化为运输网络求解。方法是把X 的元素都看作源点, Y 的元素都看
作阱点, 边的方向都是从源点指向阱点, 再用上述方法, 虚设一个源点a 和一个阱点z , 并设所有边的权均为1。对所得的图求得最大流的值就是最大匹配的边数, 最大流通过的属于E 的边集, 就是最大匹配。