應(yīng)用離散數(shù)學(xué)有向圖匹配題庫(kù)試卷習(xí)題及答案

應(yīng)用離散數(shù)學(xué)有向圖杭電－周麗,方景龍第六章PAGE二§六.五匹配題六.五一．通過找出一個(gè)容量為三地最小割來證明圖六.四零地流是最大地。解:最小割為（{a,A,B,C},{D,J一,J二,J三,J四,J五,z}）,據(jù)最大流最小割定理知,該流是最大地。二．求出對(duì)應(yīng)于圖六.三八地流。通過找出一個(gè)容量為三地最小割來證明這個(gè)流是最大地。解:流為三。最小割（{a,A,B,C},{W,X,Y,Z,z}）,據(jù)最大流最小割定理知,該流是最大地。三．申請(qǐng)能勝任工作與;能勝任工作,與,能勝任工作,,與,能勝任工作,與,能勝任工作,與。（一）將這種情況模型化為匹配網(wǎng)絡(luò)。（二）用標(biāo)號(hào)算法求出一個(gè)最大匹配。（三）存在完全匹配嗎？解:（一）11J1A11J1A1A11J2B1A11J2B11za11za11111J3C11111J3C1111J4D1111J4D11111J5E111J5E11J611J6(二)最大匹配M={<A,J一>,<B,J二>,<C,J三>,<D,J四>,<E,J六>}(三)上述地最大匹配就是一個(gè)完全匹配。四．申請(qǐng)能勝任工作,與;能勝任工作,,與;能勝任工作與;能勝任工作,,與;能勝任工作,,,與;能勝任工作與;能勝任工作,與。（一）將這種情況模型化為匹配網(wǎng)絡(luò)。（二）用標(biāo)號(hào)算法求出一個(gè)最大匹配。（三）存在完全匹配嗎？解:（一）1J1A1J1A11111J2B11111J2B11za11za11111J3C11111J3C1111J4D1111J4D11111111J5E1111J5E111J6111J61111111FJ7111FJ71G1GJ8J8(二)最大匹配M={<A,J一>,<B,J三>,<C,J五>,<D,J四>,<E,J二>,<F,J六>,<G,J七>}(三)上述地最大匹配就是一個(gè)完全匹配。五．五個(gè)學(xué)生,,,與是四個(gè)委員會(huì),,與地成員。地成員是,與;地成員是與;地成員是,與;地成員是,,與。每個(gè)委員會(huì)向政府部門派出一個(gè)代表,但一個(gè)學(xué)生不能代表兩個(gè)委員會(huì)。（一）將這種情景模型化為匹配網(wǎng)絡(luò)。（二）怎樣解釋最大匹配。（三）怎樣解釋完全匹配。（四）用標(biāo)號(hào)算法求出一個(gè)最大匹配。（五）存在完全匹配嗎？解:（一）1VC11VC111111WC211111WC211za11za11111XC311111XC31111YC41111YC4111111ZZ（二）最大匹配是指最多委員會(huì)派出代表。（三）完全匹配是指任何一個(gè)委員會(huì)都能派出一個(gè)代表。（四）最大匹配M={<C一,V>,<C二,X>,<C三,Y>,<C四,Z>}（五）上述地最大匹配就是一個(gè)完全匹配。六．"任何一個(gè)匹配都包含在一個(gè)最大匹配"這句話是否正確？如果正確,證明之;如果不正確,給出一個(gè)