【正文】 1）封鎖沒(méi)有畫框零元的行，封鎖就打 √； 2）在封鎖行中未畫框零元的列也封鎖； 3）在封鎖列中畫框零元的行也封鎖； 4）未封鎖行與封鎖列畫上覆蓋線。 可行頂點(diǎn)標(biāo)號(hào)法： 矩陣覆蓋法： 分枝定界法： 二部圖的匹配及其應(yīng)用 河南城建學(xué)院 矩陣覆蓋法： STEP1：求等價(jià)分配矩陣。 匈亞利算法： 0 4 4 * * 2 3 ⑦ 去掉 x1的標(biāo)記 *, 因?yàn)榕c x1鄰接的兩個(gè)點(diǎn) y2, y3都有標(biāo)號(hào) 4, 所以去掉 x3的標(biāo)記 *. 而與 x3鄰接的兩個(gè)點(diǎn) y2, y3也都有標(biāo)號(hào) 4, 此時(shí) X中所有有標(biāo)號(hào)的點(diǎn)都已去掉了標(biāo)記 *(如下圖所示 ), 因此 M1是 G的最大匹配 .沒(méi)有完美匹配。 匈亞利算法： 0 0 * 1 1 * 2 3 * ④ 去掉 x2的標(biāo)記 *, 將與 x2鄰接且尚未給標(biāo)號(hào)的三個(gè)點(diǎn) y1, y4, y5都給以標(biāo)號(hào) 2. 2 2 2 二部圖的匹配及其應(yīng)用 河南城建學(xué)院 例 18：求下圖的最大匹配。 河南城建學(xué)院 工作安排問(wèn)題之一 給 n個(gè)工作人員 x1, x2, … , xn安排 n項(xiàng)工作 y1, y2, … , yn. n個(gè)工作人員中每個(gè)人能勝任一項(xiàng)或幾項(xiàng)工作 , 但并 不是所有工作人員都能從事任何一項(xiàng)工作 . 比如 x1能做 y1, y2工作 , x2能做 y2, y3, y4工作等 . 這樣便提出一個(gè)問(wèn)題 , 對(duì)所有的工作人員能不能都分配一件他所能勝任的工作？ 二部圖的匹配及其應(yīng)用 河南城建學(xué)院 我們構(gòu)造一個(gè)二部圖 G = ( X, Y, E ), 這里 X = {x1, x2, … , xn},Y = { y1, y2, … , yn}, 并且當(dāng)且僅當(dāng)工作人員 xi勝任工作 yj時(shí) , xi與 yj才相鄰 . 于是 , 問(wèn)題轉(zhuǎn)化為求二部圖的一個(gè)完美匹配 . 因?yàn)? |X|=|Y|, 所以完美匹配即為最大匹配 . 二部圖的匹配及其應(yīng)用 河南城建學(xué)院 1x 2x 3x 4x 5x1y 2y 3y 4y 5y例 18：求下圖完美匹配 Hungarian算法： ? ? 時(shí)終止。 河南城建學(xué)院 2. 問(wèn)題求解： 顯然可以看出 ,上圖是一個(gè)連通無(wú)向圖，記為Ｇ＝｛Ｖ，Ｅ｝ . 任取 vi ∈ V(i=1,2, ……,10) ，考察 vi與Ｖ中其他頂點(diǎn)間的最短路（也稱為距離）：Ｐ ＊ （ vi， v１ ），Ｐ ＊ （ vi，v2）， …… ，Ｐ ＊ （ vi， v１０ ），把這 10個(gè)距離中最大的數(shù)稱為頂 vi的最大服務(wù)距離，記為 L(vi). 求出上圖中各點(diǎn)間的距離，如下表所示，這樣就可以把每個(gè)頂點(diǎn) vi對(duì)應(yīng)的最大服務(wù)距離 L(vi)求出來(lái) . 最短路徑問(wèn)題實(shí)例： 醫(yī)院選址問(wèn)題 河南城建學(xué)院 最短路徑問(wèn)題實(shí)例 ： 醫(yī)院選址問(wèn)題 1 2 3 4 5 6 7 8 9 10 1 0 5 3 6 5 10 10 9 12 13 2 5 0 2 3 4 9 6 8 8 9 3 3 2 0 3 2 7 7 6 9 10 4 6 3 3 0 5 7 5 6 7 8 5 5 4 2 5 0 5 5 4 7 8 6 10 9 7 7 5 0 2 1 4 5 7 10 6 7 5 5 2 0 1 2 3 8 9 8 6 6 4 1 1 0 3 4 9 12 8 9 7 7 4 2 3 0 5 10 13 9 10 8 8 5 3 4 5 0 河南城建學(xué)院 最短路徑問(wèn)題實(shí)例 ： 醫(yī)院選址問(wèn)題 注：上表中的１，２，３，４，５，６，７，８，９，１０分別代表 v1， v２ ， v３ ， v４ ， v５ ， v６ ， v７ ， v８ ， v９ ， v１０ v1到各頂點(diǎn)的距離就是上表中的第一行各數(shù)，它們中最大的是 13，所以 L(v1)=13，其它各點(diǎn)的最大服務(wù)距離分別為 : L(v2)=9， L(v3)=10， L(v4)=8， L(v5)=8 ， L(v6)=10 ， L(v7)=10， L(v8)=9 ， L(v9)=12， L(v10)=13。 若有 ，則對(duì) p點(diǎn)標(biāo)號(hào)； （４）重復(fù)第三步，一直到 t點(diǎn)得到標(biāo)號(hào)為止。 設(shè) G為賦權(quán)有向圖或無(wú)向圖， G邊上的權(quán)均非負(fù)。如選址、管道鋪設(shè) 時(shí)的選線、設(shè)備更新、投資等都可以歸給為求最短路的 問(wèn)題。3e任取一條邊 會(huì)與已選邊構(gòu)成圈 ,故停止 ,得 中選取在中選取 ,7e 中選取 . 但 與 都 }, 86 ee 84,ee 4e 8e},{ 876432 eeeeee},{ 87642 eeeee,{ 42 ee在河南城建學(xué)院 B 破圈法 任取一個(gè)圈，從圈中去掉一條權(quán)最大的邊（如果有兩條或兩條以上的邊都是權(quán)最大的邊，則任意去掉其中一條）。所以希望有一個(gè)方法以獲得相當(dāng)好（但不一定最優(yōu)）的解。如何為他設(shè)計(jì)一條最短的旅行路線（從駐地出發(fā)，經(jīng)過(guò)每個(gè)城市恰好一次，最后返回駐地）？這個(gè)問(wèn)題稱為旅行商問(wèn)題。 ? 上述中國(guó)郵遞員問(wèn)題的數(shù)學(xué)模型是：在一個(gè)賦權(quán)連通圖上求一個(gè)含所有邊的回路，且使此回路的權(quán)最小。 ? 2. 假設(shè)跡 Wi=v0e1v1…eivi 已經(jīng)選定，那么按下述方法從 E{e1, … ,ei}中選取邊 ei+1： 河南城建學(xué)院 ? （ i） ei+1和 vi相關(guān)聯(lián)； ? （ ii）除非沒(méi)有別的邊可選擇，否則 ei+1不是Gi=G {e1, … ,ei}的割邊 (cut edge)。 河南城建學(xué)院 ? 定義 包含 G的每個(gè)頂點(diǎn)的軌叫做 Hamilton(哈密頓 )軌 ；閉的 Hamilton軌叫做 Hamilton圈或 H圈 ；含 Hamilton圈的圖叫做 Hamilton圖 。 但是如何乘船渡河的大權(quán)掌握在商人們 手中 。 可用圖表示為 河南城建學(xué)院 河南城建學(xué)院 實(shí)例三 循環(huán)比賽的名次 問(wèn)題 n支球隊(duì)循環(huán)比賽 ， 每場(chǎng)只計(jì)勝負(fù) ， 沒(méi)有平局 . 根據(jù)比賽結(jié)果排出各隊(duì)名次 .圖 （ 1） 給出了 6支 球隊(duì)的比賽結(jié)果 ， 即 1隊(duì)?wèi)?zhàn)勝 6隊(duì) ， 而 輸給了 3隊(duì)； 5隊(duì)?wèi)?zhàn)勝 6隊(duì) ， 而輸給了 4 隊(duì)等等 . 河南城建學(xué)院 循環(huán)比賽的名次 方法 1：尋找按箭頭方向通過(guò)全部頂點(diǎn)的路徑 . 312456 146325 …… ?無(wú)法排名 方法 2：計(jì)算得分： 1隊(duì)勝 4場(chǎng) ， 2， 3隊(duì)各勝 3 場(chǎng) ， 4， 5隊(duì)各勝 2場(chǎng) ， 6隊(duì)勝 1場(chǎng) .2， 3 隊(duì) ， 4， 5隊(duì)無(wú)法排名 .3→ 2， 4→ 5? 排名 132456合理嗎 ？ 用圖論的知識(shí)可以解決這個(gè)問(wèn)題 . 河南城建學(xué)院 循環(huán)比賽的名次 競(jìng)賽圖及其性質(zhì) 循環(huán)比賽的結(jié)果 —— 競(jìng)賽圖：每對(duì)頂點(diǎn)之間都有 一條邊相連的有向圖 .名次是由出度由大到小排序 。 河南城建學(xué)院 現(xiàn)在用狀態(tài)運(yùn)算來(lái)完成狀態(tài)轉(zhuǎn)移 。 河南城建學(xué)院 握手的次數(shù) 要知道史密斯太太和別人握手的次數(shù) ， 只需確定除史 密斯先生外的 9人中哪一個(gè)是史密斯太太即可 。 ? 每個(gè)人都不會(huì)跟同一個(gè)人握手兩次 —— 兩個(gè)人間的握手最多是一次 。 之后 ， 史密斯先生問(wèn)每個(gè)人和別人握了幾 次手 ， 他們的答案都不一樣 。 (4) 連通的無(wú)圈圖稱為 樹(shù) 。 河南城建學(xué)院 定義 3 (1) 設(shè) 是賦權(quán)圖 G中從 u到 v的路徑 ， 則稱 為 路徑 P的權(quán) 。 (4)若子圖 G?無(wú)孤立點(diǎn)且 G?由 E?唯一確定，則稱 G?是 由邊集E?導(dǎo)出的子圖 ； (5)若對(duì)子圖 G?=?V?,E??中任二頂點(diǎn) u,v,(u,v)?E ?(u,v)?E?，則 稱 G?是 由頂點(diǎn)集 V?導(dǎo)出的子圖 (易見(jiàn) :V?導(dǎo)出的子圖 G?是以 V?為其頂點(diǎn)集 ,所有在 G中同時(shí)關(guān)聯(lián)于V?中兩點(diǎn)的邊為其邊集 ). 圖的定義與記號(hào) 河南城建學(xué)院 圖的定義與記號(hào) 定義 3 : （ 1 ） 在無(wú)向圖中，與頂點(diǎn) v 關(guān)聯(lián)的邊數(shù)（環(huán)算 兩次）稱為 v 的 次數(shù)（度） ， 記為()dv。 ( 8) 若, V X Y X Y? ? ?， X 中任兩頂點(diǎn)不相鄰， Y 中任兩頂點(diǎn)不相鄰，稱 G 為 二部圖 ；若 X 中每一頂點(diǎn)都和Y 中一切頂點(diǎn)相鄰，稱為 完全二部圖 ，記為,nmK，其中 m ， n 分別為 X 與 Y 的頂點(diǎn)數(shù)。 (4)不與任何結(jié)點(diǎn)鄰接的頂點(diǎn)稱為孤立點(diǎn)，全為孤立點(diǎn)組成的圖 (無(wú)向圖和有向圖均可 )稱為空?qǐng)D。 2．圖的定義與記號(hào) 定義 1 （ 1 ） 圖 G 是一個(gè)二重組： G= （ V ， E ），其中V =12{ , , , }nv v v是非空有限集合，稱為頂點(diǎn)集，它的元素稱為圖 G 的頂點(diǎn)； E 也是 ( 可空 ) 有限集合 ， 稱為邊集，它的元素稱為圖 G 的邊。假定個(gè)產(chǎn)地的產(chǎn)量和家工廠的需要量已知，單位產(chǎn)品從任一產(chǎn)地到任一工廠的運(yùn)費(fèi)已知，那么如何安排運(yùn)輸方案可以使總運(yùn)輸成本最低？ 河南城建學(xué)院 ? 上述問(wèn)題有兩個(gè)共同的特點(diǎn)： 一是它們的目的都是從若干可能的安排或方案中尋求某種意義下的最優(yōu)安排或方案，數(shù)學(xué)上把這種問(wèn)題稱為最優(yōu)化或優(yōu)化（ optimization）問(wèn)題；二是它們都易于用圖形的形式直觀地描述和表達(dá)，數(shù)學(xué)上把這種與圖相關(guān)的結(jié)構(gòu)稱為（ work）。如何為他（她）設(shè)計(jì)一條最短的投遞路線（從郵局出發(fā)，經(jīng)過(guò)投遞區(qū)內(nèi)每條街道至少一次，最后返回郵局）？由于這一問(wèn)題是我國(guó)管梅谷教授 1960年首先提出的，所以國(guó)際上稱之為中國(guó)郵遞員問(wèn)題。 河南城建學(xué)院 ? 例 2 公路連接問(wèn)題 ? 某一地區(qū)有若干個(gè)主要城市，現(xiàn)準(zhǔn)備修建高速公路把這些城市連接起來(lái)，使得從其中任何一個(gè)城市都可以經(jīng)高速公路直接或間接到達(dá)另一個(gè)城市。 圖論簡(jiǎn)介 Konigsberg 七橋問(wèn)題 是否可以 一筆畫？ A B D C D C A B 河南城建學(xué)院 1 概論 圖與網(wǎng)絡(luò)是運(yùn)籌學(xué)（ Operations Research）中的一個(gè)經(jīng)典和重要的分支，所研究的問(wèn)題涉及經(jīng)濟(jì)管理、工業(yè)工程、交通運(yùn)輸、計(jì)算機(jī)科學(xué)與信息技術(shù)、通訊與網(wǎng)絡(luò)技術(shù)等諸多領(lǐng)域。第一篇圖論論文是瑞士數(shù)學(xué)家歐拉于 1736 年發(fā)表的“哥尼斯堡的七座橋”。 1 概論 ? 圖論起源于 18世紀(jì)。哈密爾頓于 1859年提出“周游世界”游戲，用圖論的術(shù)語(yǔ)，就是如何找出一個(gè)連通圖中的生成圈，