中科院研究生院专业基础课：《图论与网络流理论》第一章图的基本概念 Graph Theory and Network Flow Theory（高随祥）.pdf_大学文库

4 邻。（3）边与边的相邻：如果图 G 中两条边有至少一个公共端点，则称这两条边在图 G 中相邻。（4）环边(loop)：图中两端点重合的边称为环边。（5）重边(multiedge)：设 u 和 v 是图 G 的顶点，图 G 中连接 u 和 v 的两条或两条以上的边称为图 G 中 u、v 间的重边。（6）简单图(simple graph)：既无环边也无重边的图称为简单图。（7）完全图(complete graph)：任意两点间都有一条边的简单图称为完全图，n 阶完全图记为 Kn. （8）平凡图(trivial graph): 只有一个顶点，没有边的图。（9）空图(empty graph): 边集为空的图。（10）零图(null graph): 顶点集为空的图。（11）顶点 v 的度(degree)：图 G 中顶点 v 所关联的边的数目（环边计两次）称为顶点 v 的度，记为 dG(v)或 d(v)。（12）图 G 的最大度： (G) max{d (v) | v V (G)} Δ = G ∈ ；图 G 的最小度： (G) min{d (v) | v V (G)} δ = G ∈ 。（13）正则图(regular graph)：每个顶点的度都相等的图。（14）图的补图(complement)：设 G 是一个图，以V(G) 为顶点集，以{(x, y) | (x, y) ∉ E(G)} 为边集的图称为 G 的补图，记为G 。定理 1.1.1 对任何图 G，都有 ( ) ( ) 2 vVG d v ε ∈ ∑ = 。证明：按每个顶点的度来计数边，每条边恰数了两次。推论 1.1.1 任何图中，奇度顶点的个数总是偶数（包括 0）。证明留作练习。 4. 子图子图(subgraph)：对图 G 和 H，如果V(H) ⊆ V(G) 且 E(H) ⊆ E(G) ，则称图 H 是图 G 的子图，记为 H ⊆ G 。生成子图(spanning subgraph): 若 H 是 G 的子图且VH VG ( ) () = ，则称 H 是 G 的生成子图。点导出子图(induced subgraph)：设 G 是一个图，V ′ ⊆ V(G) 。以V ′为顶点集，以 G 中两端点均属于V ′的所有边作为边集所组成的子图，称为 G 的由顶点集V ′导出的子图，简称为 G 的点导出子图，记为G[V ′]. 边导出子图(edge-induced subgraph)：设 G 是一个图， E′ ⊆ E(G) 。以 E′为边集，以 E′中边的所有端点作为顶点集所组成的子图，称为 G 的由边集 E′导出的子图，简称为 G 的边导出子图，记为G[E′]

设gV(G),EcE(G),今后经常用G-表示从图G中删除顶点子集V"(连同它们关联的边一起删去)所获得的子图,用G-E表示从图G中删除边子集E′(但不删除它们的端点)所获得的子图。特别地,对顶点v和边e,常用G-v表示G-{v},G-e 表示G-{e}图G的一个顶点子集E'。 5.路和圈途径wak:图G中一个点边交替出现的序列w=veve2…∈V称为图G的一条途径, 其中v、V分别称为途径w的起点和终点,w上其余顶点称为中途点迹(trai):图G中边不重复的途径称为迹。路(path):图G中顶点不重复的迹称为路。 (注:简单图中的路可以完全用顶点来表示,P=VV1…v) 闭途径( closed walk:图G中起点和终点相同的途径称为闭途径。闭迹( closed trail):图G中边不重复的闭途径称为闭迹,也称为回路( circuit)。圈( cycle):中途点不重复的闭迹称为圈注 (1)途径(闭途径)、迹(闭迹)、路(圈)上所含的边的数目称为它的长度 (2)简单图G中长度为奇数和偶数的圈分别称为奇圈 odd cvcle)和偶圈( even cvcle) (3)对任意x,y∈V(G),从x到y的具有最小长度的路称为x到y的最短路( shortest path) 其长度称为x到y的距离 distance,记为d(x,y) (4)简单图G中最短圈的长度称为图G的围长 girth),最长圈的长度称为图G的周长 (circumference) 例112设G是一个简单图,若δ(G)≥2,则G中必含有圈证明:设G中的最长路为P=vV1…V。因d(v0)≥2,故存在与v1相异的顶点v与v相邻。若vgP,则得到比P更长的路,这与P的取法矛盾。因此必定v∈P,从而G中有圈。证毕。例113设G是简单图,若(G)≥3,则G必有偶圈证明:设P=v0V1…v是G的最长路。因为d(v)≥3,所以存在两个与v1相异的顶点v,v”与v相邻。v,v"必都在路P上, 否则会得到比P更长的路。无妨设v=,"=v,(</)。若i,j中有奇数,比如i是奇数,则路P上v0到v的一段与边vv构成一个偶圈若都是偶数,则路P上v到v的一段与边vv及v”,构成一个偶圈。证毕。例14设G是简单图,若(G)≥3,则G中各个圈长的最大公因数是1或2

5 设V ′ ⊆ V (G) ， E′ ⊆ E(G) ，今后经常用G −V ′ 表示从图 G 中删除顶点子集V ′（连同它们关联的边一起删去）所获得的子图，用G − E′ 表示从图 G 中删除边子集 E′（但不删除它们的端点）所获得的子图。特别地，对顶点 v 和边 e，常用G − v 表示G {} − v ，G − e 表示G e −{ }图 G 的一个顶点子集 E′。 5. 路和圈途径(walk)：图 G 中一个点边交替出现的序列 k k i i i i i i w v e v e "e v 0 1 1 2 = 称为图 G 的一条途径，其中 0 i v 、 k i v 分别称为途径 w 的起点和终点，w 上其余顶点称为中途点。迹(trail)：图 G 中边不重复的途径称为迹。路(path)：图 G 中顶点不重复的迹称为路。（注：简单图中的路可以完全用顶点来表示， k i i i P v v "v 0 1 = ）闭途径(closed walk)：图 G 中起点和终点相同的途径称为闭途径。闭迹(closed trail)：图 G 中边不重复的闭途径称为闭迹，也称为回路（circuit）。圈(cycle)：中途点不重复的闭迹称为圈。注：（1）途径（闭途径）、迹（闭迹）、路（圈）上所含的边的数目称为它的长度。（2）简单图 G 中长度为奇数和偶数的圈分别称为奇圈(odd cycle)和偶圈(even cycle)。（3）对任意 x, y ∈V(G)，从 x 到 y 的具有最小长度的路称为 x 到 y 的最短路（shortest path），其长度称为 x 到 y 的距离(distance)，记为d (x, y) G 。（4）简单图 G 中最短圈的长度称为图 G 的围长(girth)，最长圈的长度称为图 G 的周长 (circumference)。例 1.1.2 设 G 是一个简单图，若δ (G) ≥ 2，则 G 中必含有圈。证明：设 G 中的最长路为 k P v v "v = 0 1 。因d(v0 ) ≥ 2 ，故存在与 1 v 相异的顶点 v 与 0 v 相邻。若v ∉ P ，则得到比 P 更长的路，这与 P 的取法矛盾。因此必定v ∈ P ，从而 G 中有圈。证毕。例 1.1.3 设 G 是简单图，若δ (G) ≥ 3 ,则 G 必有偶圈。证明：设 k P v v "v = 0 1 是 G 的最长路。因为d(v0 ) ≥ 3，所以存在两个与 1 v 相异的顶点v′, v′′ 与 0 v 相邻。v′, v′′ 必都在路 P 上，否则会得到比 P 更长的路。无妨设v v , v v , (i j) ′ = i ′′ = j < 。若i, j 中有奇数，比如 i 是奇数，则路 P 上 0 v 到 i v 的一段与边 i v v0 构成一个偶圈；若i, j 都是偶数，则路 P 上 i v 到 j v 的一段与边 i v v0 及 j v v0 构成一个偶圈。证毕。例 1.1.4 设 G 是简单图，若δ (G) ≥ 3 ,则 G 中各个圈长的最大公因数是 1 或 2

6 证明：由上例知，G 中有长分别为i +1, j +1和 j − i + 2 的圈。若i +1, j +1， j − i + 2 三数有公因数m > 2，则m ji |( ) − ，于是m | 2 ，这是不可能的。因此i +1, j +1， j − i + 2 三数的公因数必不超过 2。从而各个圈长的最大公因数是 1 或 2。证毕。 6. 二部图二部图 (bipartite graph)：若图 G 的顶点集可划分为两个非空子集 X 和 Y，使得 G 的任一条边都有一个端点在 X 中，另一个端点在 Y 中，则称 G 为二部图（或偶图），记为 G＝ (X ∪Y , E) ，(X,Y ) 称为 G 的一个顶点二划分。完全二部图(complete bipartite graph)：在二部图G = (X ∪Y , E) 中，若 X 的每个顶点与 Y 的每个顶点有边连接，则称 G 为完全二部图；若| X |= m ，|Y |= n ，则记此完全二部图为 Km,n 。定理 1.1.2 一个图是二部图当且仅当它不含奇圈。证明：必要性：设 0 1 0 C v v v v = " k 是二部图G = (X ∪Y , E) 的一个圈。无妨设v0 ∈ X ，由二部图的定义知，v1 ∈Y ，v2 ∈ X ， "，一般地，v2i ∈ X ，v2i+1 ∈Y ，（i = 0,1,"）。又因v0 ∈ X ，故vk ∈Y ，因而 k 是奇数。注意到圈 C 上共有k + 1条边，因此是偶圈。充分性：设 G 不含奇圈。取u ∈V(G) ，令 X = {v ∈V(G) | d(u, v)＝odd}，Y = {v ∈V(G) | d(u, v)＝even}。任取一条边 1 2 e = v v ，欲证 1 2 v , v 分属于 X 和 Y。设 P，Q 分别是 u 到 1 2 v , v 的最短路。（1）如果 2 1 P = Q + v v 或 1 2 Q = P + v v ，则 1 2 v , v 到 u 的距离奇偶性相反， 1 2 v , v 分属于 X 和 Y。（2）否则，设u′ 是 P 与 Q 的最后一个公共顶点，因 P 的(u,u′) 段和 Q 的(u,u′) 段都是 u 到u′ 的最短路，故这两段长度相等。假如 P，Q 的奇偶性相同，则 P 的( , )1 u′ v 段和 Q 的( , ) 2 u′ v 段奇偶性相同，这两段与边 e 构成一个奇圈，与定理条件矛盾。可见 P，Q 的奇偶性不同，从而 1 2 v , v 分属于 X 和 Y。这便证明了 G 是一个二部图。证毕。例 1.1.5 判断下列图是不是二部图。 Herschel 图 Peterson 图解：Herschel 图的一个顶点二划分如下：

从数学上看,同构的两个图,其顶点间可建立一一对应,边之间也能建立一一对应,且若一图的两点间有边,则在另一图中对应的两点间有对应的边。严格的数学定义如下。定义111对两个图G=(V(G,E(G)与H=(V(H,E(H),如果存在两个一一映射: a:V(G)→(H),B:E(G)→E(H) 使得对任意e=(,v)∈E(G),都有(a(u,a(v)∈E(H)且B(e)=(a(u),a(v),则称图 G与H同构,记为G≡H 图的同构关系是一种等价关系(即满足反身性、对称性、传递性),这种等价关系将υ阶图分成若干等价类,彼此同构的图属于同一类。同一个等价类中的图有相同的结构,差别仅在于顶点和边的名称不同。由于人们关心的是图的结构,因此,通常将同构图类中的所有图看成同一个图,而不在乎它们顶点和边的名称以及它们的图示画法。在图的图示中,不给顶点和边标定名称的图称为非标定图,否则称为标定图。非标定图实际上就是一个同构图类的代表。在不致误解的情况下,我们也往往不严格区分标定图与非标定图。目前尚无简便的方法判别两个图是否同构,特别是当图的顶点数较大时,判断两个图是否同构是一件很困难的事情。两图同构,首先它们的阶必须相等,边数必须相等;其次要有相同的环边、重边及圈的状态;还应保持顶点的度,即在同构映射下相对应的顶点必须有相同的度。这些都是两图同构的必要条件,可用来判断两图不同构为判定两图同构,一般要按定义构造出两图顶点间的一一映射,然后检验它是否保持邻接关系。有时也可根据图的特点使用特殊方法。例1.1.8判断下列图是否同构 14 15 16 解:图G1和G2是同构的。事实上,定义它们顶点间的映射f,分别将顶点n,n2,n3,V4,v,Y6 映射到砌1,l3,ls,l2,l,l,显然这是G1到G2的一个一一映射,且容易验证它保持顶点间的相邻关系。图G2和G3也是同构的。事实上,定义它们顶点间的映射g,分别将顶点m,,l3,l4,u l6映射到w1,w2,w3,w4,ws,w6,显然这是G2到G3的一个一一映射,且容易验证它保持顶点间的相邻关系图G3和G4不同构,因为G4含有三角形(即子图K3),但G3不含。注:(1)G1、G2、G3的同构性还可以通过它们的二部图特性来证明。可以检验,它们都是完全二部图K3 (2)容易证明,两个图G和H同构当且仅当它们的补图G、H同构。利用这一结论也可以较简便地判定G1、G2、G3的同构性,事实上,G1、G2、G3的补图都是两个不相交的 C3(长为3的圈),因此同构。而G4的补图是C6,故G4与前三个图不同构

8 从数学上看，同构的两个图，其顶点间可建立一一对应，边之间也能建立一一对应，且若一图的两点间有边，则在另一图中对应的两点间有对应的边。严格的数学定义如下。定义 1.1.1 对两个图G = (V(G),E(G)) 与 H = (V (H),E(H))，如果存在两个一一映射： α :V(G) →V(H)， β : E(G) → E(H) ，使得对任意e = (u,v) ∈ E(G) ，都有(α(u),α(v)) ∈ E(H) 且 β (e) = (α(u),α(v))，则称图 G 与 H 同构，记为G ≅ H 。图的同构关系是一种等价关系（即满足反身性、对称性、传递性），这种等价关系将υ 阶图分成若干等价类，彼此同构的图属于同一类。同一个等价类中的图有相同的结构，差别仅在于顶点和边的名称不同。由于人们关心的是图的结构，因此，通常将同构图类中的所有图看成同一个图，而不在乎它们顶点和边的名称以及它们的图示画法。在图的图示中，不给顶点和边标定名称的图称为非标定图，否则称为标定图。非标定图实际上就是一个同构图类的代表。在不致误解的情况下，我们也往往不严格区分标定图与非标定图。目前尚无简便的方法判别两个图是否同构，特别是当图的顶点数较大时，判断两个图是否同构是一件很困难的事情。两图同构，首先它们的阶必须相等，边数必须相等；其次要有相同的环边、重边及圈的状态；还应保持顶点的度，即在同构映射下相对应的顶点必须有相同的度。这些都是两图同构的必要条件，可用来判断两图不同构。为判定两图同构，一般要按定义构造出两图顶点间的一一映射，然后检验它是否保持邻接关系。有时也可根据图的特点使用特殊方法。例 1.1.8 判断下列图是否同构解：图 G1 和 G2 是同构的。事实上，定义它们顶点间的映射 f，分别将顶点 v1, v2, v3, v4, v5, v6 映射到 u1, u3, u5, u2, u4, u6，显然这是 G1 到 G2 的一个一一映射，且容易验证它保持顶点间的相邻关系。图 G2 和 G3 也是同构的。事实上，定义它们顶点间的映射 g，分别将顶点 u1, u2, u3, u4, u5, u6 映射到 w1, w2, w3, w4, w5, w6，显然这是 G2 到 G3的一个一一映射，且容易验证它保持顶点间的相邻关系。图 G3 和 G4 不同构，因为 G4 含有三角形（即子图 K3），但 G3 不含。注：（1）G1、G2、G3 的同构性还可以通过它们的二部图特性来证明。可以检验，它们都是完全二部图 K3,3。（2）容易证明，两个图 G 和 H 同构当且仅当它们的补图G H 、同构。利用这一结论，也可以较简便地判定 G1、G2、G3 的同构性，事实上，G1、G2、G3 的补图都是两个不相交的 C3（长为 3 的圈），因此同构。而 G4 的补图是 C6，故 G4 与前三个图不同构。 G1 G2 u1 u2 u3 u5 u4 u6 w6 w5 w1 w3 w2 w4 v1 v2 v3 v4 v5 v6 x1 x2 x3 x5 x4 x6 G3 G4

9 关于图的同构有两个猜想至今尚未解决。猜想 1（Ulam 重构猜想，1929）设 G 与 H 是两个图， |V(G)| = |V(H)|, V(G) = {u1, u2, ⋅⋅⋅, un}，V(H)={v1, v2, ⋅⋅⋅, vn}。若对∀ ∈i n {1, 2, , } " ，都有Gu Hv −≅ − i i ，则G H≅ 。其中G v − i 表示将 vi 以及与 vi 关联的边都从 G 中删除后所得之图， H v − i 类似。猜想 2 设 G 与 H 都是至少有四条边的图，若存在一一映射ϕ : () ( ) EG EH → ，使得对 ∀ ∈e EG( ) ，都有GeH e −≅ −ϕ( ) ，则G H≅ 。有关图的重构问题的更多内容可参看: [1] C.St.J.A. Nash-Williams, The reconstruction problem, in Selected Topics in Graph Theory (L. W. Beineke and R.J. Wilson eds.), Academic Press, London, (1978) 205-236. [2]W.T. Tutte, Graph Theory, Cambridge University Press, (2001) 115-124.(影印版：图论，机械工业出版社，2004). §1.2 最短路问题一、赋权图给图 G 的每条边 e 赋以一个实数 w(e)，称为边 e 的权。每条边都赋有权的图称为赋权图。权在不同的问题中会有不同的含义。例如交通网络中，权可能表示运费、里程或道路的造价等。设 H 是赋权图 G 的一个子图，H 的权定义为W (H) ＝ ∑∈ ( ) ( ) e E H w e ，特别地，对 G 中一条路 P，其权为W (P) ＝ ∑∈ ( ) ( ) e E P w e 。二、最短路问题最短路问题：给定赋权图 G 及 G 中两点 u, v，求 u 到 v 的具有最小权的路（称为 u 到 v 的最短路）。注：赋权图中路的权也称为路的长，最短(u,v)路的长也称为 u,v 间的距离，记为 d(u,v)。最短路问题是一个优化问题，属于网络优化和组合优化的范畴。对这种优化问题的解答一般是一个算法。最短路问题有很多算法，其中最基本的一个是 Dijkstra 算法。三、Dijkstra 算法 1. 算法思想设赋权图 G 中所有边都具有非负权，Dijkstra 算法的目标是求出 G 中某个指定顶点 0 v 到其它所有点的最短路。它依据的基本原理是：若路 P vv v v = 01 1 " k k − 是从 0 v 到 k v 的最短路，则 P vv v 01 1 k− ′ = " 必是从 0 v 到 k 1 v − 的最短路。基于这一原理，算法由近及远地逐次求出 0 v 到其它各点的最短路

10 下面通过例子说明具体做法。图 1.1 （1）令 0 S v = { }， S VS = \ ，求 0 v 到 S 中最近点的最短路。在当前的例子中，从 v0v1、 v0v2、v0v3 中选一条最短的，结果获得 v0 到 v1 的最短路 v0v1。（2）令 1 SS v : {} = ∪ ，S VS : \ = ，求 0 v 到 S 中最近点的最短路。这里“最近”是指 0 v 到 S 的直接连边、以及从 0 v 出发的已有最短路上的点（即 S 中除 0 v 外的点，当前只有 1 v ）通过最短路再添加上向 S 的连边所形成的路中最短的。即选取 S 中一点v 使得距离 0 0 , ( , ) min { ( , ) ( )} i i i v Sv S d v v d v v w vv ∈ ∈ = + 。 (*) 在当前的例子中，从 v0v2、v0v3、v0v1v2、v0v1v3 中选一条最短的，结果获得 v0 到 v3 的最短路 v0v1v3。（3）令 3 SS v : {} = ∪ ， S VS : \ = ，求 0 v 到 S 中最近点的最短路。即选取 S 中一点v 使得 0 0 , ( , ) min { ( , ) ( )} i i i v Sv S d v v d v v w vv ∈ ∈ = + 。当前应从 v0v2、v0v1v2、v0v1v3v2、v0v1v3v4中选一条最短的，结果获得 v0 到 v4 的最短路 v0v1v3v4。（4）令 4 SS v : {} = ∪ ， S VS : \ = ，求 0 v 到 S 中最近点的最短路。即选取 S 中一点v 使得 0 0 , ( , ) min { ( , ) ( )} i i i v Sv S d v v d v v w vv ∈ ∈ = + 。当前应从 v0v2、v0v1v2、v0v1v3v2、v0v1v3v4 v2 中选一条最短的，结果获得 v0 到 v2 的最短路 v0v1v2 （或 v0v1v3v4 v2）。一般地，若 0 1 {,, , }k S vv v = " 以及相应的最短路已找到，则可用(*)式来选取v ，获得 0 v 到v 的最短路。 2．算法实现－标号法在上述算法的过程中，每轮循环求 0 dv v ( ,) 时，都要对所有的点 i v S ∈ 计算 0 (,) ( ) i i d v v w vv + 且比较出一个最小的值，因而在算法循环过程中需要大量重复的路长计算和比较。为了避免这种重复计算，Dijkstra 算法采用标号方法来实现：算法执行中，给每个点 v 都附一个标号 l(v)，表示当前已经算出的从 v0 到该点的最短路的长 0 dv v ( ,) 。算法每轮循环都考虑修改点 v 的标号，如果通过此前刚刚进入 S 集合的点 vi 到该点的连边不能获得更短的路，则该点保持原有标号 l(v)不变；否则，修改该点标号为 l(v): = l(vi) + w(viv)，当前 v0 到 v 的最短路应由 v0到 vi 的最短路及边 viv 构成。 1 v0 v1 v2 v3 v4 5 8 1 2 2 6 4

中科院研究生院专业基础课：《图论与网络流理论》第一章 图的基本概念 Graph Theory and Network Flow Theory（高随祥）

中科院研究生院专业基础课：《图论与网络流理论》第一章图的基本概念 Graph Theory and Network Flow Theory（高随祥）