第八章几种特殊的图

第八章几种特殊的图本章讨论几类在理论研究和实际应用中都有重要意义的特殊图，它们是二分图、平面图和树。8.1二分图8.1.1二分图的基本概念定义8.1无向图G=V，E，称为二分图（bipartitegraph），如果有非空集合X，Y使X∪Y=V，X∩Y=，且对每一eE，(e)=(x,y)，xX，yY。此时常用X，E，Y表示二分图G。若对X中任一x及Y中任一y恰有一边eE，使(e)=(x,y),则称G为完全二分图（completebipartitegraph）。当X=m，Y=n时，完全二分图G记为Km,n。例8.1图8.1中（a），（b）为二分图，（c）为完全二分图K3,3，(d),(e)不是二分图。(a)(b)(c)(d)(e)图8.1二分图的下列特征性是重要的。定理8.1无向图G为二分图的充分必要条件是，G至少有两个顶点,且其所有回路的长度均为偶数。证先证必要性。设G为二分图X，E，Y。由于X，Y非空，故G至少有两个顶点。若C为G中任一回路，令C=(v0,v1,v2,…,vl-1,vl=v0)其中诸vi(i=0,1,…,l)必定相间出现于X及Y中，不妨设{v0,v2,v4,…,vl=v0}X{v1,v3,v5,…,vl-1}Y因此l必为偶数，从而C中有偶数条边。再证充分性。设G的所有回路具有偶数长度，并设G为连通图（不失一般性，若G不连通，则可对G的各连通分支作下述讨论）。令G的顶点集为V，边集为E，现构作X，Y，使X，E，Y=G。取v0V,置X={vv=v0或v到v0有偶数长度的通路}Y=V-XX显然非空。现需证Y非空，且没有任何边的两个端点都在X中或都在Y中。由于V≥2并且G为一连通图，因此v0必定有相邻顶点，设为v1，那么v1Y；故Y不空。设有边(u,v),使uX，vX。那么，v0到u有偶数长度的通路，或u=v0；v0到v有偶数长度的通路，或v=v0。无论何种情况，均有一条从v0到v0的奇数长度的闭路径，因而有从v0到v0的奇数长度的回路（因从闭路径上可能删去的回路长度总为偶数），与题设矛盾。故不可能有边（u,v）使u,v均在X中。“没有任何边的两个端点全在Y中”的证明可仿上进行，请读者思考。二分图是十分有用的一种数学模型，许多问题可以用它来刻划。例如“资源分配”、“工作安排”、“人员择偶”等等。但是，利用二分图分析解决这类问题时，还需要有关二分图的另一个概念——匹配。8.1.2匹配定义8.2设G=X，E，Y为二分图，ME。称M为G的一个匹配（matching），如果M中任何两条边都没有公共端点。G的所有匹配中边数最多的匹配称为最大匹配（maximalmatching）。如果X(Y)中任一顶点均为匹配M中边的端点，那么称M为X(Y)-完全匹配(perfectmatching)。若M既是X-完全匹配又是Y-完全匹配，则称M为G的完全匹配。例8.2图8.2中各图的粗线表示匹配中的边（简称匹配边）。（b）中匹配是最大的，X-完全的，（c）中匹配是完全的（从而也是最大的）。（a）（b）（c）图8.2注意，最大匹配总是存在但未必唯一。此外，X(Y)-完全匹配及完全匹配必定是最大的，但反之则不然；X(Y)-完全匹配未必存在。为讨论最大匹配的求法及完全匹配的存在条件，需要下列术语。定义8.3设G=X，E，Y，M为G的一个匹配。（1）M中边的端点称为M-顶点，其它顶点称为非M-顶点。（2）G中vk到vl的通路P称为交替链，如果P的起点vk和终点vl为非M-顶点，而其边的序列中非匹配边与匹配边交替出现（从而首尾两边必为非匹配边，除顶点vk，vl以外各顶点均为M-顶点）。特别地，当一边（v,v'）两端点均为非M-顶点，通路（v,v'）亦称为交替链。以下算法可把G中任一匹配M扩充为最大匹配，此算法是Edmonds于1965年提出的，被称为匈牙利算法，其步骤如下：（1）首先用（*）标记X中所有的非M-顶点，然后交替进行步骤（2），（3）。（2）选取一个刚标记（用（*）或在步骤（3）中用（yi）标记）过的X中顶点，例如顶点xi，然后用（xi）去标记Y中顶点y，如果xi与y为同一非匹配边的两端点，且在本步骤中y尚未被标记过。重复步骤（2），直至对刚标记过的X中顶点全部完成一遍上述过程。（3）选取一个刚标记（在步骤（2）中用（xi）标记）过的Y中结点，例如yi，用（yi）去标记X中结点x，如果yi与x为同一匹配边的两端点，且在本步骤中x尚未被标记过。重复步骤（3），直至对刚标记过的Y中结点全部完成一遍上述过程。（2），（3）交替执行，直到下述情况之一出现为止：（Ⅰ）标记到一个Y中顶点y，它不是M-顶点。这时从y出发循标记回溯，直到（*）标记的X中顶点x，我们求得一条交替链。设其长度为2k+1，显然其中k条是匹配边，k+1条是非匹配边。（Ⅱ）步骤（2）或（3）找不到可标记结点，而又不是情况（Ⅰ）。（4）当（2），（3）步骤中断于情况（Ⅰ），则将交替链中非匹配边改为匹配边，原匹配边改为非匹配边（从而得到一个比原匹配多一条边的新匹配），回到步骤（1），同时消除一切现有标记。（5）对一切可能，（2）和（3）步骤均中断于情况（Ⅱ），或步骤（1）无可标记结点，算法终止（算法找不到交替链）。我们不打算证明算法的正确性，只用一个例子跟踪一下算法的执行，来直观地说明这一点。例8.3用匈牙利算法求图8.3的一个最大匹配。图8.3（1）置M=，对x1-x6标记（*）。（2）找到交替链（x1,y1）（由标记（x1），（*）回溯得），置M={(x1,y1)}。（3）找到交替链（x2,y2）（由标记（x2），（*）回溯得），置M={(x1,y1),(x2,y2),}。（4）找到交替链（x3,y1,x1,y4）（如图8.4所示。图中虚线表示非匹配边，细实线表示交替链中非匹配边，粗实线表示匹配边），因而得M={(x2,y2),(x3,y1),(x1,y4)}。（5）找到交替链（x4,y3）（由标记（x4），（*）回溯得），置M={(x2,y2),(x3,y1),(x1,y4),(x4,y3)}。（6）找到交替链（x5,y4,x1,y1,x3,y7）（如图8.5所示，图中各种线段的意义同上），因而得M={(x2,y2),(x4,y3),(x5,y4),(x1,y1),(x3,y7)}即为最大匹配（如图8.6所示）。图8.4x1x2x3x4x5x6y1y2y3y4y5y6y7x1x2x3*x4*x5*x6*y1y2y3y4y5y6y7（x3）（x1）（y1）图8.5图8.6现在我们来讨论完全匹配的存在条件。为此，定义图G=V，E，的顶点子集SV的相邻顶点集N(S)（所有与S中顶点相邻的顶点组成的集合）：N(S)={vvV∧ue(uS∧eE∧(e)=(u,v))}或N(S)={vue(uS∧(e)=(u,v))}定理8.2设图G=X，E，Y。G有X-完全匹配的充分必要条件是：对每一SX有N(S)≥S此定理是霍尔（Hall）于1935年证明的，通常称为霍尔婚姻定理。证必要性是易证的。设G有X-完全匹配{(x0,yi0),(x1,yi1),…,(xm,yim)}(m=X)其中诸xi互不相同，诸yij也各不一样，因此对任一SX，S中有多少元素，N(S)中至少也有同样多的元素，即N(S)≥S。x1x2x3x4x5x6y1y2y3y4y5y6y7(y4)(y1)**(x1)(x5)(x3)x1x2x3x4x5x6y1y2y3y4y5y6y7现证充分性。设G满足：对任一SX，N(S)≥S，但G无X-完全匹配。作G的最大匹配M，据假设，至少有顶点xX，x不是M-顶点。用匈牙利算法求起始于x的所有交替链。由于M已是最大匹配，上述构作过程必定在步骤（3）中因情况(Ⅱ)停止，即它们都只能是末尾边为匹配边的链（暂称伪交替链）。用Q表示这些伪交替链上的顶点集合，易知，Q中只有x不是M-顶点。置S=Q∩X，S'=Q∩Y（参阅图8.7）图8.7显然，S-{x}中顶点与S'中顶点一一对应，因此S'=S-1S'N(S)事实上N(S)=S'，因为对每一yN(S)，都有顶点uS=Q∩X（因而uQ）使(u,y)为一伪交替链中的边，从而yQ，即yQ∩Y=S'之中。据以上讨论，N(S)=S'=S-1N(S)S与题设矛盾，因此M必是X-完全匹配。定理8.2证毕。对Y-完全匹配有类似的结论，不赘述。例8.4k-正则二分图（k0）有完全匹配。证设G=X,E,Y为k-正则二分图，那么k·X=E=k·Y从而X=Y。设S为X的任一子集，E1为S中顶点所邻接的边的集合，E2为N(S)中顶点所邻接的边xS-{x}S’v的集合。据N(S)的定义，E1E2，于是k·N(S)=E2≥E1=k·SN(S)≥S因此G有X-完全匹配M。由于X=Y，显然M也是Y-完全匹配，故G有完全匹配。8.3欧拉图与哈密顿图8.3.1欧拉图与欧拉路径定义8.19图G称为欧拉图（Eulergraph），如果图G上有一条经过G的所有顶点、所有边的闭路径。图G称为欧拉路径（Eulerwalk），如果图G上有一条经过G所有顶点、所有边的路径。本章一开头介绍的哥尼斯堡桥问题，现在可以这样来叙述：图8.l（b）是否为一欧拉图？定理8.11无向图G为欧拉图当且仅当G连通，并且所有顶点的度都是偶数。有向图G为欧拉图，当且仅当G是弱连通的，并且每个顶点的出度与入度相等。证这里仅对无向图立论，定理的后半部分仿此可证，不赘述设G为一欧拉图，那么G显然是连通的。另一方面，由于G本身为一闭路径，它每经过一个顶点一次，便给这一顶点增加度数2，因而各顶点的度均为该路径经历此顶点的次数的两倍，从而均为偶数。反之，设G连通，且每个顶点的度均为偶数，欲证G为一欧拉图。为此，对G的边数归纳。当m=1时，G必定为单结点的环，如图8.22（a）所示，显然这时G为欧拉图。设边数少于m的连通图，在顶点度均为偶数时必为欧拉图，现考虑有m条边的图G。设想从G的任一点出发，沿着边构画，使笔不离开图且不在构画过的边上重新构画。由于每个顶点都是偶数度，笔在进入一个结点后总能离开那个结点，除非笔回到了起点。在笔回到起点时，它构画出一条闭路径，记为H。从图G中删去H的所有边，所得图记为G’，G’未必连通，但其各顶点的度数仍均为偶数（为什么？）。考虑G的各连通分支，由于它们都连通，顶点度数均为偶数，而边数均小于m，因此据归纳假设，它们都是欧拉图。此外，由于G连通，它们都与H共有一个或若干个公共顶点（如图8.22（b）所示），因此，它们与H一起构成一个闭路径。这就是说，G是一个欧拉图。H(a)(b)图8.22如果G，G1，G2为图，G=G1G2，G1G2为零图，那么称G可分成G1，G2。由上述定理的证明过程，我们还能得到以下定理。定理8.12如果G为欧拉图，那么G可分成若干个（一个或几个）回路。定理8.13无向图G为欧拉路径(非欧拉图)，当且仅当G连通，并且恰有两个顶点的度是奇数。有向图G为欧拉路径(非欧拉图)，当且仅当G连通，并且恰有两个顶点的入度与出度不等，它们中一个的出度比入度多1，另一个入度比出度多l。例8.12（1）由于图8.1（b）的四个顶点都是奇数度的，因此它既不是欧拉图也不是欧拉路径。这就是说，无论是否要求回到原地，不重复地走遍七桥是不可能的。（2）奇数(大于1)个顶点的完全图、k为偶数时的k-正则图都是欧拉图。（3）一笔画游戏(笔不离开纸,不重复地画遍纸上图形的所有的边),实质上是一个欧拉图、欧拉路径的判定问题。图8.23（a）可以从一点出发一笔画所有边后回到起点；图8.23（b）可以一笔画所有边，但不能使笔回到起点；图8.23（c）则根本不可能一笔画所有边。(a)(b)(c)图8.238.3.2哈密顿图及哈密顿通路定义8.20无向图G称为哈密顿图（Ham