图论 一般性参考： 《离散数学》，左孝凌等，上海科学技术出版社

Presentation on theme: "图论 一般性参考： 《离散数学》，左孝凌等，上海科学技术出版社"— Presentation transcript:

1 图论 侯越先，yxhou@tju.edu.cn，25楼B-1223室 一般性参考： 《离散数学》，左孝凌等，上海科学技术出版社
《现代图论》英文版，Bollobas等，科学出版社 《算法导论》英文版，Cormen等，高教出版社 本ppt下载： acm.tju.edu.cn/lab/people/hyx.html

2 1.图的基本概念 引入：实体和实体之间的关系是现实世界的两个基本要素。图论（Graph Theory，GT）有效地刻画了实体与实体之间的关系，是研究现实世界的有力数学工具，在算法理论、人工智能、软件理论和软件工程、计算机网络等计算机科学的不同分支中均有重要应用。 例子：聚会握手问题 例子：柯尼斯堡7桥问题

3 1 图的基本概念 定义1：一个图G是一个序偶<V(G)，E(G)>，其中V(G)是一个非空的结点（vertex）集合，E(G)是边（edge）集合，且E(G)V×V。通常，可以将图G简记为<V，E>。 例：<{a，b，c，d } ，{<a，b><b，c><c，d><d，a>}> 注: 1.若边ei与结点的序偶<vj,vk>相关联，称该边为有向边。 2.若边ei与结点的无序偶 (vj,vk) 相关联，称该边为无向边；若无需区别边的方向，可以用(vj,vk)指代有向边或者无向边。 3. 邻接点：由一条边关联的两个结点。 4. 孤立结点：不与任何结点相邻接的点。 5. 零图：仅由孤立结点组成的图。 6. 平凡图：仅由一个孤立结点组成的图。 7. 邻接边：关联于同一结点的两条边。

4 1 图的基本概念 8. 环（loop）：关联于同一结点的边，也称为自回路
9. 有向图、无向图和混合图：本课程只涉及有向图和无向图 定义2：设G=<V,E>是一个图，则|V|称为G的阶数（order），|E|称为G的规模（size）。 定义3：在图G= <V,E>中，与结点v (v ∈ V)关联的边数，称为该结点的度数（degree），记作deg(v)。

5 1.图的基本概念 注：1 每个环在其对应的结点上增加两度。 2 记△(G)=max{deg(v)|v∈V｝
δ(G)=min{deg(v)|v∈V｝ △(G)和δ(G)分别称为图G的最大度和最小度 定理1：每个图中，结点度数的总和等于边数的两倍。 定理2：在任何图中，度数为奇数的结点必定是偶数个。 定义4：在有向图中，射入一个结点的边数称为该结点的入度，由一个结点射出的边数称为该结点的出度。结点的出度与入度的和就是该结点的度数。

6 1.图的基本概念 定理3：在任何有向图中，所有结点的入度之和等于出度之和。
定义5：连接同一对结点的边称为平行边（parallel edge），含有平行边的图称为多重图（multigraph）；不含有平行边和自回路的图称为简单图(simple graph)。 定义6：简单图G＝<V,E>中，若每一对结点间都有边相连，称该图为完全图（complete graph）。通常将有n个结点的无向完全图记作Kn。 例子 定理4：Kn的边数为n(n-1) /2

7 1.图的基本概念 定义7：设图G＝<V,E>，如果图G’＝<V’,E’>满足E’  E，V’  V，则G’称为G的子图（subgraph） 若G’包含了E中所有连接了V’中任意两个点的边，则G’称为V’的导出子图（induced subgraph） 若V’=V，则称G’为G的一个生成子图（spanning subgraph） 例子

8 1.图的基本概念 定义10：给定一个图G，由G中所有结点和所有能使G成为完全图的添加边组成的图，称为G相对于完全图的补图，简称G的补图，记作
定义11：设G’=<V’,E’>是G=<V,E>的子图，若给定另外一个图G”=<V”,E”>使得E”=E-E’，且V”中仅包含E”的边所关联的结点。则称G”是子图G’的相对于G的补图。 注：相对于完全图的补关系是对称的；相对于任意图G的补关系则不是对称的。 例子

9 1. 图的基本概念 定义12：设图G=<V,E> 及图G’=<V’,E’>，如果存在双射f：V→V’ ，使得e=(vi ,vj ) 是G的一条边，当且仅当e’ = (f(vi), f(vj)) 是G’的一条边，则称G与G’同构，记作G G’。 例子 图同构的必要条件：结点数相同；边数相同；度数相同的结点数目相同。 问题：可否用代数系统之间的同构来表达图之间的同构？反之呢？

10 1. 图的基本概念 定理5：设G＝<V,E>是简单图， ，则G中必包含一个三角。 问题：定理5给出的边界是否是紧的？
为便于讨论图算法，给出算法复杂性的几个基本定义 定义13：对于给定的函数g(n)，定义如下的函数集合 O(g(n)):={f(n)|存在正常数c和n0，使得对于所有n≥ n0，0≤f(n) ≤cg(n)}，称g(n)为O(g(n))中任意函数f(n)的渐近上界（注：一般要求g(n)和f(n)定义于N）

11 1. 图的基本概念 注：算法的时间复杂性，可通过计算开销对于输入长度的函数的渐近上界来刻画
例子：给定图G=<V,E>，构造一个求△(G)的算法，使其最坏时间复杂性的渐近上界为O(n+m)，这里n=|V|， m=|E| 。 定义14：如果一个算法的时间复杂性的渐近上界是输入长度的多项式函数，则称该算法是有效的， 思考题：尝试给出一个判定图同构的算法，说明该算法的在时空效率方面是否是有效的。

12 2. 路与回路 定义1：给定图G=<V,E>，设v0,v1,…,vn ∈ V，e1,e2,…,en ∈ E，其中ei是关联于结点vi-1，vi的边，交替序列v0 e1 v1 e2 … en vn称为结点v0到vn的路(walk)。 注：v0和vn分别称作路的起点和终点。 边的数目n称作路的长度。 当v0 = vn时，这条路称作回路(closed walk)。 若一条路中所有的边e1,e2,…,en均不相同，称作迹(trail)。起点和终点重合的迹称为闭迹(closed trail or circuit)。 若一条路中所有的结点v0,v1,…,vn均不相同，称作通路(path) 。闭的通路，即除v0 = vn外，其余的结点均不相同的路，称作圈(cycle)。

13 2. 路与回路 长度为L的通路记为PL 长度为L的圈记为CL， C3称为三角，C4称为四边形， C5称为五边形…
简单图路中，路可以由其结点序列v0v1…vn表示；结点数大于1的路也可由边序列e1e2…en表示。 例子 定理1：无向图G=<V,E>的边集合E可以被划分为一组圈，当且仅当V中的任意结点v的具有偶数度。 问题：定理1如何推广到有向图？

14 2. 路与回路 定理2：在一个具有n个结点的图中，若从结点vj到结点vk存在一条路，则从vj到vk必存在一条不多于n－1条边的通路。
定义2：无向图G中，结点u和v之间若存在一条路，则称结点u与结点v是连通的(connected)。 注：结点之间连通性是G的结点集V上的等价关系；由此等价性，可决定V上的一个划分V1,V2 ,…, Vk，使得属于同一分块的结点之间互相连通，将这样的分块称为图G的一个连通分支(connected component)。以W(G)表示图G的连通分支数 例子

15 2. 路与回路 定义3：若图G只有一个连通分支，则称G是连通图 在图中删除点v，即是把v以及与v关联的边都删去；
在图中删除边e，仅需把该边删去。 定义4：设无向图G＝<V,E>为连通图，若有点集V1V,使图G删除了V1的所有结点后，所得的子图不是连通图，而删除了V1的任何真子集后，所得的子图仍是连通图，则称V1是G的一个点割集。若某一结点构成点割集，则称其为割点(cut vertex)。 问题：一个图是否可能有多个点割集？ 注：若G不是完全图，定义k(G)=min{|V1|| V1是G的点割集}为G的点连通度。k(G)是为了产生一个不连通图需要删去的最少结点数。 不连通图或平凡图的点连通度约定为0，存在割点的图的点连通度为1。

16 2. 路与回路 完全图Kp中，删去任何m个(m<p-1)点后仍是连通图，但是删去个p-1个点后产生了一个平凡图，故定义k(Kp)为p-1 定义5：设无向图G＝<V,E>为连通图，若有边集E1E,使图G删除了E1的所有边后，所得的子图是不连通图，而删除了E1的任一真子集后，所得的子图是连通图，则称E1是G的一个边割集。若某一个边构成边割集，则称该边为割边（或桥bridge）。 问题：一个图是否可能有多个边割集？ 注：非平凡图G的边连通度定义为：λ(G)=min{|E1|| E1是G的边割集}。 λ(G)是为了产生一个不连通图需要删去的最少边数。 对平凡图G或一个不连通图G，定义其λ(G)为0 问题： λ(Kp)=?

17 2. 路与回路 定理3：若W(G)=n，在G中删除一边获得G’，则W(G’) ≤n+1
定理4：对于任何一个图G，有k(G) ≤λ(G) ≤ δ(G) 定理5：一个连通无向图G中的结点v是割点 存在两个结点u和w，使得结点u和w的每一条路都通过v。 定义6：若u可达v，它们之间所有路中，最短路的长度称为结点u和v之间的距离，记作d<u,v>，若从u到v不可达，d<u,v>＝∞。称D=max{d<u,v>|u,v∈V}为图G=<V,E>的直径 注：d<u,v> ≥ 0，d<u,u>＝0 d<u,v> ＋ d<v,w> ≥ d<u,w>

18 2. 路与回路 对于无向图，d(u,v)=d(v,u)
定义7：在简单有向图G中，任一对结点间，至少有一个结点到另一个结点是可达的，则称这个图是单侧连通的。若对于图G中任一对结点两者之间是相互可达的，则称这个图是强连通的。若在图G中略去边的方向，将它看成无向图后，图是连通的，则称该图为弱连通的。 例子 注：若图G是强连通的，则必是单侧连通的； 若图G是单侧连通的，则必是弱连通的。 以上两命题，其逆不真。

19 2.路与回路 定理6：一个有向图是强连通的当且仅当G中有一个回路，它至少包含每个结点一次。
定义7：在简单有向图中，具有强连通性质的极大子图称为强分图；具有单侧连通性质的极大子图称为单侧分图；具有弱连通性质的极大子图称为弱分图。 问题：简单有向图是否可能有多个强（弱、单侧）分图？ 定理7：在有向图G＝<V,E>中，它的每一结点位于且只位于一个强分图中。

20 2.路与回路 定理8：若无向图G恰有两个奇数度结点，则此两点间必有一条路
定义8：如果图G=<V,E>的结点集合V可划分为两个非空集合V1 、 V2的并，使得任意e∈E均连接了分处V1和V2中的两个结点，则称其两分图（bipartite graph）。 例子 定理9：简单图G=<V,E>是两分图 iff 不包含任何奇圈。

21 3. 图的矩阵表示 定义1：设G=<V,E>是一个简单图，它有n个结点V={v1,v2,…vn}，定义n阶方阵A(G)=(aij)为G的邻接矩阵： 若G是无向图，aij=1，iff vi adj vj，aij=0，if vi nadj vj 或 i=j，这里adj表示邻接，nadj表示不邻接。 若G是有向图，aij=1 iff <vi ，vj>∈E 注：如无特别说明，只考虑简单图的邻接矩阵。 无向图G的邻接矩阵A(G)是对称的；有向图的邻接矩阵则一般不对称。 对于有向图，邻接矩阵第i行的元素和等于结点vi的出度；第j列的元素和等于结点vj的入度。

22 3. 图的矩阵表示 例子 定义2：将n阶方阵A的列作一置换，再将相应的行作同样的置换，得到一个新的n阶方阵A’，则称A’与A置换等价。
注：任意置换可分解为一组初等置换的复合；任意置换矩阵可表示为一组初等置换矩阵的乘积。所以任意置换可由置换矩阵表示 置换等价是n阶布尔矩阵集合上的等价关系。 图的结点按不同次序所写出的邻接矩阵是彼此置换等价的，可取图的任一邻接矩阵作为该图的矩阵表示

23 3. 图的矩阵表示 可由图的邻接矩阵求得图上点与点之间路的数目：设有向图G的结点集合V={v1,v2,…vn}，它的邻接矩阵为A(G)=(aij)n×n，则从结点vi到结点vj的长度为2的路的数目为： ai1a1j+ ai2a2j+…+ ainanj=∑kaikakj 这恰好等于矩阵(A(G))2中第i行，第j列的元素。 以 表示。 类似地，从vi到vj长度为3的路可以看做由vi到vk的长度为1的路，再联结由vk到vj长度为2的路所形成的，即： 。上述结论可以推广到任意长度为n的路

24 3. 图的矩阵表示 定理1：设A(G)是图G的邻接矩阵，则(A(G))l中的i行j列元素等于G中联结vi与vj的长度为l的路的数目。
定义3：设G=<V,E>是一个简单图，它有n个结点V={v1,v2,…vn}，定义n阶方阵P(G)=(pij) ，其中， pij = 1 从vi到vj至少存在一条路 = 0 从vi到vj不存在任何路 称矩阵P是图G的可达性矩阵 注：无向图的可达性矩阵是对称的，有向图的可达性矩阵则一般不对称。

25 3. 图的矩阵表示 可由图G的邻接矩阵A得到可达矩阵P，即令 P=A+A2+…+An-1，
再将P中不为0的元素改换为1，即得可达矩阵P（或者，在计算P和Ai时可采用布尔运算规则）。 若把邻接矩阵看作点集V上关系R的关系矩阵，则求可达矩阵即为求R的传递闭包，可用Floyd-Warshall算法求解 问题：利用Floyd算法的思想，构造一个求解权重图最短路径长度的算法，并说明算法复杂性

26 3. 图的矩阵表示 问题：求解可达性矩阵或传递闭包的算法是否可能进一步优化？ 动态规划(dynamic programming)的基本原则
对于特定问题，可否应用动态规划？ 1 动态规划能否求解特定问题？ 2 动态规划能否有效求解特定问题？ 例子：Viterbi、SAT 思考题：2-SAT是否存在有效解法？ Aspvall, Bengt; Plass, Michael etc. (1979), "A linear-time algorithm for testing the truth of certain quantified boolean formulas", Information Processing Letters 8 (3): 121–123

27 3. 图的矩阵表示 定义4：给定简单无向图，G＝<V,E>，|V|=n，定义n×n矩阵L(G)=(lij), 其中
－ 若在G中(vi, vj)是G的边 lij = deg(vi ) i=j 其他 称L(G)为无向图G的拉普拉斯矩阵(Laplacian)。 例子 注：Laplacian矩阵必有一个特征值为0 Laplacian矩阵半正定

28 3. 图的矩阵表示 引理：简单无向图G与H同构，当且仅当存在置换矩阵P使得L(G)=PL(H)PT，这里置换矩阵P是初等置换矩阵的乘积
注：类似可证简单无向图G与H同构iff存在置换矩阵P使得A(G)=PA(H)PT 定理2：简单无向图G与H同构的必要条件是L(G)与L(H)具有完全相同的特征值 注：类似可证简单无向图G与H同构的必要条件是A(G)与A(H)具有完全相同的特征值 定理3：若G与H同构，设ui和vi分别是无向图A(G)和A(H)的第i个最小特征值λi所对应的特征向量，λi 孤立且ui和vi同模，则存在置换π，使得ui(j)=vi(π(j))

29 应用例子： Laplacian Eigenmap
背景：流形学习（信息抽象） 科学理论是对经验数据的约简和压缩描述。 “Physics is experience, arranged in economical order” (物理学是以思维经济的原则组织经验材料) Ernst Mach

30 应用例子： Laplacian Eigenmap
用尽可能少的独立变量建模经验数据

31 应用例子： Laplacian Eigenmap
例子：牛顿万有引力的发现 观测量：行星绕太阳运行的周期T 行星距太阳的距离r(t), t=1,2,…,T 行星的角速度ω(t), t=1,2,…,T （以上观测量总结为经验规律：开普勒三定律） 每个行星需要2T+1个观测量加以描述 牛顿发现这2T＋1个观测量由更少的隐变量所决定

32 应用例子： Laplacian Eigenmap
由F(t)=km/r(t)2，有 r(t)=(km/F(t))^(1/2), t=1,2,…,T ω(t)=(F(t)/mr(t)) ^(1/2), t=1,2,…,T T=2π/ ω ， ω是ω(t)的均值 即有

33 应用例子： Laplacian Eigenmap
原理：给定D维空间中n个点，假定已经建立了相应的图表示G = <V, E>。 首先考虑将这n个映射到一条直线之上，使得在G中相邻的点尽可能地靠近，因此我们希望最小化 这里yi是第i个样本点在直线上的嵌入。 记 注意到对于任意的y有

34 应用例子： Laplacian Eigenmap
原理（续） 由此，最小化问题可归约为 这里的约束 是为了去除任意的尺度缩放 这样，一般化特征值问题 的次小特征值所对应的特征向量，即为所求 由于1是特征值0所对应的特征向量，所以问题可更精确地表述为

35 应用例子： Laplacian Eigenmap
原理（续） 更一般地，由RD到Rd的嵌入由n×d矩阵 Y = [y1, y2, …, yd] 给出，其每一行对应一个样本点的d维嵌入。 这里y1, y2, …, yd分别是除0之外最小d个特征 值所对应的满足约束的特征向量 更形式地，问题需最小化 即求解 ，且yi正交于1

36 应用例子： Laplacian Eigenmap
参考： 1 Laplacian Eigenmaps and Spectral Techniques for Embedding and Clustering 2 Nonlinear Dimensionality Reduction by Locally Linear Inlaying

37 3. 图的矩阵表示 定义5：给定无向图G，v1,v2,…,vp和e1,e2,…,eq分别是G的结点和边，定义矩阵M(G)=(mij),其中
mij = 1 若vi关联ej 0 若vi不关联ej 称M(G)为无向图G的完全关联矩阵。需注意的是:无向图的关联矩阵不考虑自回路，若有自回路则删去 例子 注：图中每一边关联两个结点，故M(G)的每一列中只有两个1。 每一行中元素和是对应结点的度数。 一行中元素全为0，其对应的结点为孤立结点。

38 3. 图的矩阵表示 两个平行边对应的两列相同。 同一个图当结点或边的编序不同时，其对应的M(G)仅有行序或列序的差别。
定义6：给定有向图，G＝<V,E>，V={v1,v2,…,vp }，E={e1,e2,…,eq }，定义p×q阶矩阵M(G)=(mij), 其中 1 若在G中vi是ej的起点 mij = －1 若在G中vi是ej的终点 0 若vi与ej不关联 称M(G)为有向图G的完全关联矩阵。需注意的是:有向图的关联矩阵不考虑自回路，若有自回路则删去

39 3. 图的矩阵表示 完全关联矩阵M(G)中，若记vi对应的行是 ，则可如下定义第i行与第j行的相加：对有向图，第i行与第j行的相加是指对应分量的普通加法运算；对无向图是指对应分量的模2加法运算。有向图和无向图的行相加均记为 ，其意义是将G的结点vi与vj合并。 例子

40 3. 图的矩阵表示 定理4：若一个无向连通图G有r个结点，则其完全关联矩阵M(G)的秩为r－1，即 rank M(G) = r－1（这里的秩计算是在完全关联矩阵加法和乘法意义下的） 。 推论：设无向图G有r个结点，w个连通分支，则图G完全关联矩阵的秩为r－w。

41 4. 欧拉图与汉密尔顿图 定义1：给定无孤立结点图G，若存在一条路，经过图中每边一次且仅一次，该条路称为欧拉路（Euler trail）；若存在一条回路，经过图中每边一次且仅一次，该回路称为欧拉回路（Euler circuits） 。 注：欧拉路和欧拉回路分别是迹和闭迹 具有欧拉回路的图称为欧拉图。 定理1：无向图G具有一条欧拉路 iff G是连通的，且有零个或两个奇数度结点。 推论：无向图G具有一条欧拉回路 iff G是连通的，且所有结点度数均为偶数。

42 4. 欧拉图与汉密尔顿图 定义2：给定有向图G，通过图中每边一次且仅一次的一条单向路（回路），称为单向欧拉路（回路）。 定理2：
iff G是连通的，且每个结点入度等于出度。 ）一个有向图G具有单向欧拉路 iff G是连通的，且除两个结点外，每个结点入度等于出度，但这两个结点中，一个结点的入度比出度大1，另一个结点的入度比出度小1 。

43 4. 欧拉图与汉密尔顿图 定义3：给定图G，若存在一条路或回路，经过图中每个结点恰好一次，称这条路为汉密尔顿路（Hamilton paths）或汉密尔顿回路（Hamilton cycles）。 注：汉密尔顿路和汉密尔顿回路分别是通路和圈 具有汉密尔顿回路的图称为汉密尔顿图。 定理3：若图G=<V,E>具有汉密尔顿回路，则对于结点集V的每个非空子集S均有W(G－S) ≤|S|成立。其中W(G－S)是G－S中连通分支数。 定理4：设G是具有n个结点的简单图，若G中每一对结点度数之和大于等于n－1，则在G中存在一条汉密尔顿路（充分条件）。

44 4. 欧拉图与汉密尔顿图 定理5：设G是具有n个结点的简单图，若G中每一对结点度数之和大于等于n，则在G中存在一条汉密尔顿回路。
例子：在7天安排7门课的考试，要求由同一教师担任的课程不在连续的两天中考试。求证若没有教师担任4门以上课程，则可做出符合要求的考试安排 定义4：给定图G=<V,E>有n个结点，若将图G中度数之和至少是n的非邻接结点连接起来得图G’,对图G’重复上述步骤，直到不再有这样的结点对存在为止，所得到的图，称为原图G的闭包，记作C(G)。 例子

45 4. 欧拉图与汉密尔顿图 定理6：当且仅当一个简单图的闭包是汉密尔顿图时，这个简单图是汉密尔顿图。
给定任意图G，不存在有效的算法判定其中是否有汉密尔顿路或回路（假设P不等于NP）；事实上，汉密尔顿路或回路的存在性判定是NP完全问题 以标记法判定汉密尔顿路的存在性： 相邻点分别采用不同标记 若两个相邻点的标记相同，则在其间插入采用不同标记的新点（例子：p310图7-4.13） 问题：上述方法是否可以作为判定汉密尔顿路存在性的充要判据？

46 5. 平面图 定义1：设G＝<V,E>是一个无向图，若能够把G的所有结点和边画在平面上，且使得任何两条边除了端点外没有其他的交点，则称G为平面图(planar graph) 。 注：某些表面上有边相交的图实际上是平面图；某些图无论如何改画都存在相交的边，这类图不是平面图 定义2：设G是一连通的平面图，由图中的边所围成的区域，在区域内既不包含图的结点，也不包含边，这样的区域称为G的一个面(face)；包围该面的诸边所构成的图形称为这个面的边界。 注：本课程只对连通平面图讨论面

47 5. 平面图 例子（p313图7-5.3） 注： 两个点属于同一个面的充要条件是这两个点之间可由一条连续曲线相连，且此曲线不经过图的任何点或边。 面的边界是回路（Closed Walk） 构成面r边界的回路长度称作该面的次数，记deg(r) 。 对于只是一个面r的边界的边，计算r的次数时应两次计算此边

48 5. 平面图 定理1：一个有限（连通）平面图，面的次数之和等于其边数的两倍。（例子：p313图7-5.3）
定理2（图论欧拉定理）：设有一个连通的平面图G，共有v个结点，e条边和r个面，则欧拉公式 v－e＋r ＝ 2 成立。 定理2*（拓扑欧拉定理）：设凸多面体有v个结点，e条棱和r个面，则v－e＋r＝2成立（证明作为思考题）。 注：定理2*的结论可扩展到满足下列条件的多面体P 1） P的任何两个顶点可以用一串棱相连 且2） P表面上的任何直线段构成的圈将P的表面分成不连通的两部分

49 5. 平面图 平面图与凸多面体的关系？ 任何凸多面体决定了一个画于平面上的3-连通简单平面图表示；反之，任何3-连通简单平面图决定了一个凸多面体。Duijvestijn, A. J. W. and Federico, P. J. "The Number of Polyhedral (-Connected Planar) Graphs." Math. Comput. 37, , 1981 注：点连通度大于等于3的图称为3-连通图 定理3：设G是一个有v个结点，e条边的连通简单平面图，若v≥3，则e≤3v－6。

50 5. 平面图 注：此定理的条件是必要条件 例子：求证K5和K3,3不是平面图
定义：图的围长（girth）定义为其最短圈的长度。若图中无圈，约定其围长为无穷大 定理4：设G是有v≥3个结点，e条边的连通简单平面图，若G的围长为g，则e≤max｛(n-2)*g/(g-2),n-1｝ 平面图的判定问题：在给定图G的边上，插入一个新的度数为2的结点，使一条边分成两条边，或者对于关联于一个度数为2的结点的两条边，去掉这个结点，使两条边化成一条边，都不会影响图的平面性。 定义3：给定两个图G1和G2 ，若它们是同构的，或者在反复插入或除去若干2度结点后同构，则称G1和G2是在2度结点内同构的。

51 5. 平面图 定理4（Kuratowski）：一个图是平面图 iff 它不包含与K3,3或K5在2度结点内同构的子图。
思考题：尝试给出一个判定平面图的算法。你给出的算法是有效的吗？ （线索：Hopcroft & Tarjan 1974）

52 6 对偶图与着色 引入：资源任务分配问题 地图着色问题，四色问题
定义1：给定平面图G=<V,E>，它具有面F1 ,F2,…Fn ，若有图G*=<V*,E*>满足： a)对于图G的任一面Fi，内部有且仅有一个结点vi*∈V*。 b)对于图G的面Fi ,Fj的公共边界ek，存在且仅存在一条边ek* ∈ E* ，使ek* =(vi* , vj* )，且ek*与ek相交。 c)当且仅当ek只是一个面Fi的边界时， vi*上存在且仅存在一个环ek*和ek相交。 则称图G*是图G的对偶图。

53 6 对偶图与着色 注：定义1中的“相交”，均指相交于一点； 对偶图的任一边与且仅与原图中的一条边相交 例子
注：若G*是连通平面图G的对偶图，则G是G*的对偶图 一个连通平面图G的对偶图G*也是平面图 定义2：如果图G的对偶图G*同构于G，则称G是自对偶图。

54 6 对偶图与着色 注：1.对于地图的着色问题可以归结为对其对偶图的结点的着色问题；四色问题可以归结为证明：一定可以用四种颜色，对地图的对偶图进行结点着色，使得邻接的结点都有不同的颜色。 2.如果图G在着色时用了n种颜色，称G为n-色图。 3.对于图G着色时，需要的最少颜色数称为G的着色数，记作x(G)。 不存在有效算法一般地判定图是否是n-色的(n≥ 3)， 有一些图着色的启发，例如：

55 6 对偶图与着色 Welch Powell启发 a) 将图G中的结点按照度数的递减次序进行排列。（排列可能不是唯一的，因为可能序某些点度数相同） b) i:=1 c) 用第i种颜色对当前度数最大的未着色点着色；并按排列次序，对所有与目前已被颜色i着色的点不邻接的点着上颜色i。 d) 若V中仍有未着色的点 then i:=i+1，返回c)； else 结束

56 6 对偶图与着色 定理1：对于任意图G，Powell启发最多使用Δ(G)＋1种颜色，即可完成着色 问题：上述启发的时间复杂性？
此启发与“不存在有效算法判定图是否是n-色的” 矛盾吗？ 问题：Powell启发为什么按照结点度数递减的次序着色？ 定理2：对于n个结点的完全图Kn，有x(Kn)=n。 定理3：设G为一个至少具有三个结点的简单连通平面图，则G中必有一个结点u，使得deg(u) ≤ 5。

57 6 对偶图与着色 定理4：任意简单平面图G最多是5-色的。 问题：定理4能否推广到任意平面图？
注：无飞地的四色地图问题于1976年被证明（阿佩尔&黑肯） 思考题：是否存在有效算法判定任意图能否被两种颜色正常着色？ 练习：证明任意6个人中，总有3个人互相认识，或3个人互相不认识。

58 7. 树与生成树 定义1：一个连通且无回路的无向图称为树。树中度数为1的结点称为树叶，度数大于1的结点称为分枝点或内点。一个无回路的无向图称作森林，它的每个连通分支是树。 定理1：定理1：给定图G，以下关于树的定义是等价的。 1) 无回路的连通图。 2) 无回路且e＝v－1，其中e是边数，v是结点数。 3) 连通且e＝v－1。 4) 无回路，但增加一条新边，得到一个且只有一个回路。 5) 连通，但删去任一边后便不连通。 6) 每一对结点之间有一条且仅有一条路。 注：定义1和定理1中的“回路”指“圈”

59 7. 树与生成树 例子 定理2：任一棵树中至少有两片树叶。 定义2：若图G的生成子图是一棵树，则称该树为生成树。
注：1) 设图G有一棵生成树T，则T中的边称作树枝。 2) 图G中不在生成树中的边称作弦。 3) 所有弦的集合称作生成树T的补。 注：图的生成树一般不唯一 定理3：连通图至少有一棵生成树。

60 7. 树与生成树 设G为一个有n个结点和m条边的连通图，则G的生成树正好有n－1条边。因此要确定G的一棵生成树，必须删去G的m-(n-1)=m-n+1条边，将m-n+1称为连通图G的秩。 连通图G的生成树的构造算法 1) 从V中任取一点x，依据V中各点与x的最短距离，将V划分为V0,V1,V2,…，其中Vi 中的点与x的距离为i 2) 对于Vi,i>0中任意一点y，在G中必与Vi－1中的某些点相邻，将某一个这样的点z与y相连。 3) 重复上步，直到每个Vi,i>0中的点均与某一Vi－1,i>0中的点相连，以此获得的生成图即为图G的生成树

61 7. 树与生成树 问题：上述算法的时间复杂性？ 例子：Dijkstra算法的求解结果中所包含的边是连通图的一个生成树
定理4：G的任一条回路和G的任何一棵生成树的补至少有一条公共边。 定理5：任一边割集和任何生成树至少有一条公共边。 设G是具有n个结点的连通图。对应于G的每一条边e，指定一个正数C(e)，称为边e的权。G的生成树T也有一个树权，它是T的所有边权的和。

62 7. 树与生成树 定义3：在图G的所有生成树中，树权最小的那棵生成树，称作最小生成树。
定理6：设图G有n个结点，以下算法（Kruskal算法）产生的是最小生成树。 a) 选取最小权边e1，置边数i:=1； b) 若 i = n-1结束，否则转c)； c) 设已选择边为e1, e2,… ei ，在G中选取不同于e1, e2,… ei的边ei+1，使{e1, e2,… ei, ei+1}中无回路且ei+1是满足此条件的最小边（若有多条边满足此条件，则选择其中任意一条）。 d) i:= i ＋1，转b) 。

63 7. 树与生成树 例子 贪婪原则 算法二 1) 将G所有的边依照权重的降序排列 2) i:=1 3) 若删除边ei不会导致G不连通，则删除之
4) 若当前剩余的边形成一个树，则算法结束 否则i:=i+1；返回3) 定理7：算法二产生的结果是G的最小生成树

64 7. 树与生成树 例子：连通图G的结点集合由黑白两色结点构成，是否存在有效算法，使用数目最少的白色结点，使得所有黑色结点之间互相可达？
回答：不存在（除非P=NP），实际上该问题是NPC的，因为NP完全问题最小Steiner树的求解可多项式地归约为该问题的求解。 最小Steiner树问题：给定图G = < V, E> 和V的子集R，E中的每条边e有正整数边权w(e)，求解包含R中所有结点的最小权重子树。 思考题：给出归约的过程

65 8. 根树及其应用 定义1：如果一个有向图在不考虑边的方向时是一棵树，则称其为有向树。
定义2：一棵有向树，若恰有一个结点的入度为0，其余所有结点的入度都为1，则称为根树。根树中，入度为0的结点称为根，出度为0的结点称为叶，出度不为0的结点称为分枝点或内点。 例子 注：在根树中，任意结点v的层次，就是从根到该结点的单向通路长度。 根树可有不同的画法

66 8. 根树及其应用 从根树的结构中可以看到，树中每一个结点都可以看作是原来树中的某一棵子树的根，由此，根树可递归定义
定义3：根树包含一个或多个结点，其中有唯一满足如下两个条件的结点称为根 1）根的入度为0 2）根到所有结点是可达的 树根之外的结点被分成树根的出度个子根树。 注：1. 这个定义把n个结点的根树用结点数少于n的根树来定义，最后归约为一组只包含一个结点的根树，它们就是原来那棵树的叶。 2. 若指明根树中的结点或边的次序，则称其为有序树。 3. 结点之间的关系称谓

67 8. 根树及其应用 定义4：在根树中，若每一个结点的出度小于或等于m，则称这棵树为m叉树。若每一个结点的出度恰好等于m或0，则称这棵树为完全m叉树，若其所有树叶层次相同，称为正则m叉树。当m＝2时，称为二叉树。 例子 以完全m叉树表示实际问题（p330图7-8.4）

68 8. 根树及其应用 有序树与二叉树由下述改画方法可建立一一对应。
1) 除了最左边的分枝点外，删去从每一个结点长出的所有分枝。在同一层次中，兄弟结点之间用从左到右的有向边连接。 2)选定二叉树的左子和右子如下：直接处于给定结点下面的结点，作为左子，对于同一水平线上与给定结点右邻的结点，作为右子，以此类推。 问题：为什么要将一般的有序树改画为二叉树？ 给定某有序树的二叉树表示，如何访问树中 某结点的第三子（如果存在）？ 注：上述方法可推广到有向森林的改画

69 8. 根树及其应用 定理1：设有完全m叉树，其树叶数为l，分枝点数为i，则(m－1)i＝l－1。
推论：存在l个树叶的完全m叉树，当且仅当i=(l－1)/(m－1)是正整数。 例子：28个电灯，用四插座接线板级联，需几个接线板？ 问题：给定l和m，完全m叉树是否唯一？ 定义5：在根树中，一个结点的通路长度，就是从树根到此结点的通路中的边数。分枝点的通路长度称为内部通路长度，树叶的通路长度称为外部通路长度。

70 8. 根树及其应用 定理2：若完全二叉树有n个分枝点，且内部通路长度的总和为I，外部通路长度的总和为E，则：E=I+2n
问题：对于完全m叉树，是否有E=I+mn ？ 给定一组权w1,w2,…, wt，设w1≤w2 ≤ … ≤ wt 。设有一棵二叉树，共有t片树叶，分别带权w1, w2,…, wt，该二叉树称为带权二叉树。

71 8. 根树及其应用 定义6：在带权二叉树中，若带权为wi的树叶，其通路长度为L(wi)，我们把w(T)=∑ti=1wiL(wi) ，称为该带权二叉树的权。在所有带权w1, w2,… , wt的二叉树中， w(T)最小的那棵树，称为最优树。 最优树的应用例子：压缩编码 注：最优树必是完全的 定理3：设T为带权w1 ≤w2 ≤…≤wt的最优树，则： a)以树叶vw1,vw2为子的分枝点，其通路长度最长。 b)带权的w1, w2树叶vw1,vw2是兄弟。

72 8. 根树及其应用 定理4：设T为带权w1 ≤w2 ≤…≤wt的最优树，若将以带权w1和w2的树叶为儿子的分枝点改为带权w1+w2的树叶，得到一棵新树T’，则T’也是最优树。 根据定理3和定理4，要画一棵带有t个权的最优树，可简化为画一棵带有t-1个权的最优树，而这又可简化为画一棵带有t-2个权的最优树，依此类推。具体做法：首先找出两个最小的权值，设为w1和w2，然后对t-1个权w1+w2,w3,… ,wt求作一棵最优树，并将这棵最优树的结点 代之以 w1 w2 w1+w2

73 8. 根树及其应用 二叉树的另一个应用－前缀码问题 定义7：给定一个序列的集合，若没有一个序列是另一个序列的前缀，该序列集合称为前缀码。
定理5：任意一棵二叉树的树叶可对应一个前缀码。 定理6：任何一个前缀码都对应一棵二叉树。 注：如果给定前缀码对应的二叉树是完全二叉树，则给定任意bit序列，均可对其译码。

74 9. 有向图的流理论 问题引入：电网的传输能力问题 交通网的运输能力问题
定义1：给定有向连通图G＝<V,E>，f是定义于E之上的非负函数，若除了V中两个特殊结点之外，f在其余每个结点之上均满足Kirchhoff条件： ∑yf(x,y) = ∑z f(z,x) y∈K+(x) z∈K-(x) 其中K+(x)={y|y∈V,<x,y>∈E}, K-(x)={y|y∈V,<y,x>∈E}, f(x,y)表示f(<x,y>)的值 则称f是G上的流(flow)

75 9. 有向图的流理论 注：若<x,y>不属于E，则f(x,y)＝0
易证两个特殊结点中，一个结点的流出量大于等于流入量，记该点为s；另一个结点的总流入量大于等于总流出量，记该点为t。由此f通常称为从s到t的流。 流出s的总流量等于流入t的总流量，即有 ∑f(s,y) － ∑f(y,s) ＝ ∑f(y,t) － ∑f(t,y) y∈K+(s) y∈K-(s) y∈K-(t) y∈K+(t) 记s的总流出量（或t的总流入量）为v(f)，称为流f的值 例子 网络的最大流问题在给定G的各边容量限制的情况下求从f到t的流f的最大值

76 9. 有向图的流理论 定义2：给定有向连通图G＝<V,E>，容量c是定义于E之上的非负函数，c规定了流过各边的流量上界，称为容量(capacity) 注：以c(x,y)表示c(<x,y>)的值 若<x,y>不属于E，则约定c(x,y)＝0 定义3：给定有向连通图G＝<V,E>，若S是V的子集，且s属于S，t不属于S，则 E(S,～S)={<x,y>∈E|x∈S, y∈～S} 称为E的截(cut) 例子

77 9. 有向图的流理论 注：若删除一个截中的所有边，则不会有从s到t的正值流存在；反之，若F是E的某个子集，且删除F后不存在从s到t的正值流，则F必包含某个截 定义截E(S,～S)的容量为： c(S,～S) ＝∑c(x,y), <x,y>∈E(S,～S) 显然，任何截的容量至少不应小于最大流的值 定理1（最大流最小截定理）：从s到t的最大流等于最小截的容量

78 9. 有向图的流理论 证明概要：假设最大流v(f)有限，如下定义集合S： 1） 令s属于S
2） 若x属于S，且c(x,y)>f(x,y) or f(y,x)>0 则加y加入S 3） 重复上步，直到V中没有元素可添加 显然，t不属于S，即E(S,～S)是V的一个截。否则必存在s=x0,x1,…,xk=t，使得对0<=i<=k-1， di=max{c(xi, xi+1)-f(xi, xi+1),f(xi+1, xi)}>0，令d=minidi，则流的值可以增加到v(f)+d，矛盾。 由此流f在截E(S,～S)上的值可以由如下公式获得： ∑f(x,y) － ∑f(y,x) = c(S,～S) x∈S, y∈～S x∈S, y∈～S

79 9. 有向图的流理论 最大流构造算法（假设各边的容量是整数） 1) i:=0 2) fi(x,y)=0，任意<x,y>属于E
3) 由定理1证明中的过程，构造Si 4) 若t属于Si， 则利用定理1证明的过程，获得新流fi+1=fi+n，n是一个正整数；i:=i+1；更新fi(x,y)，返回3) 否则，结束算法，此时的fi即为最大流 注：若各边的容量不是整数，则通过做同比的缩放，可以任意的精度近似求解最大流 显然，若各边的容量为整数，则必存在各边流值均为整数的最大流

80 9. 有向图的流理论 定理2：从一组源结点到一组汇结点的最大流等于分割所有源和汇的最小截中的容量
定义3：给定有向连通图G＝<V,E>，容量c是定义于V-{s, t}之上的非负函数，c规定了流过各点的流量上界，称为点容量(vertex-capacity) 定义4：给定有向连通图G＝<V,E>，若S是V-{s，t}的子集，且删除S后s和t在G-S中不再连通，则S称为V的点截(vertex-cut) 定理3：给定有向图G及其上的点容量c，s和t分别是源和汇，则从s到t的最大流等于容量最小的点截的容量

81 10. 连通性和Menger定理 定义1：一个图G是k-连通（k-connected）的，当且仅当它至少有k+1个结点，且删除其中任何k-1个结点不会导致不连通 注：通常所说的“连通的”可理解为1-连通 一个k-连通的图（k>1）显然也是k-1连通的 定义2：若图G是k-连通的，但不是(k+1)-连通的，则称k是G的连通度(connectivity)。 定义3：一个图G是k-边-连通（k-edge-connected）的，当且仅当它至少有2个结点，且删除G中任何k－1条边不会导致不连通

82 10. 连通性和Menger定理 定理1：若G1和G2都是图G的k-连通子图，且G1和G2至少有k个公共点，则G1+G2也是k-连通的
定义4：设G=<V,E>连通，W包含于V，若图G-W不再连通，则称W分割了G；如果V-W中的两个点s和t属于图G-W的不同连通分支，则称W分割了s和t 定理2（Menger定理）：1) 若s和t是图G中的两个非邻接的点，则分割s和t的最小结点数等于从s到t的最大独立通路数。2) 若s和t是图G中的两个点，则分割s和t的最小边数等于从s到t的最大独立迹数。 注：独立通路指没有相同的结点的通路 独立迹指没有相同边的迹

83 10. 连通性和Menger定理 推论：若s和t是图G中的两个非邻接的点，则分割s和t的最小结点数小于等于：
min{deg(s),deg(t)} 定理3：1) 图G=<V,E>是k-连通的，当且仅当|V|>1，且G中任何两点之间至少存在k条独立通路。2) 图G=<V,E>是k-边-连通的，当且仅当|V|>1，且G中任何两点之间至少存在k条独立迹。 练习：两分图的最大匹配问题

84 10. 连通性和Menger定理 思考题：是否存在算法有效求解有向图的最小点割集？
线索：有向图的k-cut问题存在有效算法，这里k-cut问题定义如下： 给定有边权的图G=<V,E>，求解V的一个划分V1,V2,…, Vk ，最小化 ∑w(x,y), x∈Vi, y∈Vj, i不等于j。

85 11 两分图的匹配 问题引入： 1 给定X的一族子集A={A1,A2,…,Am}，是否可能找到X的m个不同的元素，使得每个元素恰好属于某个Ai，以作为Ai的代表元素？ 2 婚礼问题：m个女人，n个男人，每个女人认识若干个男人，是否可能让每个女人找到一个认识的男人做新郎？ 两分图G(m,n)的完全匹配问题：是否存在m个独立边？

86 11 两分图的匹配 定理1：若两分图G的结点集V=V1∪V2，则G包含一个从V1到V2的完全匹配 iff 如下条件成立：
|K(S)| ≧ |S| ，对于V1的任意子集S 注：定理1中，K(S)定义为结点集S的邻接结点集 推论1：X的一族子集A={A1,A2,…,Am}具有m个代表元素，iff 如下条件成立： |∪i属于F Ai| ≧ |F|，对于任意｛1, 2,…, m｝的真子集F

87 11 两分图的匹配 推论2：若两分图G的结点集V=V1∪V2，则G中包含|V1|-d条独立边 iff G满足如下条件：
|K(S1)| ≧ |S1|-d ，对于V1的任意子集S1 定理2：若两分图G的结点集V=V1∪V2，|V1|=m，|V2 |=n；记h为G中的最大独立边数，i为G中的最大独立点数，j为覆盖G中所有结点的最小边和点的数目，则以下关系成立： i=j=m+n-h 注：独立点指不邻接的点

88 11 两分图的匹配 证明： 1) j=m+n-h，令E’∪V’是覆盖了所有结点的最小集合。如果E’ 的两个元素e和f有公共端点，则可以简单地用f的另一个端点代替f。因此，可假定E’只包含独立边。由于E’显然应最大化，即E’=h，故有j=m+n-h 2) i=m+n-h i)假设VI是G的一个最大独立结点集，EI是G的一个最大独立边集。 i≦m+n-h，EI 中任意边至少与V- VI中的一个点相邻，且EI 中的任意两个边无相邻的结点，故有m+n-i≧h，即i≦m+n-h

89 11 两分图的匹配 ii) 由于G的最大独立边集的势为h，根据推论2，必存在V1的子集S1，有|K(S1)|=|S1|-(m-h)。记
T= V2 -K(S1) 则S1∪T 是独立结点集，且有 | S1∪T|=|S1|+n-|K(S1)|=m+n-h 即i≧m+n-h

90 11 两分图的匹配 定理3：令G是两分图，且具有结点集合V1={x1,…,xm}和V2={y1,…,yn}，则G包含一个子图H使得dH(xi)=di，0≦dH(yi)≦1 iff 对于任意S的子集V1 |K(S)| ≧∑di xi∈S 定义1：称图G的生成子图H为r-因子，如果H中的每个结点均为r度 例子：1-因子

91 11 两分图的匹配 定理4：若图G=<V,E>具有1-因子，S是V的子集，则G-S中至多包括|S|个奇连通分支（奇连通分支即结点数为奇的连通分支） 定理5（Tutte’s 1-因子定理）：令q(G)为图G中的奇连通分支数，则图G=<V,E>有1-因子 iff 如下条件成立： q(G-S) ≦ |S|，对于任意V的真子集S