《图论及其应用》主要知识点讲义讲解

图和子图 图和简单图 图G=(VE),其中 }V--项顶点集 V-顶点数 E={e1,e2……,e} E--边数 例。左图中 V={a,b,,f}, E=ip 注意,左图仅仅是图G的几何实现(代表),它们 有无穷多个。真正的图G是上面所给出式子,它与顶点的位 置、边的形状等无关。不过今后对两者将经常不加以区别 称边ad与顶点a(及d)相关联。也称顶点b及f) 与边bf相关联 称顶点a与e相邻。称有公共端点的一些边彼此相邻, 例如p与af f 环(loop, selfloop):如边l 棱(link):如边aea G=(VE 重边:如边p及边q 简单图:( simple graph)无环,无重边 平凡图:仅有一个顶点的图(可有多条环 条边的端点:它的两个顶点 记号:(G)=|(G E(G)=|E(G)。 习题 1.1.1若G为简单图,则E≤ 1.1.2n(≥4)个人中,若每4人中一定有一人认识其他3人,则一定有一人认识其他n-1人 同构 在下图中, 图G恒等于图H,记为G=H台VG=V(H,E(G)=E(H)。 图G同构于图FVG)与V(F),E(G)与E(F)之间各存在一一对应关系,且这二对应关系 保持关联关系。 记为G≡F 注往往将同构慨念引伸到非标号图中,以表达两个图在结构上是否相同。 d d x d w GV,E) HV,E) FV,E)

1 图和子图 图和简单图 图 G = (V, E)， 其中 V = {} V ---顶点集，  ---顶点数 E = { e e e 1 2 , ,......,  } E ---边集，  ---边数 例。 左图中， V={a, b,......,f}, E={p,q, ae, af,......,ce, cf} 注意， 左图仅仅是图 G 的几何实现（代表）， 它们 有无穷多个。真正的 图 G 是上面所给出式子，它与顶点的位 置、边的形状等无关。不过今后对两者将经常不加以区别。 称 边 ad 与顶点 a (及d) 相关联。也称 顶点 b(及 f) 与边 bf 相关联。 称顶点 a 与 e 相邻。称有公共端点的一些边彼此相邻， 例如 p 与 af 。 环（loop，selfloop）：如边 l。 棱（link）：如边 ae。 重边：如边 p 及边 q。 简单图：（simple graph）无环，无重边 平凡图：仅有一个顶点的图（可有多条环）。 一条边的端点：它的两个顶点。 记号： (G) = V(G), (G) = E(G).。 习题 1.1.1 若 G 为简单图，则          2 。 1.1.2 n (  4 )个人中，若每 4 人中一定有一人认识其他 3 人，则一定有一 人认识其他 n-1 人。 同构 在下图中， 图 G 恒等于图 H , 记为 G = H  VG)=V(H), E(G)=E(H)。 图 G 同构于图 F  V(G)与 V(F), E(G)与 E(F)之间 各 存在一一对应关系，且这二对应关系 保持关联关系。 记为 G  F。 注 往往将同构慨念引伸到非标号图中，以表达两个图在结构上是否相同。 d e f G=(V, E) p q a b c r a y z x w b c d e G=(V, E) x w b c d e a y z H=(V’, E’) x’ d’ w’ a’ b’ c’ y’ e’ z’ F=(V’’, E’’)

注判定两个图是否同构是 NP-hard问题 完全图 complete graph)Kn 空图( empty g.)台E=必 V(sV为独立集V中任二顶点都互不相邻 二部图(偶图, bipartite g.)G=(X,Y;E)台存在VG)的一个2-划分(X,Y),使Ⅹ与Y都 是独立集 完全二部图Km,n台二部图G=(X,Y),其中X和Y之间的每对顶点都相邻,且X=m, K K4 Ke 部图 类似地可定义,完全三部图(例如Km,np),完全n-部图等 例。用标号法判定二部图。 习题 1.2.1G≡H当wG)=vH),(G)=ε(H)。并证明其逆命题不成立 1.2.2证明下面两个图不同构: 12.3证明下面两个图是同构的: 124证明两个简单图G和H 同构 存在一一映射f:V(G) ¤→V(H),使得u∈E(G)当且仅当 fu)f(v)∈E(H)。 1.2.5证明:(a)(Kmn)=mn; (b).对简单二部图有ε≤v2/4 1.2.6记Tmn为这样的一个完全m-部图:其顶点数为n,每个部分的顶点数为nm或{nm} 证 (a). E(Tmn)= 2/+(m-1 其中k=[mm (b)’.对任意的n顶点完全m-部图G,一定有c(G)≤(Tm),且仅当GTm时等式才成立 127所谓k方体是这样的图:其顶点是由0与1组成的有序k元组,其二顶点相邻当且仅当它 们恰有一个坐标不同。证明k-方体有个顶点,k*2k1条边,且是一偶图 12.8简单图G的补图G是指和G有相同顶点集V的一个简单图,在G中两个顶点相邻当且 仅当它们在G不相邻。 (a).画出Kn和Kmn (b)如果G≡G则称简单图G为自补的。证明:若G是自补的,则v≡0,1(mod4)

2 注 判定两个图是否同构是 NP-hard 问题。 完全图(complete graph) Kn 空图（empty g.）  E =  。 V’ (  V) 为独立集  V’中任二顶点都互不相邻。 二部图（偶图，bipartite g.） G = (X, Y ; E)  存在 V(G) 的一个 2-划分 (X, Y), 使 X 与 Y 都 是独立集。 完全二部图 Km,n  二部图G = (X, Y)，其中X和Y之间的每对顶点都相邻，且 X = m, Y = n 。 类似地可定义，完全三部图（例如 Km,n,p），完全 n-部 图等。 例。用标号法判定二部图。 习题 1.2.1 G  H  (G) = (H) , (G) = (H) 。 并证明其逆命题不成立。 1..2.2 证明下面两个图不同构： 1.2.3 证明下面两个图是同构的： 1.2.4 证明两个简单图 G 和 H 同构  存在一一映射 f : V(G) →V(H) ，使得 uv  E(G)当且仅当 f(u)f(v)  E(H) 。 1.2.5 证明：(a).(Km,n ) = mn ; (b). 对简单二部图有    2 /4 . 1.2.6 记 Tm,n 为这样的一个完全 m-部图：其顶点数为 n，每个部分的顶点数为[n/m]或{n/m}个。 证明： (a). (Tm,n) = n k m  − k      + −  +      2 1 1 2 ( ) 其中 k =[n/m] . (b)* . 对任意的 n 顶点完全 m-部图 G，一定有 (G) (Tm,n)，且仅当 G Tm,n 时等式才成立。 1.2.7 所谓 k-方体是这样的图：其顶点是由 0 与 1 组成的有序 k-元组，其二顶点相邻当且仅当它 们恰有一个坐标不同。证明 k-方体有个顶点，k*2 k-1 条边，且是一偶图。 1.2.8 简单图 G 的补图 Gc 是指和 G 有相同顶点集 V 的一个简单图，在 Gc中两个顶点相邻当且 仅当它们在 G 不相邻。 (a). 画出 Kc n 和 Kc m,n。 (b). 如果 G  G c则称简单图 G 为自补的。证明：若 G 是自补的，则   0, 1 (mod 4) 二部图 K1 K2 K3 K4 K5 K3,3 K1,5 K2,2,2

关联矩阵M(G)与邻接矩阵A(G) M(G)=[;, Ive A(G=Laiv 其中m.;=顶点v与边e;的关联次数=0,1,2. a,;=连接顶点v;与v的边数。 例 0 00|v M(G l 1001 000 0 V4 子图 子图( subgraph) HCG V(HsV(G),E(H≌E(G)。 真子图HcG。 母图( super graph) 生成子图( spanning subg)eHG且v(H)=V(G) 生成母图 基础简单图( underlying simple g)。 导出子图( induced subg)GV,(非空vV) 台以V为顶点集,以G中两端都在V上的边全体为边集构成的G的子图。 边导出子图G[E] 非空EE 以E'为边集,以E中所有边的端点为顶点集的的子图。 例 EuwxyiI GluwxlI 以上两种子图,其实,对应于取子图的两种基本运算。下面是取子图的另两种基本运算: G-V去掉及与Ⅴ'相关联的一切边所得的剩余子图

3 关联矩阵 M(G)与邻接矩阵 A(G) M(G)=[mi,j] , A(G)=[ai,j] , 其中 mi,j = 顶点 vi 与边 ej 的关联次数= 0, 1, 2. ai,j = 连接顶点 vi 与 vj 的边数 。 例。 e e e e e e e M G v v v v 1 2 3 4 5 6 7 1 2 3 4 1 1 0 0 1 0 1 1 1 1 0 0 0 0 0 0 1 1 0 0 1 0 0 0 1 1 2 0 ( ) =             v v v v A G v v v v 1 2 3 4 1 2 3 4 0 2 1 1 2 0 1 0 1 1 0 1 1 0 1 1 ( ) =             子图 子图(subgraph) H  G  V(H)  V(G) , E(H)  E(G) 。 真子图 H  G。 母图（super graph）。 生成子图（spanning subg.）  H  G 且 V(H) = V(G) 。 生成母图。 基础简单图 （underlying simple g.）。 导出子图（induced subg.）G[V’], (非空 V’ V )  以 V’为顶点集，以 G 中两端都在 V’上的边全体为边集构成的 G 的子图。 边导出子图 G[E’] 非空 E’  E  以 E’为边集，以 E’中所有边的端点为顶点集的的子图。 例。 以上两种子图，其实，对应于取子图的两种基本运算。下面是取子图的另两种基本运算： G - V’  去掉 V’及与 V’相关联的一切边所得的剩余子图。 e1 e2 e3 e4 e5 e6 v1 v2 v4 v3 G=(V, E) e7 G[{f, c]} G[{c, d, e}] e a b c d f g h G=(V, E) x w v y u G[{u,w,x,y}] G[{u,w,x}]

台即GVVv G-E’从中去掉E后所得的生成子图 例。G-{b,d,g}, (=GE\b, d, gil G-b, c,d, gi, (≠G[E\{b,c,d,g G-a,e, f, g) (≠G[E\{a,e,f,g} 注意G\E]与G-E虽有相同的边集,但两者不一定相等:后者一定是生成子图,而前者则 不然。 上述四种运算是最基本取子图运算,今后老要遇到,一定要认真掌握好。关于子图的一些定义还有 G+E’往G上加新边集E’所得的(G的母)图 为简单计,今后将 G±{e}简计为G±e {v}简计为 设G1,Gi2cG,称Gi与G2为 不相交的( disjiont)sGi)∩(G2)=② (∴E(G1)∩E(G2)=) 边不相交(edge- disjiont)分E(G1)∩E(G2)= (但这时G1与G2仍可能为相交的)。 并图GUG2,当不相交时可简记为G1+G2 交图G∩G2 习题 141证明:完全图的每个导出子图是完全图:偶图的每个导出子图是偶图 42设G为一完全图,1<n<v1。证明:若v≥4,且G中每个n顶点的导出子图均有相同 的边数,则G≡K或K。 顶点的度 顶点v的度d(v)=G中与顶点v相关联边数。(每一环记为2) 最大、最小度△,δ。(△(G),6(G) 定理11( hand shaking lemma)任一图中 ∑d(v)=2 系1.1任一图中,度为奇数顶点的个数为偶数 例。任一多面体中,边数为奇数的外表面的数目为偶数 证明。作一图,使其顶点对应于多面体的面,并使其中二顶点相邻当且仅当对应的两个面相 邻 k-正则图(k- regular g)edv)=k,v∈V 习题 → 0正则图 1-正则图2-图 3正贝图 1.5 证明:δ≤2E/v≤Δ。 1.52若k-正则偶图(k>0)的2-划分为(X,Y),则 153在人数>1的人群中,总有二人在该人群中有相同的朋友数。 1.54设V(G)={v,V2,…},则称(dv1),dv2),,d(yy)为G的度序列。证明:非负

4  即 G[V \ V’] G - E’  从中去掉 E’ 后所得的生成子图 例。G - {b, d, g}, ( = G[E \ {b, d, g}] ) G - {b, c, d, g}, (  G[E \ {b, c, d, g}] ) G - {a, e, f, g}. (  G[E \ {a, e, f, g}] ) 注意 G[E \ E’] 与 G - E’ 虽有相同的边集，但两者不一定相等 ： 后者一定是生成子图，而前者则 不然。 上述四种运算是最基本取子图运算，今后老要遇到，一定要认真掌握好。关于子图的一些定义还有： G + E’  往 G 上加新边集 E’ 所得的（G 的母）图。 为简单计，今后将 G  {e} 简计为 G  e ； G - {v} 简计为 G - v 。 设 G1, G2  G ，称 G1 与 G2 为 不相交的（disjiont）  V(G1)  V(G2) =  (  E(G1)  E(G2) =  ) 边不相交 （edge-distjiont） E(G1)  E(G2 ) =  。 ( 但这时 G1 与 G2 仍可能为相交的）。 并图 G1G2 , 当不相交时可简记为 G1+G2. 交图 G1G2 . 习题 1.4.1 证明：完全图的每个导出子图是完全图；偶图的每个导出子图是偶图。 1.4.2 设 G 为一 完全图，1 n  -1。证明：若   4，且 G 中每个 n 顶点的导出子图均有相同 的边数，则 G  K或 Kc  。 顶点的度 顶点 v 的 度 dG(v) = G 中与顶点 v 相关联边数。 （每一环记为 2） 最大、最小度 ， 。 （(G) , (G) ) 定理 1.1 (hand shaking lemma) 任一图中， d v v V ( )   = 2 . 系 1.1 任一 图中，度为奇数顶点的个数为偶数。 例。任一多面体中，边数为奇数的外表面的数目为偶数。 证明。作一图，使其顶点对应于多面体的面，并使其中二顶点相邻当且仅当对应的两个面相 邻。......  k-正则图 （k-regular g.)  d(v) = k, v  V . 习题 1.5.1 证明：  2/   。 1.5.2 若 k-正则偶图(k > 0)的 2-划分为 (X, Y),则 X = Y。 1.5.3 在人数 >1 的人群中，总有二人在该人群中有相同的朋友数。 1.5.4 设 V(G) = { v v v 1 2 , ,......,  }，则称 ( d(v1), d(v2), ...... , d(v) ) 为 G 的度序列。证明：非负 3-正则图 0-正则图 1-正则图 2-正则图

整数序列(d,d,dn)为某一图的度序列∑d1是偶数 1.55证明:任一无环图G都包含一偶生成子图H,使得dn(V)≥dkv)/2对所有v∈V成立 1.56设平面上有n个点,其中任二点间的距离≥1,证明:最多有3n对点的 距离=1。 路和连通性 途径(wa|k) 例如(u,x)-途径 W= ueyfvgyhwbvgydxdydx(有限非空序列) uyvywvyxyx(简写法一当不引起混淆时) 起点( origin)u。 终点( terminus)x 内部顶点( internal vertex)y,v,w,x。 注意,中间出现的x也叫内部顶点。) 长兮边数(重复计算)。 节(段, sect i on)。例如W的(y,w)-节=yw b 逆途径),WW(两条途径W与W相衔接 迹(trai)分边各不相同的途径。例如,ywyx。 路(path)顶点各不相同的途径。(可当作一个图或子 图)。例如,ywx。 d(u,v)=u与之间最短路的长 例。(命题)G中存在(u,ⅵ)-途径G中存在(u,)-路。 G中顶点u与v为连通的( connected) G中存在(u,)-路 (G中存在(u,)-途径。) V上的连通性是V上的等价关系,它将V划分为(等 图 价类) 使每个V中的任二顶点u及都连通(即存在(u,v)-路)。称每个 G[V] 为G的一个分支( component);称o(G)为G的分支数。 G为连通图o(G)=1 G中任两点间都有一条路相连。 为非连通图o(G)>1。 记号对任一非空scV,令S=Ⅵs,记(称为边割) [s,S]=G中一端在S中,另一端在S中的一切边的集合。 例。(命题)G连通对任ScV都有[S,S]≠② 例。(命题)简单图G中,δ≥k→G中有长≥k的路。 习题 1.6.1证明:G中长k为的(,v)-途径的数目,就是A中的(1,j元素。 1.6.2证明:对简单图G有, 2/→G连通

5 整数序列 ( d1 ,d 2, ......, d n) 为某一图的度序列  di i n =  1 是偶数。 1.5.5 证明：任一 无环图 G 都包含一 偶生成子图 H，使得 dH(v)  dG(v)/2 对所有 v  V 成立。 1.5.6* 设平面上有 n 个点，其中任二点间的距离  1，证明：最多有 3n 对点的 距离 = 1 。 路和连通性 途径 （walk) 例如 （u，x）-途径 W = ueyfvgyhwbvgydxdydx (有限非空序列） = uyvywvyxyx (简写法---当不引起混淆时） 起点（origin ） u 。 终点（terminus） x。 内部顶点（internal vertex） y, v, w, x。 （注意，中间出现的 x 也叫内部顶点。） 长  边数（重复计算）。 节（段，section）。 例如 W 的(y, w)-节=yvw 。 W - 1 （逆途径）, WW’（两条途径 W 与 W’相衔接）。 迹( trail)  边各不相同的途径。 例如，yvwyx 。 路 (path)  顶点各不相同的途径。（可当作一个图或子 图)。例如， yvwx 。 d(u, v) = u 与 v 之间最短路的长。 例。（命题）G 中存在(u, v)-途径  G 中存在(u, v)-路。 G 中顶点 u 与 v 为连通的(connected)  G 中存在(u, v)-路 (  G 中存在(u, v)-途径。) V 上的连通性是 V 上的等价关系，它将 V 划分为（等 价类）： V1,......,V 使每个 Vi 中的任二顶点 u 及 v 都连通（即存在(u, v)-路）。 称每个 G[Vi] i=1,2,...... 为 G 的一个分支（component）; 称(G）为 G 的分支数。 G 为连通图  (G) = 1  G 中任两点间都有一 条路相连。 G 为非连通图  (G)  1。 记号 对任 一非空 SV ，令 S = V\S, 记（称为边割） [S, S ] = G 中 一 端在 S 中，另一 端在 S 中 的一切边的集合。 例。（命题）G 连通  对任 S  V 都有 [S, S ]   例。（命题） 简单图 G 中，   k  G 中有 长  k 的路。 习题 1.6.1 证明：G 中长 k 为的(vi ,vj )-途径的数目, 就是 A k 中的(I, j)元素。 1.6.2 证明：对简单图 G 有，     −      1 2  G 连通。 u v y x w e a b d h c f g 图 G