离散数学一些特殊的图

《离散数学一些特殊的图》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、1第8章一些特殊的图8.1二部图8.2欧拉图8.3哈密顿图8.4平面图28.1二部图二部图完全二部图匹配极大匹配最大匹配匹配数完备匹配3二部图定义设无向图G=,若能将V分成V1和V2(V1V2=V,V1V2=),使得G中的每条边的两个端点都一个属于V1,另一个属于V2,则称G为二部图(二分图),记为,称V1和V2为互补顶点子集.又若G是简单图,且V1中每个顶点均与V2中每个顶点都相邻,则称G为完全二部图,记为Kr,s,其中r=

2、V1

3、,s=

4、V2

5、.(a)(b)以上两个图都是二部图，其中(b)图是完全二部图。4例

6、完全二分图Km,n=(V1,V2,E)共有多少条边?解因为V1中每个顶点都与V2中每个顶点相邻接,所以V1中每个顶点关联

7、V2

8、=n条边;而V1中有m个顶点,所以Km,n共有mn条边。5二部图的判别法定理无向图G=是二部图当且仅当G中无奇圈。即G中的每一条回路都是由偶数条边组成。证明：当G(V1,V2)是二部图时，G中的任意一条回路的各边必须往返于V1,V2之间，因此其回路必由偶数条边组成。6例：判断下图是否为二部图。解：图中的每一条回路都是由偶数条边组成。所以此图为二部图。→7匹配设G=(V,E)是具有互补顶点子集V1和V2的二分图,

9、ME,若M中任意两条边都不相邻,则称M为G中的匹配(对集)。如果M是G的匹配,且M中再加入任何一条边就都是不匹配了,则称M为极大匹配。最大匹配:边数最多的匹配匹配数:最大匹配中的边数,记为1。8如在下图中，如果用a1,a2,a3,a4表示4位教师，b1,b2,b3表示三门待开的课程。当某位教师能开某门课程时，则把它们的对应顶点用边连接起来。如果规定一个教师只能担任一门课程，那么匹配M就表示了一种排课方案。为了使排课方案能最大限度地作到“各尽其能”，这就是最大匹配的概念。9匹配(续)设M为G中一个匹配ai与bj被M匹配:(ai,bj)Mai为

10、M饱和点:M中有边与ai关联ai为M非饱和点:M中没有边与ai关联M为完美匹配:G的每个顶点都是M饱和点10定义设G=为二部图,

11、V1

12、

13、V2

14、,M是G中最大匹配,若V1中顶点全是M饱和点,则称M为G中V1到V2的完备匹配.当

15、V1

16、=

17、V2

18、时,完备匹配变成完美匹配.(1)(2)(3)图中红边组成各图的一个匹配，(1)为完备的,但不是完美的;(2)不是完备的,其实(2)中无完备匹配;(3)是完美的.匹配(续)例：如图11M1M2例求下图的饱和点，并判断哪个图是完美匹配？解：关于M1,a,b,e,d是饱和点f,c是非饱和点M1

19、不是完美匹配M2是完美匹配，所以M2中a,b,c,d,e,f都是饱和点。12设G=V1,V2,E是二部图，M是G的一个匹配，如果对G的任意匹配M′，都有

20、M′

21、≤

22、M

23、，则M为G的最大匹配为了寻求二部图的最大匹配，以下引进交替通路和增长通路两个概念。定义设G=V1,V2,E是二部图，M是G的匹配，P是G中的一条路，如果P是由G中属于M的边和不属于M的边交替组成，则称P为G的M交替通路。如果交替通路的始点和终点都是M的非饱和点，则称为G的M增长通路。13例如，在图中匹配M={(a1,b2),(a2,b3),(a3,b5)}，路L1：a1b2

24、a2b3a3，L2：a2b3a3b5a4，L3：b1a3b5a4，L4：b1a1b2a2b3a3b5a4都是M的交替通路，其中后两条交替通路L3和L4的始点和终点都是M的非饱和点，所以这两条路是M增长通路。14设G=V1,V2,E是二部图，M是G的一个匹配，P是G中的一条M增长通路。把P中所有属于M的边从M中去掉，而把P中所有不属于M的边添加到M中，得到一个新的边集M′，则M′也是一个匹配，其所含边数比匹配M所含的边数多1。15例如在图中，把M增长通路L3：b1a3b5a4中属于M的边(a3,b5)从M中去掉，而把L3中不属于M的边(a3,b

25、1)和(a4,b5)添加到M中，得到一个新的边集M′=(a1,b2),(a2,b3),(a3,b1),(a4,b5)，显然M′也是匹配且M′的边数比M的边数多l，即

26、M′

27、＝

28、M

29、+1。16由此可见，利用增长通路可以增加匹配所含的边数。不断地寻求G的增长通路，直到再也找不到新的增长通路，就可得到一个最大匹配。将这个结论写成下列的定理。定理设G=V1,V2,E是二部图，M为G的最大匹配的充分必要条件是G中不存在M增长通路。证明：设M为G的最大匹配，下证G中不存在M可扩路。如果G中存在一条M可扩路，则可以得到比M的边数多1的匹配，所以M不是最

30、大匹配，矛盾。所以G中不存在M可扩路。设G中不存在M可扩路，下证M为G的最大匹配。设M1是最大匹配，证明

31、M

32、=

33、M1

34、。考察属于M而不