《图论及其应用》主要知识点讲义讲解.doc_大学文库

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-正则图

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

6 对于 > 1，试给出   =  −      1 2 的不连通简单图。 1.6.3 简单图 G 中，  > [/2] - 1  G 连通。当是偶数时，试给出一个不连通的([/2]-1) 正则简单图。 1.6.4 G 不连通  G c 连通。 1.6.5 对任意图 G 的任一边 e，有 (G) (G-e)  (G) +1 。 1.6.6 G 连通，且 d(v)=偶数，  v V  (G-v) d(v)/2,  v V. 1.6.7 连通图中，任二最长路必有公共顶点。 1.6.8 对任一图的任三个顶点 u, v, w 都有 d(u, v)+d(v, w)  d(u, w)。 1.6.9 任一简单图非完全图中，一定有三个顶点 u, v, w，使得 uv, vw E 而 uw E。圈闭途径（closed walk)  起点=终点且长  0 的途径。闭迹 (closed trail) 边各不相同的闭途径。圈（cycle） 顶点各不相同的闭迹。（可当作一图或子图。）例。闭途径： uyvyu ; uywxywvu ； uyuyu。闭迹：uyxwyvu。圈： yfvgy ; uywvu。 k-圈（k-cycle） 长为 k 的圈。例。1-圈（即一条环）， 2-圈(由重边组成），3-圈（又称三角形）。奇圈 (odd cycle)。偶圈 (even cycle)。定理 1.2 G 为二部图  G 不含奇圈。证明：：设 G 的 2-划分为（X, Y），由 G 的定义，G 的任一圈中，X 和 Y 的顶点一定交错出现，从而其长必为偶数。 ：不妨设 G 为连通的。任取一顶点 u,令 X = { xV  d(u, x) = 偶数 }, Y = { yV  d(u, y) = 奇数}。由于，易见，(X, Y)为 V 的 2-划分，只要再证 X 和 Y 都是 G 的独立集（即 X（或 Y）中任二顶点 v，w 都不相邻）即可：令 P 与 Q 分别为最短(u, v)-路与最短(u, w)-路。设 u’为 P 与 Q 的最后一个公共顶点；而 P’与 Q’分别为 P 的(u’, v)-节与 Q 的(u’, w)-节。则 P’与 Q’只有一公共顶点。又，由于 P 与 Q 的(u, u’)-节的长相等， P’与 Q’的长有相同的奇偶性，因此 v 与 w 不能相邻，不然， v( P’)-1 Q’wv 将是一奇圈，矛盾。 例。（命题）图 G 中   2  G 中含圈。例。（命题）简单图 G，  2  G 含长   +1 的圈。例。（命题）任一图中 (a).     含圈。 (b)*.    + 4  含二条边不重的圈。 u v y x w e a b d h c f g P Q u P’ Q’ u’ v w

9 定理 2.2 G 是树   =  - 1。证明：对  进行归纳。当  = 1 时，G = K 1 ，成立。假设定理对小于 个顶点的树成立，而 G 为  个顶点的树。任取 G 的一边 uv 。它是 G 中的一条路，由定理 2.1 知， G - uv 不连通，且它恰有二分支（习题 1.6.5），设为 G1 与 G2 。它们都是连通无圈图，因此是树。又，它们的顶点数都小于  。由归纳假设知 (G I ) = (G I )- 1 I= 1,2 . 故， (G) = (G 1 ) + (G 2 ) + 1 = (G 1 ) + (G 2 ) - 1 = (G) - 1 。  推论 2.2 每棵非平凡树至少有两个度为 1 的顶点。证明：由于 G 为非平凡连通图， d(v)  1 ,  v  V 。再由定理 1.1 及 2.2 知， d v v V ( )   = 2 = 2 − 2 ，由此知推论成立。例。（命题）恰只包含二度为一顶点的树是路。习题 2.1.1 证明：非平凡树中，任一最长路的起点和终点均是度为 1 的顶点。再由此去证明推论 2.2。 2.1.2 当  =  - 1 时，证明以下三结论是等价的： (a) G 是连通图； (b) G 是无圈图； (c) G 是树。 2.1.3 一树中若   k，则其中至少有 k 个度为 1 的顶点。 2.1.4 G 为林   =  -  。 2.1.5 若林 G 恰有 2k 个奇点，则 G 中存在 k 条边不重的路 P1 ,P2 ,..,Pk ,使得 E(G) = E(P1 )E(P2 ) ... E(Pk )。 2.1.6 正整数序列(d 1 ,d 2 ,...,d  )是一棵树的度序列，当且仅当 di i=  = − 1 2 1  ( ) 。 2.1.7 饱和烃分子形如 C mH n ,其中碳原子的价键为 4，氢原子的价键为 1，且任何价键序列都不构成圈。证明：对每个 m，仅当 n = 2m + 2 时 C mH n 方能存在。割边和键 e 为割边( cut edge)  (G-e) > (G) 。（即 (G-e) = (G) + 1 ）定理 2.3 e 为 G 的割边  e 不在 G 的任一圈中。证明：令 e = xy ，则 x 与 y 在 G 的同一分支中。于是， e 为 G 的割边  (G-e) = (G) + 1  x 与 y 不 G-e 在同一分支中  G-e 中无(x,y)-路  G 中无含 e 的圈。  定理 2.4 图 G 连通，且每边是割边  G 为树

10 证明：注意到以下事实即可， G 无圈  G 中每边不在任一圈中  G 中每边是其割边。  连通图 G 的生成树（spanning tree )  G 的生成子图，且为树。推论 2.4.1 每一连通图都包含一生成树。证明：令 T 为极小( minimal)连通生成子图（意指 T 的任一真子图都不是连通生成子图）（由定义，T 可在保持连通性的前提下，用逐步从 G 中去边（ 所去的边一定在一圈中（即非割边））（每次破坏一圈）的办法求出。由 T 的定义知， (T) = 1 ， (T - e) = 2  e  E(T) 。即 T 的每边为割边，故由定理 2.4 知 T 为树。  注也可用极大无圈（生成）子图（即其真生成母图都含圈）来求生成树 T。它可由 V 上的空图开始，在保持无圈的前提下，逐步由 G 中取边的办法求出。（为何是生成树？）推论 2.4.2 G     - 1 。定理 2.4.5 设 T 为 G 的一生成树，e 为 G 中不属于 T 的边，则 T+e 含唯一的圈。证明：由于 T 无圈，T + e 中的每个圈都包含 e 。又， C 为 T + e 的一圈  C - e 为 T 中连接 e 的两个端点的路。但，由定理 2.1 知，T 中恰只有一条这样的路，因此 T + e 中包含唯一的圈。小结 G 为树  G 中任二顶点间有唯一的路相连，且无环  G 连通，无圈  G 连通，且每边为割边  G 连通，且  =  - 1  G 连通。且  =  - 1 。图 G 的边割（ edge cut） [S, S ] S  V  G 中一端在 S 另一端在 S 中的边的子集合。显然，在连通图 G 中， E’  边割  (G-E’) > 1 。键（bond, 割集 cut set )  极小非空边割。例。e 是 G 的割边  {e} 是 G 的键。例。左图 G 中， {uv, zv, zy, vw, yx}, {zu, zv, zy, xy, xw}, {uv, zv, zy} {zu, zv, zy} 都是边割，其中后两个为键。而 E’ ={zu, zv, zy, uv} 不是 G 的边割，当然更不是 G 的键，虽然 G- E’ 变成不连通。易见，当 G 连通且 S   时，边子集 B 为 G 的键  B 是使 G 不连通的 E 的极小子集。  (G-B)=2，且中每边的两端点分别在二分支中。边割 B = [S, S ]为键  G[S],G[ S ]都连通。（习题）设 H 为 G 的子图，称子图 G - E(H) 为 G 中 H 的补图，记为： u v w z y x