证明:由上例知,G中有长分别为i+1,j+1和j-i+2的圈。若i+1,j+1,j-i+2三 数有公因数m>2,则m|(j-1),于是m|2,这是不可能的。因此i+1,j+1,j-i+2 三数的公因数必不超过2。从而各个圈长的最大公因数是1或2。证毕 6.二部图 二部图( bipartite graph):若图G的顶点集可划分为两个非空子集X和Y,使得G的任一条 边都有一个端点在X中,另一个端点在Y中,则称G为二部图(或偶图),记为G= (XUY,E),(X,Y)称为G的一个顶点二划分。 完全二部图( (complete bipartite graph):在二部图G=(X∪Y,E)中,若X的每个顶点与Y 的每个顶点有边连接,则称G为完全二部图;若XFm,|YFn,则记此完全二部图为 K 定理112一个图是二部图当且仅当它不含奇圖 证明:必要性:设C=Vv1…vv是二部图G=(XUY,E)的一个圈。无妨设vo∈X, 由二部图的定义知,v1∈Y,v2∈X,…,一般地,v2;∈X,v2a1∈Y,(i=0,1,…)。 又因v∈X,故v∈Y,因而k是奇数。注意到圈C上共有k+1条边,因此是偶圈。 充分性:设G不含奇圈。取u∈(G),令 X={v∈V(G)|d(u,v)=odl},Y={v∈(G)|d(u,)=even}。 任取一条边e=v1v2,欲证v,V2分属于X和Y。设P,Q分别是a到v1,V2的最短路 (1)如果P=Q+v2V1或Q=P+vV2,则v1,V2到a的距离奇偶性相反,v1,v2分属于X 和Y (2)否则,设u'是P与Q的最后一个公共顶点,因P的(,u)段和Q的(u,u)段都是u 到’的最短路,故这两段长度相等 假如P,Q的奇偶性相同,则P的(2v1)段和Q的(,v2)段奇偶性相同,这两段与边 e构成一个奇圈,与定理条件矛盾。可见P,Q的奇偶性不同,从而v1,v2分属于X和y 这便证明了G是一个二部图。证毕 例11.5判断下列图是不是二部图 Herschel图 Peterson图 解: Herschel图的一个顶点二划分如下
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 图的一个顶点二划分如下:
可见 Herschel图是一个二部图。 Peterson图中含有奇圈,因此不是二部图 7.连通性 图中两点的连通:如果在图G中u,v两点间有路相通,则称顶点u,v在图G中连通。 连通图( connected graph):若图G中任二顶点都连通,则称图G是连通图 图的连通分支( connected branch, component):若图G的顶点集IG可划分为若干非空子集 V1,H2,…V,使得两顶点属于同一子集当且仅当它们在G中连通,则称每个子图G]为 图G的一个连通分支(i=1,2…,O)。 注:(1)图G的连通分支是G的一个极大连通子图。 (2)图G连通当且仅当=1。 例1.1.6设有2n个电话交换台,每个台与至少n个台有直通线路,则该交换系统中任二台均 可实现通话。 证明:构造图G如下:以交换台作为顶点,两顶点间连边当且仅当对应的两台间有直通线 路。问题化为:已知图G有2n个顶点,且δ(G)≥n,求证G连通。 事实上,假如G不连通,则至少有一个连通分支的顶点数不超过n。在此连通分支中, 顶点的度至多是n-1。这与(G)≥n矛盾。证毕。 例1.1.7若图中只有两个奇度顶点,则它们必连通。 证明:用反证法。假如u与v不连通,则它们必分属于不同的连通分支。将每个分支看成一 个图时,其中只有一个奇度顶点。这与推论1.1.1矛盾。证毕。 图的同构 我们已经知道,同一个图可以有不同形状的图示。反过来,两个不同的图也可以有形状 相同的图示。比如 易见G1和G2的顶点及边之间都一一对应,且连接关系完全相同,只是顶点和边的名称 不同而已。这样的两个图称为是同构的( isomorphic)
7 可见 Herschel 图是一个二部图。 Peterson 图中含有奇圈,因此不是二部图。 7. 连通性 图中两点的连通:如果在图 G 中 u,v 两点间有路相通,则称顶点 u,v 在图 G 中连通。 连通图(connected graph):若图 G 中任二顶点都连通,则称图 G 是连通图。 图的连通分支(connected branch, component):若图 G 的顶点集 V(G)可划分为若干非空子集 V V Vω , , , 1 2 " ,使得两顶点属于同一子集当且仅当它们在 G 中连通,则称每个子图 [ ] G Vi 为 图 G 的一个连通分支(i = 1,2,",ω )。 注:(1)图 G 的连通分支是 G 的一个极大连通子图。 (2)图 G 连通当且仅当ω=1。 例 1.1.6 设有 2n 个电话交换台,每个台与至少 n 个台有直通线路,则该交换系统中任二台均 可实现通话。 证明:构造图 G 如下:以交换台作为顶点,两顶点间连边当且仅当对应的两台间有直通线 路。问题化为:已知图 G 有 2n 个顶点,且δ (G) ≥ n ,求证 G 连通。 事实上,假如 G 不连通,则至少有一个连通分支的顶点数不超过 n。在此连通分支中, 顶点的度至多是n −1。这与δ (G) ≥ n 矛盾。证毕。 例 1.1.7 若图中只有两个奇度顶点,则它们必连通。 证明:用反证法。假如 u 与 v 不连通,则它们必分属于不同的连通分支。将每个分支看成一 个图时,其中只有一个奇度顶点。这与推论 1.1.1 矛盾。证毕。 8. 图的同构 我们已经知道,同一个图可以有不同形状的图示。反过来,两个不同的图也可以有形状 相同的图示。比如: 易见G1 和G2 的顶点及边之间都一一对应,且连接关系完全相同,只是顶点和边的名称 不同而已。这样的两个图称为是同构的(isomorphic)。 v1 v2 v3 v4 e1 e3 e2 e4 e5 e6 a4 u1 a1 a2 a3 u3 u2 u4 a6 a5 u1 u2 u3 u4 a1 a3 a2 a4 a5 a6 G1 G2 x y y y y x x x x y y
从数学上看,同构的两个图,其顶点间可建立一一对应,边之间也能建立一一对应,且 若一图的两点间有边,则在另一图中对应的两点间有对应的边。严格的数学定义如下。 定义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
关于图的同构有两个猜想至今尚未解决 猜想1(Uam重构猜想,1929)设G与H是两个图 V(G=Ⅳ(H),V(G)={at,2,…,an},VH={v,v2,…,vn}。 若对ⅵi∈{1,2,…,m},都有G-l1=H-v,则G≡H。其中G-v表示将v以及与v 关联的边都从G中删除后所得之图,H-v类似。 猜想2设G与H都是至少有四条边的图,若存在一一映射q:E(G)→E(H),使得对 ve∈E(G),都有G-e=H-g(e),则G≡H。 有关图的重构问题的更多内容可参看 [1]CSt 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]wT.Tute, Graph Theory, Cambridge University Press,(2001)115-124(影印版:图论,机械 工业出版社,2004) §12最短路问题 、赋权图 给图G的每条边e赋以一个实数w(e),称为边e的权。每条边都赋有权的图称为赋权 图 权在不同的问题中会有不同的含义。例如交通网络中,权可能表示运费、里程或道路的 造价等。 设H是赋权图G的一个子图,H的权定义为W(H)=∑w(e),特别地,对G中 eEE(H) 条路P,其权为W(P)=∑w(e) 、最短路问题 最短路问题:给定赋权图G及G中两点lV,求u到v的具有最小权的路(称为u到 的最短路)。 注:赋权图中路的权也称为路的长,最短(u,)路的长也称为uy间的距离,记为d(ly)。 最短路问题是一个优化问题,属于网络优化和组合优化的范畴。对这种优化问题的解答 般是一个算法。最短路问题有很多算法,其中最基本的一个是 Dijkstra算法。 、 Dijkstra算法 1.算法思想 设赋权图G中所有边都具有非负权, Dijkstra算法的目标是求出G中某个指定顶点v到 其它所有点的最短路。它依据的基本原理是:若路P=vv1…V-1v是从v到v的最短路 则P'=vav1…V-1必是从v到v-1的最短路。基于这一原理,算法由近及远地逐次求出v 到其它各点的最短路
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 到其它各点的最短路
下面通过例子说明具体做法。 图1.1 (1)令S={},S=\S,求到S中最近点的最短路。在当前的例子中,从won、 v0η2、w0吟3中选一条最短的,结果获得到v的最短路vov1 (2)令S=S∪{v1},S=V\S,求v到S中最近点的最短路。这里“最近”是指v到S 的直接连边、以及从v出发的己有最短路上的点(即S中除v外的点,当前只有v)通过 最短路再添加上向S的连边所形成的路中最短的。即选取S中一点ν使得距离 d(vo, v)=min(d(vo, v)+w(vv)) 在当前的例子中,从v吟2、wn、1n2、w0v1v3中选一条最短的,结果获得v到v3的最短路 1o1113o (3)令S=SU{v3},S=\S,求v到S中最近点的最短路。即选取S中一点v使得 d(vo, v)=min_d(vo, v)+w(vv)i 当前应从wη2、wv、wην3昑2、wv13γ4中选一条最短的,结果获得w到γ4的最短路vovv3v4 (4)令S=SU{v},S=V\S,求v到S中最近点的最短路。即选取S中一点v使得 d(vo, v)=min_(d(vo, v )+w(v)) 当前应从υ、wov1n2、w1ν3n2、woη34中选一条最短的,结果获得v到γ的最短路wvn2 (或v13v42) 一般地,若S={v,V,…,V}以及相应的最短路已找到,则可用(*)式来选取v,获得v 到v的最短路。 2.算法实现一标号法 在上述算法的过程中,每轮循环求d(Vo,ν)时,都要对所有的点v∈S计算 d(vo,v)+w(vv)且比较出一个最小的值,因而在算法循环过程中需要大量重复的路长计 算和比较。为了避免这种重复计算, Dijkstra算法采用标号方法来实现:算法执行中,给每 个点v都附一个标号/v),表示当前己经算出的从v到该点的最短路的长d(v,v)。算法每 轮循环都考虑修改点ν的标号,如果通过此前刚刚进入S集合的点ν到该点的连边不能获得 更短的路,则该点保持原有标号)不变:否则,修改该点标号为(v)=(v)+(v),当前 0到ν的最短路应由到v1的最短路及边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