第7章图论II.ppt
《第7章图论II.ppt》由会员分享,可在线阅读,更多相关《第7章图论II.ppt(108页珍藏版)》请在三一文库上搜索。
1、第八章 几类重要的图,退出,8.1 欧拉图与哈密尔顿图 8.2 二部图 8.3 树 8.4 平面图,8.1 欧拉图与哈密尔顿图,1736年瑞士数学家欧拉发表了图论的第一篇著名论文“哥尼斯堡七桥问题”(下称七桥问题)。这个问题是这样的:哥尼斯堡城有一条横贯全城的普雷格尔河,城的各部分用七桥联结,每逢节假日,有些城市居民进行环城周游,于是便产生了能否“从某地出发,通过每桥恰好一次,在走遍了七桥后又返回到原处”的问题。,在图11.1.1画出了哥尼斯堡城图,城的四块陆地部分以A,B,C,和D标记。欧拉巧妙地把哥尼斯堡城图化为图11.1.2所示图G,他把陆地设为图G中的结点,把桥画成相应地联结陆地即结点
2、的边。于是,通过哥尼斯堡城中每座桥恰好一次问题,等价于在图G中从某一结点出发找出一条链,它通过每条边恰好一次后回到原出发结点,亦即等价于在图G中寻找一个圈,它通过G中每一条边恰好一次。,图 11.1.1,A,B,D,C,图 11.1.2,欧拉在这篇论文中提出了一条简单准则,确定七桥问题是不能解的。下面就来讨论这个问题。 定义8.1.1 图G中的存在一个回路,若它通过G中的每一条边(或弧)恰好一次,则称该回路为欧拉回路(欧拉环游,Euler tour),具有这种回路的图称为欧拉图。欧拉回路是一个闭迹。 定理8.1.1 给定连通无向图G,G有欧拉回路G中每个结点都是偶度结点。,Proof . Th
3、e degree condition is clearly necessary: a vertex appearing k times in an Euler tour (or k +1 times, if it is the starting and finishing vertex and as such counted twice) must have degree 2k. Conversely, let G be a connected graph with all degrees even, and let W = v0e0 . . . el-1vl be a longest wal
4、k in G using no edge more than once. Since W cannot be extended, it already contains all the edges at vl. By assumption, the number of such edges is even. Hence vl= v0, so W is a closed walk.,Suppose W is not an Euler tour. Then G has an edge e outside W but incident with a vertex of W, say e = uvi.
5、 Here we use the connectedness of G,then the walk ueviei . . . el-1vl e0 . . . ei-1vi is longer than W, a contradiction. 由定义11.1.1可知,具有欧拉回路的图是欧拉图,故图G为欧拉图G中每个结点都是偶度结点。 由于七桥问题所对应的图中每个结点都是奇度结点,根据上述定理可知,七桥问题无解。,定义8.1.2 图G中的一条通道,若它通过G中的每条边恰好一次,则称该通道为欧拉迹。 定理8.1.2 给定连通无向图G=,u,vV且uv,u与v间存在欧拉迹G中仅有u和v为奇度点。 (补
6、证)。,定理8.1.3 给定弱连通有向图G,G有欧拉回路G中的每个结点的入度等于出度。 定理8.1.4 给定弱连通有向图G=,u,vV且uv,u与v之间存在欧拉迹G中唯有u和v的入度不等于出度,且u的入度比其出度大于1和v的出度比其入度小于1(或者反之)。,这两个定理的证明,可以看作是关于无向图的欧拉回路和欧拉迹的推广。因为对于有向图的任意一个结点来说,如果入度与出度相等,则该结点为偶度结点;如果入度与出度之差为1时,该结点必是奇度结点,所以定理11.1.3和14.1.4与前面两个定理的证明类似。,与欧拉回路和迹非常类似的问题是哈密尔顿圈和哈密尔顿圈路的问题。 1859年,爱尔兰数学家哈密尔顿
7、(W.R.Hamilton)首先提出“环球周游”问题。他用一个正十二面体的20个顶点代表世界上20个大城市(见图11.1.4(a),这个正十二面体同构于一个平面图(见图11.1.4(b),平面图的定义稍后给出),要求旅游者能否找到沿着正十二面体的棱,从某个顶点(即城市)出发,经过每个顶点(即每座城市)恰好一次,然后回到出发顶点?这便是著名的哈密尔顿问题。,图 11.1.4,按图11.1.4(c)中所给的编号进行旅游,便是哈密尔顿问题的解。 对于任何连通图也有类似的问题。,图 11.1.4,定义8.1.3 图G中的一个圈,若它通过G中每个结点恰好一次,则该圈称为哈密尔顿圈,具有哈密尔顿圈的图称为
8、哈密尔顿图。 由该定义可知,完全图必是哈密尔顿图。,定义8.1.4 图G中的一条路,若它通过G中的每个结点恰好一次,则该路称为哈密尔顿 路。 哈密尔顿图尽管在形式上与欧拉图极其相似,但其结论上却有很大不同,至今还没有得到关于哈密尔顿图的非平凡的充要条件,这是图论尚未解决的主要问题之一。然而,还是有不少重要成果,下面给出几个必要和充分条件的定理。,定理8.1.5 若连通图G=是哈密尔顿图,S是V 的任意真子集,则(G-S)|S|。 (课上补证) 本定理给出是哈密尔顿图的一个必要条件,但这个条件又不便于使用,因为它要求对G的结点集合的所有真子集进行验证。尽管如此,利用它还可以证明某些图不是哈密尔顿
9、图。,不过,利用这个必要条件不总是有效的。例如: 彼得森图:满足必要条件,但是非汉密尔顿的。,下面给出图G是哈密尔顿图的充分条件,这个结果是于1952年Dirac研究得到的。 定理8.1.6 给定简单图G=,|V|=n,若n3和(G)n/2,则G是哈密尔顿图。 请注意,本定理给出的仅是充分条件。例如,十多边形显然是哈密尔顿图,但=2 =5。,Proof . Let G = (V,E) be a graph with |G| = n3 and (G)n/2. Then G is connected: otherwise, the degree of any vertex in the small
10、est component C of G would be less than |C|n/2. Let P = x0 . . . xk be a longest path in G. By the maximality of P, all the neighbours of x0 and all the neighbours of xk lie on P. Hence at least n/2 of the vertices x0, . . . , xk-1are adjacent to xk, and at least n/2 of these same k n vertices xi ar
11、e such that x0xi+1E. By the pigeon hole principle, there is a vertex xi that has both properties, so we have x0xi+1E and xixkE for some i k.,We claim that the cycle C := x0xi+1PxkxiPx0 is a Hamilton cycle of G. Indeed, since G is connected, C would otherwise have a neighbour in G C, which could be c
12、ombined with a spanning path of C into a path longer than P.,x0,xk,xi+1,xi,Bondy和Chvatol于1974年证明了更强的充分条件。他们的方法是建立下面两个引理之上的。 引理8.1.1 给定图G=,|V|=n3。若u,vV,u与v不邻接且d(u)+d(v)n,则G是哈密尔顿图G +uv是哈尔密顿图。,受引理8.1.1启示,可以定义图的闭包概念。 定义8.1.4 给定图G=,|V|=n。图G的闭包是由G通过相继地用边连接两个其度之和至少为n的不邻接结点,直到不能如此进行为止而得到的图。用C(G)表示图G的闭包。 引理8
13、.1.2 C(G)是唯一确定的。,下面定理是引理11.1.1的直接结果: 定理8.1.7 简单无向图G是哈密尔顿图C(G)是哈密尔顿图。 容易看出,至少有三个点的所有完全图都是哈密尔顿图。由此可得到下面推论: 推论 给定简单无向图G=,|V|3。若C(G)是完全图,则图G是哈尔密顿图。,对于有向图的哈密尔顿回路和路也有此类似结果,但其证明却是困难得多,因此这里只叙述由Ghoula-Houri给出的定理如下: 定理8.1.8 给定n阶强连通图G=。若对任意vV,有d+(v)+d-(v)n,则G有哈密尔顿回路。,8.2 二部图,本节简要介绍二部图及二部图中匹配理论的主要概念和成果。 定义8.2.1
14、 给定简单无向图G=,且V=V1V2,V1V2=。若V1和V2的导出子图和都是零图,则称G是二部图或偶图,并将二部图记作G=,并称V1,V2是V的划分。,在一个二部图G=中,若|V1|=m,|V2|=n,且对任意的uV1,vV2均有(u,v)E,则称G为完全二部图,记为Km,n。 定理8.2.1 简单图G为二部图G中不含奇圈。 定理: 若G为n阶二部图,则|E(G)|n2/4。 注:课上补证。,定义8.2.2 给定简单无向图G=,若ME且M中任意两条边都是不邻接的,则子集M称为G的一个匹配或对集(matching),并把M中的边所关联的两个结点称为在M下是匹配的。 令M是G的一个匹配,若结点v
15、与M中的边关联,则称v是M饱和的;否则,称v是M不饱和的;若G中的每个结点都是M饱和的,则称M是完全匹配(perfect matching)。如果G中没有匹配M1,使|M1|M|,则称M是最大匹配。显然,每个完全匹配是最大匹配,但反之不真。,定义8.2.3 令M是图G=中的一个匹配。若存在一条路,它是由分别由E-M和M中的边交替构成,则称该路是G中的M-交错路(M-alternating path); 若M-交错路的始结点和终结点都是M-不饱和的,则称该链为M-增广路(M-augmenting path);特别地,若M-交错路的始结点也是它的终结点而形成圈,则称该圈为M-交错圈。,在匹配理论中
16、,人们特别关心的是最大匹配。Alternating paths play an important role in the practical search for large matchings. Berge在1957年给出了一个图中的一个匹配为最大匹配的充要条件。在证明这一结论时,将要用到两个集合的对称差的概念,现叙述如下:给定两个集合S和T,S与T的对称差,记为ST,其定义为:ST=(ST)-(ST).,引理8.2.1 设M1和M2是图G中的两个匹配,则在中,每个(连通)分支或是交错路,或是交错圈。 定理8.2.2 (Berge,1957)图G的一个匹配M是个最大匹配当且仅当G中不含有M
17、-增广路。 证:Let M be a maximum matching in G. Suppose that G contains an M-augmenting path P. Then M := ME(P) is a matching in G, and |M| = |M| + 1. Thus M is not a maximum matching.,Conversely, suppose that M is not a maximum matching, and let M be a maximum matching in G, so that |M| |M|. Set H := GMM
18、, as illustrated in Figure. Each vertex of H has degree one or two in H, for it can be incident with at most one edge of M and one edge of M . Consequently, each component of H is either an even cycle with edges alternately in M and M , or else a path with edges alternately in M and M . Because | M|
19、 |M|, the subgraph H contains more edges of M than of M, and therefore some path-component P of H must start and end with edges of M. The origin and terminus of P, being covered by M, are not covered by M. The path P is thus an M-augmenting path in G.,在许多应用中,希望在二部图G=中找出一个匹配M,使得V1中每个结点都是M饱和的。1935年,Ha
20、ll首先给出存在这样匹配的充分必要条件的定理。 定理8.2.3 (Hall 1935) 给定二部图G=,G中存在使V1中每个结点饱和的匹配对任意SV1有 |N(S)|S| (2) 其中N(S)表示与S中结点邻接的所有结点集合。 证:We apply induction on |A|. For |A| = 1 the assertion is true. Now let |A|2, and assume that the marriage condition is sufficient for the existence of a matching of A when |A| is smalle
21、r.,If |N(S)|S|+1 for every non-empty set S A, we pick an edge ab G and consider the graph G* := Ga, b . Then every non-empty set S Aa satisfies|NG* (S)|NG(S)|1 |S| , so by the induction hypothesis G* contains a matching of Aa. Together with the edge ab, this yields a matching of A in G. Suppose now
22、that A has a non-empty proper subset A* with |B*| = |A*| for B* := N(A*). By the induction hypothesis, G* := GA*B* contains a matching of A*. But GG* satisfies the marriage condition too: for any set S AA* with |NGG* (S)| |S| we would have |NG(SA*)| |SA*|, contrary to our assumption. Again by induct
23、ion, GG* contains a matching of AA*. Putting the two matchings together, we obtain a matching of A in G.,推论 若G=是二部图,且对于任意vV1或V2有d(v)=k0,则G有一个完全匹配。 证: If G is k-regular, then clearly |A| = |B|; it thus suffices to show by Theorem 11.2.3 that G contains a matching of A. Now every set S A is joined to
24、N(S) by a total of k |S| edges, and these are among the k |N(S)| edges of G incident with N(S). Therefore k |S|k|N(S)|, so G does indeed satisfy the marriage condition.,在定理8.2.3的证明中,它提供了在二部图G=中寻找一个匹配M,使V1中每个结点是M一饱和的。下面给出的称为Hungarian方法的算法。令M是G=中任意一个匹配,该算法是:,(1) 若V1中每个结点是M饱和的,停止。否则,令v是V1中M不饱和结点,作 S=v和
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 章图论 II
链接地址:https://www.31doc.com/p-2608396.html