[工学]图论 的配对问题ppt课件

1、f1f2m1f3f4f5m2m3m4m5f1f2m1f3f4f5m2m3m4m5(f1,m3), (f2,m1) ,(f3,m2) ,(f4,m5) ,(f5,m4)f1f2m1f3f4f5m2m3m4m5f1f2m1f3f4f5m2m3m4m5M=(f1,m2),(f2,m1),(f3,m4),(f4,m5)f1f2m1f3f4f5m2m3m4m5M=(f1,m3), (f2,m1) ,(f3,m2) ,(f4,m5) ,(f5,m4)M=(f1,m3), (f2,m1) ,(f3,m2) ,(f5,m5)f1f2m1f3f4f5m2m3m4m5M=(f1,m3), (f2,m1) ,(f3

2、,m2) ,(f5,m5)f1f2m1f3f4f5m2m3m4m5饱和的饱和的不饱和不饱和的的f1f2m1f3f4f5m2m3m4m5M=(f1,m3),(f2,m1) ,(f3,m2) ,(f4,m5) ,(f5,m4)P=f1m3f4m5f2m1f5m4M=(f2,m5), (f3,m2) ,(f4,m3) ,(f5,m4)P=m1f2m5f4m3f1 是一条可增广道路。f1f2m1f3f4f5m2m3m4m5f1f2m1f3f4f5m2m3m4m5f1f2m1f3f4f5m2m3m4m5M=(f2,m5), (f3,m2) ,(f4,m3) ,(f5,m4)P=m1f2m5f4m3f1

3、是一条可增广道路。f1f2m1f3f4f5m2m3m4m5M=(f1,m3), (f2,m1) ,(f3,m2) ,(f4,m5),(f5,m4)M=(f1,m3), (f2,m1) ,(f3,m2) ,(f5,m5)f1f2m1f3f4f5m2m3m4m5引理引理设设P是匹配是匹配-可增广道路，那么可增广道路，那么PM是一个比是一个比M更更大的匹配，且大的匹配，且| PM|M|+1.定理定理1 (Berge) 设设G=(V,E)，M为为G中匹配，那么中匹配，那么 M为为G的的最大匹配当且仅当最大匹配当且仅当G中不存在中不存在 M可增广道。可增广道。 证明证明 必要性：如有必要性：如有M-可增

4、广道路，那么有更大匹配。矛可增广道路，那么有更大匹配。矛盾！盾！充分性充分性 ：假设有最大匹配：假设有最大匹配M, |M|M|. 思索思索MM，在 可增广路中，第一条边与最后一条边都不是 中的边，因此 可增广路中属于 的边数比不在 中边数少一条。MMMMMM实线边，M虚线边MM其中每个结点的最多与边和一个其中每个结点的最多与边和一个M边关联，每条道路是边关联，每条道路是M边和边和M边交互道路。边交互道路。其中回路包含一样数目的其中回路包含一样数目的M边和边和M边。由边。由|M|M|, 必存在必存在M边开场，边开场， M边终止的边终止的M交互道路，即交互道路，即M-可增广道路，矛盾！可增广道路，

5、矛盾！w1w2m1w3w4w5m2m3m4w1w2m1w3w4w5m2m3m4w1w2m1w3w4w5m2m3m4YXx1x2y1x3x4x5y2y3y4y5x1x2y1x3x4x5y2y3y4y5M=(x1,y1 ),(x3,y5),(x5,y3)x1x2y1x3x4x5y2y3y4y5M=(x1,y1 ),(x3,y5),(x5,y3)x1x2y1x3x4x5y2y3y4y5M=(x1,y1 ),(x3,y5),(x5,y3)x1x2y1x3x4x5y2y3y4y5M=(x1,y1 ),(x3,y5),(x5,y3)x1x2y1x3x4x5y2y3y4y5M=(x1,y1 ),(x3,y5

6、),(x5,y3)x1x2y1x3x4x5y2y3y4y5M=(x1,y1 ),(x3,y5),(x5,y3)x1x2y1x3x4x5y2y3y4y5M=(x1,y1 ),(x3,y5),(x5,y3)x1x2y1x3x4x5y2y3y4y5x1x2y1x3x4x5y2y3y4y5M=M E(P)=(x1,y1 ),(x2,y3),(x3,y2),( x5,y5)x1x2y1x3x4x5y2y3y4y5M=(x1,y1 ),(x2,y3),(x3,y2),( x5,y5)x1x2y1x3x4x5y2y3y4y5M=(x1,y1 ),(x2,y3),(x3,y2),( x5,y5)x1x2y1x

7、3x4x5y2y3y4y5M=(x1,y1 ),(x2,y3),(x3,y2),( x5,y5)x1x2y1x3x4x5y2y3y4y5M=(x1,y1 ),(x2,y3),(x3,y2),( x5,y5)x1x2y1x3x4x5y2y3y4y5M=(x1,y1 ),(x2,y3),(x3,y2),( x5,y5)x1x2y1x3x4x5y2y3y4y5M=(x1,y1 ),(x2,y3),(x3,y2),( x5,y5)x1x2y1x3x4x5y2y3y4y5M=(x1,y1 ),(x2,y3),(x3,y2),( x5,y5)x1x2y1x3x4x5y2y3y4y5M=(x1,y1 ),(

8、x2,y3),(x3,y2),( x5,y5)x1x2y1x3x4x5y2y3y4y5x1x2y1x3x4x5y2y3y4y5M=M E(P)=(x1,y1 ),(x2,y2),(x3,y5),( x4,y3 ),(x5,y4)x1x2y1x3x4x5y2y3y4y5 这时，M=(x1,y1 ),(x2,y2),(x3,y5),( x4,y3 ),(x5,y4)就是所求的最大匹配。x1x2y1x3x4x5y2y3y4y53 5 5 4 12 2 0 2 22 4 4 1 00 1 1 0 01 2 1 3 3 C=x1x2x3x4x5y1 y2 y3 y4 y5x1x2y1x3x4x5y2y3

9、y4y53 5 5 4 12 2 0 2 22 4 4 1 00 1 1 0 01 2 1 3 3 C=x1x2x3x4x5y1 y2 y3 y4 y5l(x1)=5l(x2)=2l(x3)=4l(x4)=1l(x5)=3l(y5)=0l(y1)=0l(y2)=0l(y3)=0l(y4)=0 x1x2y1x3x4x5y2y3y4y5x1x2y1x3x4x5y2y3y4y5y4x1x2y1x3x4x5y2y3y4y53 5 5 4 12 2 0 2 22 4 4 1 00 1 1 0 01 2 1 3 3 C=x1x2x3x4x5y1 y2 y3 y4 y5x1x2y1x3x4x5y2y3y4y

10、53 5 5 4 12 2 0 2 22 4 4 1 00 1 1 0 01 2 1 3 3 C=x1x2x3x4x5y1 y2 y3 y4 y5l(x1)=5l(x2)=2l(x3)=4l(x4)=1l(x5)=3l(y5)=0l(y1)=0l(y2)=0l(y3)=0l(y4)=0M=(x1,y2), (x2,y1), (x3,y3), (x5,y5)x1x2y1x3x4x5y2y3y4y5x1x2y1x3x4x5y2y3y4y5x1x2y1x3x4x5y2y3y4y5l(x1)=5l(x2)=2l(x3)=4l(x4)=1l(x5)=3l(y5)=0l(y1)=0l(y2)=0l(y3)

11、=0l(y4)=0M=(x1,y2), (x2,y1), (x3,y3), (x5,y5)V1=x4,V2=空集x1x2y1x3x4x5y2y3y4y5l(x1)=5l(x2)=2l(x3)=4l(x4)=1l(x5)=3l(y5)=0l(y1)=0l(y2)=0l(y3)=0l(y4)=0M=(x1,y2), (x2,y1), (x3,y3), (x5,y5)V1=x4,V2=x1x2y1x3x4x5y2y3y4y5l(x1)=5l(x2)=2l(x3)=4l(x4)=1l(x5)=3l(y5)=0l(y1)=0l(y2)=0l(y3)=0l(y4)=0M=(x1,y2), (x2,y1),

12、 (x3,y3), (x5,y5)V1=x4,x3,V2=y3x1x2y1x3x4x5y2y3y4y5l(x1)=5l(x2)=2l(x3)=4l(x4)=1l(x5)=3l(y5)=0l(y1)=0l(y2)=0l(y3)=0l(y4)=0M=(x1,y2), (x2,y1), (x3,y3), (x5,y5)V1=x4,x3,V2=y3x1x2y1x3x4x5y2y3y4y5l(x1)=5l(x2)=2l(x3)=4l(x4)=1l(x5)=3l(y5)=0l(y1)=0l(y2)=0l(y3)=0l(y4)=0M=(x1,y2), (x2,y1), (x3,y3), (x5,y5)V1=

13、x4,x3,x1,V2=y3,y2x1x2y1x3x4x5y2y3y4y5l(x1)=5l(x2)=2l(x3)=4l(x4)=1l(x5)=3l(y5)=0l(y1)=0l(y2)=0l(y3)=0l(y4)=0M=(x1,y2), (x2,y1), (x3,y3), (x5,y5)V1=x4,x3,x1,V2=y3,y2,3 5 5 4 12 2 0 2 22 4 4 1 00 1 1 0 01 2 1 3 3 C=x1x2x3x4x5y1 y2 y3 y4 y5=1NG(V1)=y1,y2,y3,y4,y5x1x2y1x3x4x5y2y3y4y5l(x1)=5l(x2)=2l(x3)=4

14、l(x4)=1l(x5)=3l(y5)=0l(y1)=0l(y2)=0l(y3)=0l(y4)=0M=(x1,y2), (x2,y1), (x3,y3), (x5,y5)V1=x4,x3,x1,V2=y3,y2=1l(x1)=4l(x3)=3l(x4)=0l(y2)=1l(y3)=1x1x2y1x3x4x5y2y3y4y5l(x1)=4l(x2)=2l(x3)=3l(x4)=0l(x5)=3l(y5)=0l(y1)=0l(y2)=1l(y3)=1l(y4)=0M=(x1,y2), (x2,y1), (x3,y3), (x5,y5)V1=x4,x3,x1,V2=y3,y23 5 5 4 12 2

15、 0 2 22 4 4 1 00 1 1 0 01 2 1 3 3 C=x1x2x3x4x5y1 y2 y3 y4 y5x1x2y1x3x4x5y2y3y4y5x1x2y1x3x4x5y2y3y4y5V1=x4,x3,x1,V2=y3,y2l(x1)=4l(x2)=2l(x3)=3l(x4)=0l(x5)=3l(y5)=0l(y1)=0l(y2)=1l(y3)=1l(y4)=0 x1x2y1x3x4x5y2y3y4y5M=(x1,y2), (x2,y1), (x3,y3), (x5,y5)M=(x1,y4), (x2,y1), (x3,y3), (x4,y4), (x5,y5),x1x2y1x

16、3x4x5y2y3y4y5M=(x1,y4), (x2,y1), (x3,y3), (x4,y4), (x5,y5),l(x1)=4l(x2)=2l(x3)=3l(x4)=0l(x5)=3l(y5)=0l(y1)=0l(y2)=1l(y3)=1l(y4)=0W=4+2+4+1+3=14x1x2y1x3x4x5y2y3y4y50 5 5 4 03 3 0 3 31 4 4 3 01 2 2 0 11 3 1 4 4 C=x1x2x3x4x5y1 y2 y3 y4 y5单星妖怪双星妖怪x1x2y1x3x4x5y2y3y4y5x1x2y1x3x4x5y2y3y4y5单星妖怪第一类图第一类图第二类图第

17、二类图目前仍无有效区分目前仍无有效区分(判别判别)任给定图属任给定图属第几类图的有效方法。第几类图的有效方法。内排完，且每节课所用教室数内排完，且每节课所用教室数？n 1 i p maxEiip1 lplplpElpin且且 ,1 i p 。pMpi提出条件时，断定课表的存在性问题是个NP-complete问题。甚至当G为简单偶图，且学生不提出要求的情况下，也是如此。x1x2y1x3x4x5y2y3y4y5v1v2v3v4v5v7v6v1v2v3v4v5v7v6C1=c1C2=c1,c2C3=c1,c2,c3C4=c1,c2,c3,c4C5=c1,c2,c3,c4,c5C6=c1,c2,c3,

18、c4,c5,c6C7=c1,c2,c3,c4,c5,c6,c7C1=c1C2=c1,c2C3=c1,c2,c3C4=c1,c2,c3,c4C5=c1,c2,c3,c4,c5C6=c1,c2,c3,c4,c5,c6C7=c1,c2,c3,c4,c5,c6,c7v1v2v3v4v5v7v6c1v1v2v3v4v5v7v6c1C1=c1C2=c1,c2C3=c1,c2,c3C4=c1,c2,c3,c4C5=c1,c2,c3,c4,c5C6=c1,c2,c3,c4,c5,c6C7=c1,c2,c3,c4,c5,c6,c7C2=c2 C3=c2, c3 C7=c2,c3,c4,c5,c6,c7 C5=c

19、2,c3,c4,c5 C6=c2,c3,c4,c5,c6 v1v2v3v4v5v7v6c1C1=c1C2=c2C3=c2,c3C4=c1,c2,c3,c4C5=c2,c3,c4,c5C6=c2,c3,c4,c5,c6C7=c2,c3,c4,c5,c6,c7c2v1v2v3v4v5v7v6c1C1=c1C2=c2C3=c2,c3C4=c1,c2,c3,c4C5=c2,c3,c4,c5C6=c2,c3,c4,c5,c6C7=c2,c3,c4,c5,c6,c7c2C3=c3 v1v2v3v4v5v7v6c1C1=c1C2=c2C3=c3C4=c1,c2,c3,c4C5=c2,c3,c4,c5C6=c2,c3,c4,c5,c6C7=c2,c3,c4,c5,c6,c7c2c3v1v2v3v4v5v7v6c1C1=c1C2=c2C3=c3C4=c1,c2,c3,c4C5=c2,c3,c4,c5C6=c2,c3,c4,c5,c6C7=c2,c3,c4,c5,c6,c7c2c3C5=c2,c4,c5 C1=c1,c2,c4 v1v2v3v4v5v7v6c1C1=c1C2=c2C3=c3C4=c1,c2,c4C5=c2,c4,c5C