第8章 图论 topics in graph theory11月20日周四

《第8章 图论 topics in graph theory11月20日周四》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第8章图论TopicsinGraphTheory§8.3Hamilton路径和Hamilton回路周游世界问题：每个城市访问一次只经过一次。Hamilton公爵提出是否存在一条回路通过正二十边形每个顶点恰一次。一个连通图GHamilton路径:经过每个顶点恰一次的路径。Hamilton回路：经过每个顶点恰一次的回路。Hamilton图：有Hamilton回路的图。完全图Kn，n>2，是Hamilton图。归纳可证。n个顶点的连通图G有Hamilton回路，G至少有n条边。用p(G)表示图G的连通分量的个数。定理

2、1.G＝(V,E)是Hamilton图，则对任意V1ÍV,p(G-V1)≤

3、V1

4、.证明：设C是G的一个Hamilton回路，V1都在C上。回路C中去掉V1中顶点，至多划分成

5、v1

6、段。因此p(C-V1)≤

7、V1

8、.例1.下图不是Hamilton图。引理2.n阶简单无向图G中，l：a……vivj……b，是一条有m个顶点的路径。a，b只与l中顶点相邻，D(a)+D(b)≥m。则l中所有顶点构成回路。证明.若a，b相邻，a……vivj……b是回路。设a，b不相邻。D(a)=s,D(b)=t.s+t≥m。t≥m－s。

9、l中存在相连顶点vi，vj，avj相邻，bvi相邻，avj……bvi……a构成一个回路。定理3.n阶简单无向图G中，n>2,任意两个不相邻顶点的度数之和大于等于n－1，则G有Hamilton路径。证明.取G中最长路径：l：a……vi……vj……b。我们证明其长度为n－1，包含G的所有顶点，否则一定可以加长。a，b不与l外的顶点相邻，否则l可以加长。设l的长度≤n－2，l上共有顶点少于n－1个。a,b度数和大于n－1，由引理1.l的所有顶点组成回路。这时有一顶点c不在l上，cc必与l中一点vi相邻。我们得到含有顶

10、点c，和l中所有顶点的路径，长度比l更长。推论4.n阶简单无向图G中，n>2,任意两个不相邻顶点的度数之和大于等于n，则G有Hamilton回路。证明.由定理3，G有Hamilton路径。由引理2，这条路径可以构成一条Hamilton回路。推论5.n阶简单无向图G中，n>2,任意顶点的度数大于等于n/2，则G有Hamilton回路。定理6.G有n个顶点，m条边，如果，则G是Hamilton图。证明.任取不相邻的两个顶点u，v∈G，G中去掉u，v后导出子图G’,G’有n－2个顶点，至多条边。u，v到G’的边数有D

11、(u)+D(v)≥n.由推论4.G是Hamilton图。HomeworkPP2961－6，16，17，20补.亚瑟王召见100个武士，每个武士至多49个仇人，则亚瑟王可以让这100个武士坐成一圈，使每个武士都不与仇人相邻。§8.4运输网络TransportNetworks留作自学材料。§8.5匹配问题MatchingProblem二部图、偶图BipartiteGraph：无向图G＝(V,E),V=V1∪V2，V1∩V2＝Æ。V1中顶点互不相邻，V2中顶点互不相邻，任意边连接V1，V2中各一个顶点。G=(V1,V

12、2,E).完全二部图：V1中每个顶点与V2中每个顶点都相邻。

13、V1

14、=m,

15、V2

16、=n,完全二部图记做Km,n。K2,3,K3,3.定理1.二部图中没有奇数长的回路。左边两图同构是K2,3，右边都是K3,3.E*ÍE.E*中的边互不相连，称E*为G的一个匹配。边数最大的匹配叫最大匹配。邻接V1或V2中所有顶点的匹配叫完全匹配。

17、V1

18、=

19、V2

20、时，完全匹配也叫完美匹配。定理2.（Hall定理）设G=(V1,V2,E),

21、V1

22、≤

23、V2

24、.G中有完全匹配iffV1中任意k个顶点至少与V2中任意k个顶点相邻，即，任

25、意XÍV1，

26、X

27、≤

28、R(X)

29、，R(X)为与X中顶点相邻的顶点的集合。证明.Þ是显然的。Ü对V1中顶点个数归纳：

30、V1

31、=1是显然的。设

32、V1

33、=k时定理成立。

34、V1

35、=k＋1：1）如果V1中任意k个顶点都至少与V2中k＋1个顶点相邻，从G中去掉一条边，V1中任意k个顶点都至少与V2中k个顶点相邻，存在完美匹配。2）如果V1中存在k个顶点只与V2中k个顶点相邻，例如{a1,a2,……，ak}ÍV1，{b1,b2,……，bk}ÍV2，{a1,a2,……，ak}只与{b1,b2,……，bk}相邻。则V1－{a1,

36、a2,……，ak}任意s个顶点，都与V2－{b1,b2,……，bk}中s个顶点相连。两部分都有完美匹配。推论3.二部图G＝(V1,V2,E)中如果（1）V1中每个顶点至少与V2中t条边相邻。（2）V2中每个顶点至多与V1中t条边相邻。则G有完美匹配。证明.V1中任意k个顶点的总度数≥kt。V2中任意k个顶点的总度数≤kt。V1中任意k个顶点至少与V2中k条边相邻。由Hall定理，G有完