[工学]图论-的配对问题课件.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,m2),(f5,m5)f

2、1f2m1f3f4f5m2m3m4m5饱和的饱和的不饱和不饱和的的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 是一条可增广道路。f1f2m1f3f4f5m2

3、m3m4m5M=(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|.考虑考虑M M，在 可增广路中，第一条边与最后一条边都不是 中的边，因而 可增广路中属于 的边数比不在 中边数少一条。MMMMMM实线边，M虚线边MM其中每个结点的最多与边和一个其中每个结点的最多与边和一个M边关联，每条道路是边关联，每条道路是M边和边和M边交互道路。边交互道路。其中回路包含相同数目的其中回路包含相同数目的M边和边和M边。由边。由|M|M|,必存必存在在M边开始，边开始，M边终止的边终止的M交互道路，即交互道路，即M-可增广道可增广道路，矛盾！路，矛盾！w1w2m1w3w4w5m2m3m4w1w2m1w3w4w5m2m3m4w1w2m1w3w4w5m2

5、m3m4YXx1x2y1x3x4x5y2y3y4y5x1x2y1x3x4x5y2y3y4y5M=(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),(x5,y3)x1x2y1x3x4x5y2y3y4y5M=(x1,y1),(x3,y5),(x5,y3)x1x2

6、y1x3x4x5y2y3y4y5M=(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)x1x2y1x3x4x5y2y3y4y5M=(x1,y1),(x2,y3),(x3,y2),(x5,y5)x1x2y1x3x4x5y2y3y4y5

7、M=(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)x1x2y1x3x4x5y2y3y4y5x1x2y1x3x4x5y2y3y4y5M=M E(P)=(x1,y1

8、),(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 y5x1x2y1x3x4x5y2y3y4y53 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

9、(x2)=2l(x3)=4l(x4)=1l(x5)=3l(y5)=0l(y1)=0l(y2)=0l(y3)=0l(y4)=0 x1x2y1x3x4x5y2y3y4y5x1x2y1x3x4x5y2y3y4y5x1x2y1x3x4x5y2y3y4y53 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 y5x1x2y1x3x4x5y2y3y4y53 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)=

10、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)=0l(y4)=0M=(x1,y2),(x2,y1),(x3,y3),(x5,y5)V1=x4,V2=空集x1x2y1x3x4x5y2y3y4y5l(x1)=5l(x2)=2l(

11、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),(x3,y3),(x5,y5)V1=x4,x3,V2=y3x1x2y1x3x4x5y2y3y4y5l(x1)=5l(x2)=2l(x3)=4l(x4)=1l(x5)=3l(y5)=0l(y1)

12、=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=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

13、)=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)=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=1l(x

14、1)=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 0 2 22 4 4 1 00 1 1 0 01 2 1 3 3 C=x1x2x3x4x5y1 y2 y3 y4 y5x1x2y1x3x4x5y2y3y4y5x1x2y1x3x4x5y2y3y4y5V1=x4,x3,x1,V

15、2=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),x1x2y1x3x4x5y2y3y4y5M=(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(

16、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单星妖怪第一类图第一类图第二类图第二类图目前仍无有效区分目前仍无有效区分(判别判别)任给定图属任给定图属第几类图的有效方法。第几类图的有效方法。np内排完，且每节课所用教室数？n（1 i p）maxEiip1 lplplpElpin p。pMpi提出条件时，判定

17、课表的存在性问题是个NP-complete问题。甚至当G为简单偶图，且学生不提出要求的情况下，也是如此。x1x2y1x3x4x5y2y3y4y5v1v2v3v4v5v7v6v1v2v3v4v5v7v6C1=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,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,c7v1v2

18、v3v4v5v7v6c1v1v2v3v4v5v7v6c1C1=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=c2,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,c7c2v1v2

19、v3v4v5v7v6c1C1=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,c7c

20、2c3C5=c2,c4,c5 C1=c1,c2,c4 v1v2v3v4v5v7v6c1C1=c1C2=c2C3=c3C4=c1,c2,c4C5=c2,c4,c5C6=c2,c3,c4,c5,c6C7=c2,c3,c4,c5,c6,c7c2c3c1v1v2v3v4v5v7v6c1C1=c1C2=c2C3=c3C4=c1,c2,c4C5=c2,c4,c5C6=c2,c3,c4,c5,c6C7=c2,c3,c4,c5,c6,c7c2c3c1v1v2v3v4v5v7v6c1C1=c1C2=c2C3=c3C4=c1,c2,c4C5=c2,c4,c5C6=c2,c3,c4,c5,c6C7=c2,c3,c4

21、,c5,c6,c7c2c3c1c2v1v2v3v4v5v7v6c1C1=c1C2=c2C3=c3C4=c1,c2,c4C5=c2,c4,c5C6=c2,c3,c4,c5,c6C7=c2,c3,c4,c5,c6,c7c2c3c1c2C6=c3,c4,c5,c6 v1v2v3v4v5v7v6c1C1=c1C2=c2C3=c3C4=c1,c2,c4C5=c2,c4,c5C6=c3,c4,c5,c6C7=c2,c3,c4,c5,c6,c7c2c3c1c2c3v1v2v3v4v5v7v6c1C1=c1C2=c2C3=c3C4=c1,c2,c4C5=c2,c4,c5C6=c3,c4,c5,c6C7=c2,c3,c4,c5,c6,c7c2c3c1c2C7=c2,c4,c5,c6,c7 c3v1v2v3v4v5v7v6c1C1=c1C2=c2C3=c3C4=c1,c2,c4C5=c2,c4,c5C6=c3,c4,c5,c6C7=c2,c4,c5,c6,c7c2c3c1c2c3c2