图论-的配对问题课件

第五章匹配第五章匹配1§1匹配具体问题描述有n个女士和n个男士参加舞会,每位女士与其中若干位男士相识,每位男士与其中若干位女士相识,问如何安排,使得尽量多配对的男女舞伴相识f§1匹配2下图就是一种分配方法:(f1m3),(f2m),(f3,m2),(f4m5)(f5m下图就是一种分配方法:3匹配问题是运筹学的重要问题之一,也是图论的重要内容,它在所谓“人员分配问题”和“最优分配问题”中有重要作用。假定有一个男生有穷集合,其中每个男生认识一些女生,在什么条件下每个男生都可以和他认识的女生配对?口类似的工作分配问题:现有n个人,m份工作,每个人有其擅长的工作。在什么条件下每个人都可以得到一份他擅长的工作?如何分配?匹配问题是运筹学的重要问题之一,也是图论的重要4定义:若图G=(,E的顶点可以分成X,Y两个子集,每个子集里的顶点互不相邻,这样的图称为二分图。定义:若图G=(,E的顶点可以分成X,Y两5定义:若Ⅵ是图G=(,F的边子集,且M的任意两条边在G中不相邻,则称M为G中的一个匹配,M中的每条边的两个端点称为是M饱和的的。M={(f1m2)2,m1),f3,m),(f4,ms)}定义:若Ⅵ是图G=(,F的边子集,且M6定义:若图G中每个顶点均被M许配时,称M为G中的一个完美匹配。M={(f1m3),(f2m1),(f3,m2),(f4,ms),(f5,m)}定义:若图G中每个顶点均被M许配时,称7定义:图G中边数最多的匹配M,称为G中的一个最大匹配。M={f1m3),(f2,m),(f3,m2),(f51m5)}定义:图G中边数最多的匹配M,称为G中8定义:若匹配M的某边和顶点v关联,称v是M饱和的,否则就是M不饱和的饱和的M={(1mn3,、(2m),(5,m2)、(5m3)不饱和定义:若匹配M的某边和顶点v关联,称v是9定义:若M是图G的一个匹配,若从G中个顶点到另一个顶点存在一条道路,此路径由属于M和不属于M的边交替出现组成的,刂称此路径为M交错路。M={(f1m3),(f2,m1),(f2,m2),(f4m5),(f,m)}P=f,mfgmf,m,fsm定义:若M是图G的一个匹配,若从G中10图论-的配对问题课件11图论-的配对问题课件12图论-的配对问题课件13图论-的配对问题课件14图论-的配对问题课件15图论-的配对问题课件16图论-的配对问题课件17图论-的配对问题课件18图论-的配对问题课件19图论-的配对问题课件20图论-的配对问题课件21图论-的配对问题课件22图论-的配对问题课件23图论-的配对问题课件24图论-的配对问题课件25图论-的配对问题课件26图论-的配对问题课件27图论-的配对问题课件28图论-的配对问题课件29图论-的配对问题课件30图论-的配对问题课件31图论-的配对问题课件32图论-的配对问题课件33图论-的配对问题课件34图论-的配对问题课件35图论-的配对问题课件36图论-的配对问题课件37图论-的配对问题课件38图论-的配对问题课件39图论-的配对问题课件40图论-的配对问题课件41图论-的配对问题课件42图论-的配对问题课件43图论-的配对问题课件44图论-的配对问题课件45图论-的配对问题课件46图论-的配对问题课件47图论-的配对问题课件48图论-的配对问题课件49图论-的配对问题课件50图论-的配对问题课件51图论-的配对问题课件52图论-的配对问题课件53图论-的配对问题课件54图论-的配对问题课件55图论-的配对问题课件56图论-的配对问题课件57图论-的配对问题课件58图论-的配对问题课件59图论-的配对问题课件60图论-的配对问题课件61图论-的配对问题课件62图论-的配对问题课件63图论-的配对问题课件64图论-的配对问题课件65图论-的配对问题课件66图论-的配对问题课件67图论-的配对问题课件68图论-的配对问题课件69图论-的配对问题课件70图论-的配对问题课件71图论-的配对问题课件72图论-的配对问题课件73图论-的配对问题课件74图论-的配对问题课件75图论-的配对问题课件76图论-的配对问题课件77图论-的配对问题课件78图论-的配对问题课件79图论-的配对问题课件80图论-的配对问题课件81图论-的配对问题课件82图论-的配对问题课件83图论-的配对问题课件84图论-的配对问题课件85图论-的配对问题课件86图论-的配对问题课件87图论-的配对问题课件88图论-的配对问题课件89图论-的配对问题课件90图论-的配对问题课件91图论-的配对问题课件92图论-的配对问题课件93图论-的配对问题课件94图论-的配对问题课件95图论-的配对问题课件96图论-的配对问题课件97图论-的配对问题课件98图论-的配对问题课件99图论-的配对问题课件100图论-的配对问题课件101图论-的配对问题课件102第五章匹配第五章匹配103§1匹配具体问题描述有n个女士和n个男士参加舞会,每位女士与其中若干位男士相识,每位男士与其中若干位女士相识,问如何安排,使得尽量多配对的男女舞伴相识f§1匹配104下图就是一种分配方法:(f1m3),(f2m),(f3,m2),(f4m5)(f5m下图就是一种分配方法:105匹配问题是运筹学的重要问题之一,也是图论的重要内容,它在所谓“人员分配问题”和“最优分配问题”中有重要作用。假定有一个男生有穷集合,其中每个男生认识一些女生,在什么条件下每个男生都可以和他认识的女生配对?口类似的工作分配问题:现有n个人,m份工作,每个人有其擅长的工作。在什么条件下每个人都可以得到一份他擅长的工作?如何分配?匹配问题是运筹学的重要问题之一,也是图论的重要106定义:若图G=(,E的顶点可以分成X,Y两个子集,每个子集里的顶点互不相邻,这样的图称为二分图。定义:若图G=(,E的顶点可以分成X,Y两107定义:若Ⅵ是图G=(,F的边子集,且M的任意两条边在G中不相邻,则称M为G中的一个匹配,M中的每条边的两个端点称为是M饱和的的。M={(f1m2)2,m1),f3,m),(f4,ms)}定义:若Ⅵ是图G=(,F的边子集,且M108定义:若图G中每个顶点均被M许配时,称M为G中的一个完美匹配。M={(f1m3),(f2m1),(f3,m2),(f4,ms),(f5,m)}定义:若图G中每个顶点均被M许配时,称109定义:图G中边数最多的匹配M,称为G中的一个最大匹配。M={f1m3),(f2,m),(f3,m2),(f51m5)}定义:图G中边数最多的匹配M,称为G中110定义:若匹配M的某边和顶点v关联,称v是M饱和的,否则就是M不饱和的饱和的M={(1mn3,、(2m),(5,m2)、(5m3)不饱和定义:若匹配M的某边和顶点v关联,称v是111定义:若M是图G的一个匹配,若从G中个顶点到另一个顶点存在一条道路,此路径由属于M和不属于M的边交替出现组成的,刂称此路径为M交错路。M={(f1m3),(f2,m1),(f2,m2),(f4m5),(f,m)}P=f,mfgmf,m,fsm定义:若M是图G的一个匹配,若从G中112图论-的配对问题课件113图论-的配对问题课件114图论-的配对问题课件115图论-的配对问题课件116图论-的配对问题课件117图论-的配对问题课件118图论-的配对问题课件119图论-的配对问题课件120图论-的配对问题课件121图论-的配对问题课件122图论-的配对问题课件123图论-的配对问题课件124图论-的配对问题课件125图论-的配对问题课件126图论-的配对问题课件127图论-的配对问题课件128图论-的配对问题课件129图论-的配对问题课件130图论-的配对问题课件131图论-的配对问题课件132图论-的配对问题课件133图论-的配对问题课件134图论-的配对问题课件135图论-的配对问题课件136图论-的配对问题课件137图论-的配对问题课件138图论-的配对问题课件139图论-的配对问题课件140图论-的配对问题课件141图论-的配对问题课件142图论-的配对问题课件143图论-的配对问题课件144图论-的配对问题课件145图论-的配对问题课件146图论-的配对问题课件147图论-的配对问题课件148图论-的配对问题课件149图论-的配对问题课件150图论-的配对问题课件151图论-的配对问题课件152图论-的配对问题课件153图论-的配对问题课件154图论-的配对问题课件155图论-的配对问题课件156图论-的配对问题课件157图论-的配对问题课件158图论-的配对问题课件159图论-的配对问题课件160图论-的配对问题课件161图论-的配对问题课件162图论-的配对问题课件163图论-的配对问题课件164图论-的配对问题课件165图论-的配对问题课件166图论-的配对问题课件167图论-的配对问题课件168图论-的配对问题课件169图论-的配对问题课件170图论-的配对问题课件171图论-的配对问题课件172图论-的配对问题课件173图论-的配对问题课件174图论-的配对问题课件175图论-的配对问题课件176图论-的配对问题课件177图论-的配对问题课件178图论-的配对问题课件179图论-的配对问题课件180图论-的配对问题课件181图论-的配对问题课件182图论-的配对问题课件183图论-的配对问题课件184图论-的配对问题课件185图论-的配对问题课件186图论-的配对问题课件187图论-的配对问题课件188图论-的配对问题