《图-连通的概念》由会员分享，可在线阅读，更多相关《图-连通的概念（13页珍藏版）》请在金锄头文库上搜索。
1、三、连通性 3.1 连通性和 Whitmey 定理定义 V真包含于 V(G)，GV(G)-V 不连通，而 G 是连通图，则称 V是 G 的顶剖分集。最小顶剖分集中顶的个数，记成 (G)，叫做 G 的连通度；规定(Kv)=-1；(不连通图)= (平凡图)=0 。由一个顶组成的顶剖分集叫割顶。没有割顶的图叫做块，G 中的成块的极大子图叫做 G 的块。定义 E包含于 E(G)，G 为连通图，而 G-E(从 G 中删除 E中的边)不连通，则称 E为 G 的边剖分集，若 G 中已无边剖分集 E，使得|E|=k 时，G 叫做 k 连通图；(G)=k 时，G 称为 k 边连通图。k 连通图，当 k1 时，也
2、是 k-1 连通图。k 边连通图，当 k1 时，也是 k-1 边连通图。上面就是顶连通与边连通的概念，好象不指明的就是指顶连通了。定理 1 (G)=2 条边，移去它们之后，G 变成不连通图。于是删除这 条中的 -1 条后，G 变成有桥的图。设此桥为 e=uv，我们对于上述 -1条删去的每条边上，选取一个端点，删除这些(不超过 -1 个)端点，若 G 变得不边能，则 =3 的图是 2 连通图的充要条件是任二顶共圈(在一个圈上) 。证：若任二顶共圈，任删除一个顶 w 后，得图 G-w。任取两顶 u,vV(G-w)， u,v 在 G 中共存于圈 C 上，若 w 不在 C 上，则 G-w 中仍有圈 C
3、，即 u 与 v在 G-w 中仍连通；若 w 在 G 中时在 C 上，在 G-w 中 u 与 v 在轨 C-w 上，故 u与 v 仍连通。由 u 与 v 之任意性，G-w 是连通图，故 (G)=2，即 G 是 2 连通图。反之，若 G 是 2 连通图，=3,任取 u,vV(G) ，用对 d(u,v)的归纳法证明u 与 v 之间有两条无公共内顶的轨当 d(u,v)=1 是时，因 =2，uv 边不是桥， G-uv 仍连通，于是 G-uv 中存在从 u 到 v 的轨 P1(u,v),这样从 u 到 v 有两条无公共内顶的轨P1(u,v)与边 uv。假设 d(u,v)=2),结论已成立，考虑 d(u,
4、v)=k 的情形。令 P0(u,v)之长为 k,w 是 P0(u,v)上与 v 相邻的顶，则 d(u,w)=k-1，由归纳法假设，在 u,w 之间有两条无公共内顶 P 与 Q，因 G 是 2 连通较长，故 G-w 仍连通。在 G-w 中存在轨 P(u,v)=3,则下列命题等价：(1)G 是块。(2) G 的任二顶共圈。(3) G 的任一顶与任一边共圈(4) G 的任二边共圈(5) 任给 G 的二顶及一边，存在连接此二顶含此边之轨(6) 对 G 的三个不同的顶，存在一轨，连接其中两个顶，含第三个顶(7) 对 G 的三个不同的顶，存在一轨，连接其中两个顶，不含第三个顶。(本也没什么可证的了，但就这
5、样结束了也太快了，这个证一下)证：(1)(2) ，(2)(1) 见定理 2(2)(3) 只考虑 u 为 G 的任给一个顶，vu 是 G 中任给定的一条边，且uw 的情形。设 C 是含 u 与 v 的圈，若 w 在 C 上，则 C 上含 u 的轨P(v,w)与边 vw 形成一个圈，它含 u 及边 vw。若 w 不在 C 上，因 v 不是割顶，由定理 3，存在不含 v 的轨 P(w,u)。令 u是 P(w,u)与 C 从 w 沿 P(w,u)看来的第一个公共顶，则由边 vw,P(w,u)上 w 到 u段，以及 C 上含 u 的轨 P(u,v)并成一个圈，此圈满足(3)的要求。(3)(4)与(2)(
6、3)类似证明。(4)(5) 已知任二边共圈，设 u,v 是 G 上任给定的两个顶，x 是任给定的一条边，只考虑 x 与 u,v 皆不相关联的情形。由任二边共圈显然有任二顶共圈，于是由于(2)(3) 知 u 与 x 共圈，设此圈 C1；同理 v 与 x 共圈，设此圈是 C2；若 vC1 或 uC2, 则(5)成立；若 u 不属于 C2，且 v 不属于 C1，则如下构作含x 之轨 P(u,v):从 u 出发沿 C1 到达 C1 与 C2 上第一个公共顶 w,再从 w 出发沿C2 含 x 的部分到达 v。(5)(6) 设 u,v,w 是 G 的三个顶，且与 w 相关联的一条边是 x,由(5)存在轨P
7、(u,v)，x 在 P(u,v)上，于是 w 在 P(u,v)上。(6)(7) u,v,wV(G), 由(6)，存在轨 P(u,w)，P(u,w) 含顶 v,则 P(u,w)的从 u到 v 的一段不含 w。(7)(1) 由(7)，对任给定的二顶 u 与 v,不存在这样的顶，它在从 u 到 v 的每一轨上，由定理 3，G 无割顶，故 G 是块。证毕。讲了这么多，下节才涉及到实践中的问题。下节讲可靠通讯网的构作。不过下节又是本章的最后一节了。3.3 可靠通讯网的构作我们要构作一个有线通讯网，使得敌人炸坏我几通讯站后，其余的通讯站仍然可彼此通话。显然，有两个要求是必要的：一是不怕被敌人炸坏站的数目要
8、多，一是整个造价要小。这个实际问题的数学艺术模型如下：G 是加权连通图，k 是给定的自然数，求 G 的有最小权的 k 连通生成子图。当 k=1 时，它就是用 Kruskal 算法求得的生成树；当 k1 时，是尚未解决的难解问题之一。哦，原来 k1 时是没解决的难题，自己以前也想过这方面的东西，只是想了半天也想不出个所以然，原来是个大难题呀。当 G=K，每边权皆为 1 时，Harary 于 1962 年解决了这一问题。下面介绍Harary 的工作。令 f(m,n)表示 n 个顶的 m 连通图当中边数的最小值，m=mn/2Harary 实际上构作出一个 n 顶的 m 连通图，它的边数恰为 mn/2
9、条，且f(m,n)=mn/2。此图记成 H(m,n) 。(1) m 是偶数， m=2r。H(2r,n)以0,1,2,n-1为顶集合。当 i-r=mn/2, (H(m,n)=mn/2,而 H(m,n)是 n 顶 m 连通图，故有f(m,n)=2,故存在不在 P(u,v)上的一条边 e 与 u 相关联。设 e 的另一端点为 w,若 w 不属于 P(u,v)，则 P(u,v)可以加长，与最长相矛盾，故 w 是肯定属于 P(u,v)的，所以 G 中有圈。证毕。例 9：若 G 是连通图，G包含于 G，|V(G)|=3,由“最长轨方法 ”知存在 vi0)有公共的 0-1 标志边是时， 2i 与 2j 这两
10、顶间连一条边； 20 与 2i(1=0(i=0,1,2),ai=1。这里写的 x,x0,x1,x2 是二维向量。记x=(a0,a1,a2),f(x)=(a0,a1,a2)。令 Si=(a0,a1,a2)|(a0,a1,a2)=ai,i=0,1,2。只欠证明 Si(i 从 0 至 2)非空。若Si(i 从 0 至 2)非空为真，则存在(a0,a1,a2)0；否则对每个 ai0 时，aiai，于是 aiai，矛盾(刚开始看的时候对这段话百思不得其解，回头好好的看了一下 Si 的定义，才恍然大悟)。我们如下的标志：一个三角形顶点 x 属于 Si，且 ai0 时，x 标以 i，这种标志是正态标志，例如
11、在 2 x0x1 边上各点的 a2=0，我们只能把这边上的点标以 0或 1；x0x2 上的点同理只能标 0 或 2；x1x2 上只能标 1 或 2，故为正态标志。由定理 2，至少有一个正态三角形，其顶点分别属于 S0，S1 ，S2 。我们使剖分无限变密，且小三角形有任意小的直径，则 S0，S1 ，S2 中有三个点可以任意小，又 f 连续，故 Si(i=0,1,2)是闭集，于是 Si(i 从 0 至 2)非空为真。证毕。( 最后 “又。 。 。故。 。 。于是”这点有点迷糊，好象已经超过我所学的了)这个定理是证完了，但一点都没有前几节证完一个定理的那种感觉。对这个定理的背景本身模模糊糊，不象其他
12、定理那样的通俗易懂。看起来一句是一句，看证明一句句的看下来大多都是明白的，但看完后连不起来。也许它不是一个图论中的定理的缘故。下节是本章的最后一节，讲最短路径的 Dijkstra 算法。 1.5 Dijkstra 算法这一节比较的轻松，Dijkstra 算法是这以前知道的最早的图论算法，当然那时并不知这就是 Dijkstra 算法，只知道这是求最短路径用的。这个算法比较的简单，也不用什么很高深的背景知识，所以书上也没怎么讲，算法方面这里也不想记了，这个算法随便找本数据结构的书好象都有讲的。这里给出最短路径问题的数学模型：w=w(e)是定义域为 E(G)的实函数，称 w(e)为图 G 的边 e
13、之权，G 叫做加权图，记W(G)=w(e),W(G)叫做图 G 的权，我们求满足某条件的子图 H，且使其权最小即W(H)= w(e)(e=2)人中每个人至少同其中 n 个人相识，则其中至少有四个人，使得这四人围圆桌而坐时，每个人旁边是他认识的人。3两人有酒，装滿 8 斤之瓶，另有能装 5 斤与 3 斤的空瓶各一只，今欲平分其酒，请设计一个最简便的方法。4俱乐部有 14 人想打桥牌，过去每个人都曾与其中 5 个人合作过；现规定四人中必须任何两个人都未合作过才准许在一起打一局，在这种规定下，只打三局就无法继续进行，这是新来了一位年轻人，试证明有个年轻人参加，一定还可以再打一局。5任何 9 个人中必有三人相识或四个彼此不相识。
