二分圖（英文：bipartite graph）又稱二部圖，是一類特殊的圖。其定義為：如果一個(gè)圖的頂點(diǎn)能分成兩個(gè)集合V1和V2，并使得同一集合中的任何兩個(gè)頂點(diǎn)都不鄰接，則稱此圖為二分圖。
圖論發(fā)展至今已有200多年的歷史，它最早起源于加里寧格勒七橋問題。1736年，瑞士數(shù)學(xué)家萊昂哈德·歐拉（Euler）在《關(guān)于位置幾何問題的解法》的論文中，對哥尼斯堡七橋問題進(jìn)行了論述，并將其形象地轉(zhuǎn)化為一筆畫問題，標(biāo)志著圖論的正式誕生。1878年，英國數(shù)學(xué)家西爾維斯特（Sylvester）在《自然》雜志上發(fā)表的著作《化學(xué)與代數(shù)》中首次使用了“圖”的數(shù)學(xué)術(shù)語。1914年，匈牙利數(shù)學(xué)家柯尼希（Koenig）在著作《關(guān)于集合的一般理論和圖論中的一個(gè)問題》中引入了二分圖的概念，并稱它為“偶回路圖”，后改稱為二部圖。1935年，英國數(shù)學(xué)家霍爾（Hall）在其論文《論子集的代表元》中提出了著名的霍爾定理，給出了二分圖存在完美匹配的充要條件。1957年，法國數(shù)學(xué)家貝爾熱（C.Berge）提出了圖存在最大匹配的充要條件，它可用于解決二分圖中的最大匹配問題。
二分圖有一些基本性質(zhì)，如所有回路長度均為偶數(shù)。二分圖可根據(jù)節(jié)點(diǎn)基數(shù)的大小進(jìn)行分類，它與子圖、完全圖等概念密切相關(guān)。二分圖的運(yùn)算有匹配、覆蓋、檢驗(yàn)二分性等，其中匹配可以通過匈牙利算法來求解。圖的每邊最多只有兩個(gè)頂點(diǎn)，如果推廣至任意個(gè)，可得到超圖的概念，二分圖與超圖之間可相互確定。此外，二分圖在現(xiàn)實(shí)世界中具有廣泛的應(yīng)用價(jià)值，如生物學(xué)中，融合多生物數(shù)據(jù)的二分圖聚類集成方法，能有效地處理蛋白質(zhì)功能重疊問題。
定義
二分圖：設(shè)和是圖的頂點(diǎn)子集，使，且的每一條邊的一個(gè)端點(diǎn)在中，另一個(gè)端點(diǎn)在中，則稱為二分圖，記作。
完全二分圖：如果中的頂點(diǎn)與的每個(gè)頂點(diǎn)都相連，則稱為完全二分圖。若(表示集合中元素的個(gè)數(shù)），則完全二分圖記作。
簡史
背景與起源
圖論發(fā)展至今已有200多年的歷史，它最早起源于加里寧格勒七橋問題。1736年，瑞士數(shù)學(xué)家萊昂哈德·歐拉（Euler）向圣彼得堡科學(xué)院提交了一篇名為《關(guān)于位置幾何問題的解法》的論文，在該論文中闡述了關(guān)于解決哥尼斯堡七橋的問題，并把該問題形象地轉(zhuǎn)化為一筆畫問題。該論文標(biāo)志著圖論的正式誕生，但其中并沒有涉及圖的概念，甚至不曾出現(xiàn)過現(xiàn)代意義的圖。后來，1878年，英國數(shù)學(xué)家西爾維斯特（Sylvester）在《自然》雜志上發(fā)表了著作《化學(xué)與代數(shù)》，首次使用了“圖”這一數(shù)學(xué)上的專門術(shù)語。
提出與發(fā)展
1914年，匈牙利數(shù)學(xué)家柯尼希（Koenig）在巴黎舉行的數(shù)學(xué)哲學(xué)大會(huì)上提交了著作《關(guān)于集合的一般理論和圖論中的一個(gè)問題》，引入了二分圖的概念，并且稱它為“偶回路圖”，后來受到圣·拉蓋（Saint Laggai）的著作影響而改用二部圖這一名稱。1935年，英國數(shù)學(xué)家霍爾（Hall）在論文《論子集的代表元》中提出了著名的霍爾定理，給出了二分圖存在完美匹配的充要條件。1957年，法國數(shù)學(xué)家貝爾熱（C.Berge）給出了圖存在最大匹配的充要條件，它可用于解決二分圖中的最大匹配問題。
舉例
例1 公用設(shè)施問題。代表住戶的節(jié)點(diǎn)作為一組，代表公共設(shè)施（如水廠、電廠、香港中華煤氣、電話公司等）的節(jié)點(diǎn)又是一組，兩組的節(jié)點(diǎn)之間有邊相連當(dāng)且僅當(dāng)對應(yīng)的用戶與公共設(shè)施之間存在隸屬關(guān)系，所得的圖為二分圖。
例2 人員分配問題。某公司分配個(gè)工人做件工作，就可以用一個(gè)二分圖來表示。代表人的一組頂點(diǎn)用表示，代表工作的一組用頂點(diǎn)表示。與相鄰當(dāng)且僅當(dāng)工人能做工作，所得圖是一個(gè)二分圖。
例3 鐵路優(yōu)化問題。一個(gè)輸入實(shí)例，如圖，其中列火車（左側(cè)）連接到各自的停靠站（右側(cè)）。
輸入：一個(gè)無向二分圖，具有不相交的點(diǎn)集和以及邊集。
任務(wù)：尋找最小的集合，使得中的每個(gè)頂點(diǎn)都有一條邊將它連接到中的某些頂點(diǎn)。
性質(zhì)
充要條件
（1）非平凡圖是二分圖當(dāng)且僅當(dāng)中不含有長為奇數(shù)的圈。
（2）當(dāng)且僅當(dāng)非空圖不含回路或每個(gè)回路長度為偶數(shù)時(shí)，是二分圖。
（3）圖是點(diǎn)可著色的當(dāng)且僅當(dāng)為二分圖。
（4）圖的譜是對稱的，當(dāng)且僅當(dāng)它是二分圖。
度
度：在圖中，與頂點(diǎn)關(guān)聯(lián)的邊的數(shù)目稱為在中的度，記作。
度序列：是設(shè)圖的頂點(diǎn)集為，則稱為的度數(shù)序列。
設(shè)二分圖的左、右部分的頂點(diǎn)的度數(shù)分別為和，那么
和
都等于邊數(shù)，因此
。
分類
按基數(shù)大小劃分
二分圖的節(jié)點(diǎn)可以分成兩個(gè)集合，二分圖的任意一條邊的端點(diǎn)分別在這兩個(gè)集合中。若二分圖的節(jié)點(diǎn)集劃分成的兩個(gè)子集為和，設(shè)基數(shù)較大者為，則可將二分圖分類如下：
（1）若，則稱圖為平衡的。
（2）若，則稱圖為準(zhǔn)平衡的。
（3）若，則稱圖為偏斜的。
相關(guān)概念
子圖
定義：設(shè)和是圖，如果，且中邊的重?cái)?shù)不能超過中對應(yīng)邊的重?cái)?shù)，則稱圖是的子圖，寫作。
導(dǎo)出子圖：設(shè)是圖的頂點(diǎn)集合的一個(gè)非空子集，以作為頂點(diǎn)集，以兩端點(diǎn)均在中的邊的全體為邊集的子圖，稱為由導(dǎo)出的的子圖，記為。
聯(lián)系：二分圖的任一子圖（頂數(shù)不少于）仍為二分圖。
完全圖
定義：任意兩個(gè)相異頂點(diǎn)都相鄰的簡單圖稱為完全圖，階完全圖記作。其中，有向完全圖的每對相同頂點(diǎn)間都有兩個(gè)相反方向的弧。無向完全圖的每一條邊都是無向邊，不含有平行邊和環(huán)，每一對頂點(diǎn)間都有邊相連。
聯(lián)系：完全圖可以被表示為個(gè)二分圖的并當(dāng)且僅當(dāng)。
完美圖
定義：圖稱為完美的，如果對任意誘導(dǎo)子圖成立，與此等價(jià)的說法為：對任意成立。
聯(lián)系：（1）二分圖構(gòu)成一個(gè)遺傳圖族，而且對于任意二分圖成立，因此二分圖都是完美的。
（2）二分圖的補(bǔ)圖、二分圖的線圖以及線圖的補(bǔ)圖都是完美的。
（3）根據(jù)強(qiáng)完美圖定理，二分圖的任何導(dǎo)出子圖是二分圖。
有向圖
定義：在一個(gè)圖中，若對每條邊都指定一個(gè)方向，則稱它為有向圖。
聯(lián)系：關(guān)于矩陣可約性中，通過利用鄰接矩陣，二分圖和有向圖之間存在一一對應(yīng)關(guān)系。設(shè)是一個(gè)階由和組成二元矩陣，它可以表示為一個(gè)具有個(gè)頂點(diǎn)的有向圖的鄰接矩陣；同時(shí)，還可表示為一個(gè)二分圖。由此，通過使用鄰接矩陣的概念，每個(gè)有向圖都關(guān)聯(lián)一個(gè)二分圖，反過來，每個(gè)二分圖也都關(guān)聯(lián)一個(gè)有向圖。
運(yùn)算
匹配
匹配：設(shè)是圖的邊集的一個(gè)子集，如果中任意兩條邊在中都不鄰接，則稱是的一個(gè)匹配。
完美匹配與最大匹配：中的一條邊的兩個(gè)端點(diǎn)叫做在下是配對的。若匹配的某條邊與頂點(diǎn)關(guān)聯(lián)，則稱飽和頂點(diǎn)，并且稱是飽和的，否則稱是不飽和的。如果的每個(gè)頂點(diǎn)是飽和的，則稱匹配是完美的。如果中沒有另外的匹配，使，則稱是的一個(gè)最大匹配。顯然，每個(gè)完全匹配都是最大匹配。
增廣路：若是圖中一條連通兩個(gè)未匹配頂點(diǎn)的路徑，并且中已匹配的邊和待匹配的邊在上交替出現(xiàn)，則稱為相對于的一條增廣路，即路徑將兩個(gè)不同集合的兩個(gè)未匹配頂點(diǎn)通過一系列匹配頂點(diǎn)相連。
貝爾熱（Berge）匹配定理：是圖的最大匹配，當(dāng)且僅當(dāng)中不存在可增廣路。
霍爾定理：又稱婚姻定理，它給出了二分圖存在完美匹配的充要條件。設(shè)是有二劃分與的二分圖，則含有飽和的每個(gè)頂點(diǎn)的匹配的充要條件是：，。
匈牙利算法
該算法由匈牙利數(shù)學(xué)家埃德蒙茲（Edmonds）提出，它以霍爾定理為理論基礎(chǔ)，可應(yīng)用增廣路計(jì)算無權(quán)二分圖的最大匹配。
基本思想：每次尋找一條關(guān)于匹配的增廣路，通過使得中的匹配邊數(shù)增加，其中稱為邊集與邊集的環(huán)和。依次類推，直至二分圖中不存在關(guān)于的增廣路為止。此時(shí)得到的匹配就是的一個(gè)最大匹配。
步驟：（1）從一個(gè)初始匹配開始，若飽和的每個(gè)頂點(diǎn)，則停止，即為所求；否則，設(shè)是中非飽和的頂點(diǎn)。令及。
（2）若，則停止。因?yàn)椋苫魻柖ɡ恚淮嬖陲柡偷拿總€(gè)頂點(diǎn)的匹配；否則，，故存在。
（3）若為飽和的，設(shè)，則用代替，代替，并轉(zhuǎn)到（2）；否則，存在以為起點(diǎn)和為終點(diǎn)的可擴(kuò)路，則用代替，并轉(zhuǎn)到（1）。
覆蓋
覆蓋：令為二分圖的頂點(diǎn)子集，若對任意的，的兩個(gè)端點(diǎn)中至少有一個(gè)屬于，則稱為的一個(gè)覆蓋，如果覆蓋在所有的覆蓋中使得達(dá)到最小，則稱為最小覆蓋。
最小覆蓋問題：圖的覆蓋問題包括邊覆蓋和點(diǎn)覆蓋兩種情況，邊覆蓋是用邊控制點(diǎn)，點(diǎn)覆蓋是用點(diǎn)控制邊。最小覆蓋問題研究的是用最少的點(diǎn)（或邊）控制其它的邊（或點(diǎn)）。
標(biāo)識(shí)算法
設(shè)為的一個(gè)匹配，和分別是，的子集，將和中的頂點(diǎn)稱為已加標(biāo)識(shí)的頂點(diǎn)，在下面兩種情況下稱弧邊為可標(biāo)識(shí)弧邊，并且按照下面敘述的方式給弧邊中的端點(diǎn)或者加標(biāo)識(shí)。
①，并且弧邊，此時(shí)給頂點(diǎn)實(shí)施加標(biāo)識(shí)操作，即將標(biāo)識(shí)為；
②，并且弧邊，此時(shí)給頂點(diǎn)實(shí)施加標(biāo)識(shí)操作，即將標(biāo)識(shí)為。
標(biāo)識(shí)算法可描述為：
檢驗(yàn)二分性
圖遍歷主要有廣度優(yōu)先遍歷與深度優(yōu)先遍歷兩種，它們是對偶的遍歷方法。廣度優(yōu)先遍歷是以層為順序，將某一層上的所有節(jié)點(diǎn)都搜索到了之后才向下一層搜索；深度優(yōu)先遍歷是將某一條枝上的所有節(jié)點(diǎn)都搜索到了之后，才轉(zhuǎn)向搜索另一條枝上的所有節(jié)點(diǎn)。
深度優(yōu)先遍歷
一張無向圖是二分圖，當(dāng)且僅當(dāng)圖中不存在奇環(huán)（長度為奇數(shù)的環(huán)）。該充要條件可用染色法進(jìn)行判定，二分圖染色一般基于深度優(yōu)先遍歷實(shí)現(xiàn)。
基本思想：嘗試用黑白兩種顏色標(biāo)記圖中的節(jié)點(diǎn)，當(dāng)一個(gè)節(jié)點(diǎn)被標(biāo)記后，它的所有相鄰節(jié)點(diǎn)應(yīng)該被標(biāo)記與它相反的顏色。若標(biāo)記過程中產(chǎn)生沖突，則說明圖中存在奇環(huán)。
基于深度優(yōu)先遍歷，時(shí)間復(fù)雜度為，流程如下：
廣度優(yōu)先遍歷
一個(gè)圖是二分圖等價(jià)于它是可以二著色的，基于二著色的定義，可用廣度優(yōu)先遍歷來驗(yàn)證圖的二分性。
基本思想：假設(shè)圖為二分圖，則可以從任意一個(gè)點(diǎn)開始對其進(jìn)行二著色。算法在對每個(gè)點(diǎn)進(jìn)行著色的過程中，將染為紅色，則對于的每個(gè)鄰居，可以確定它只能染為藍(lán)色。而對于的每個(gè)鄰居的鄰居，可以確定其只能染為紅色，如此往復(fù)，隨著圖遍歷的推進(jìn)，算法不斷地發(fā)現(xiàn)新的邊和點(diǎn)，進(jìn)而確定所有點(diǎn)的正確著色。在紅藍(lán)著色過程中，如果算法發(fā)現(xiàn)一個(gè)頂點(diǎn)既應(yīng)該被染成紅色，又應(yīng)該被染成藍(lán)色，則可以證明該圖一定不是二分圖。如果始終未能找到圖不是二分圖的證據(jù)，則圖為二分圖。
推廣
超圖
定義：在圖中，的每一個(gè)元素可以看作是的一個(gè)二元子集。考慮任意子集，設(shè)是一個(gè)非空有限集，令是的個(gè)子集的一個(gè)組，稱二元組為一個(gè)超圖。同樣地，可以定義階的概念，特別地，稱為超圖的秩。
聯(lián)系
（1）一個(gè)超圖可確定一個(gè)二分圖的點(diǎn)集（的分拆）定義為和的邊集定義為。根據(jù)定義可得結(jié)論：超圖的色數(shù)的充分必要條件是所確定的二分圖是阿龍·拉姆齊的。
（2）把從超圖確定二分圖的過程反轉(zhuǎn)過來，就可以從二分圖確定一個(gè)超圖，使得。這時(shí)定義的點(diǎn)集為，的每一點(diǎn)所關(guān)聯(lián)的的點(diǎn)的集定義為的一邊，所有如此得到的邊的族是超圖的邊集。
應(yīng)用
生物學(xué)
生物體中多種生物大分子間的相互作用通常以網(wǎng)絡(luò)模型的形式來描述。蛋白質(zhì)相互作用網(wǎng)絡(luò)以生物體內(nèi)的蛋白質(zhì)為結(jié)點(diǎn)，其間的相互關(guān)系為結(jié)點(diǎn)的邊形成無向圖。基于二分圖聚類集成的方法，可設(shè)計(jì)一種融合多生物數(shù)據(jù)的二分圖聚類集成方法以檢測網(wǎng)絡(luò)中的功能模塊。該算法能處理蛋白質(zhì)功能重疊問題，并能用二分圖的表示方法來表現(xiàn)蛋白質(zhì)與來自不同聚類方法的元聚類的從屬關(guān)系。與傳統(tǒng)方法對比，該算法更為有效。
計(jì)算機(jī)科學(xué)
由于知識(shí)決策、信息共享和科學(xué)研究等的需要，個(gè)人、企業(yè)、政府等數(shù)據(jù)收集者為了保證發(fā)布的數(shù)據(jù)不泄露隱私，要對收集到的信息進(jìn)行隱私保護(hù)處理。基于表存儲(chǔ)而發(fā)布的數(shù)據(jù)雖然可以實(shí)現(xiàn)隱私保護(hù)，但是個(gè)體間的關(guān)聯(lián)信息在發(fā)布中缺失，會(huì)影響發(fā)布數(shù)據(jù)的效用。為此，可采用二分圖的形式對數(shù)據(jù)進(jìn)行發(fā)布，把帶有標(biāo)簽的頂點(diǎn)按聚類方法進(jìn)行分組，根據(jù)聚類分組結(jié)果對另外一個(gè)頂點(diǎn)集進(jìn)行最大匹配分組，通過隱藏個(gè)體和頂點(diǎn)的映射關(guān)系，有效地保證了兩類個(gè)體間關(guān)系的安全發(fā)布。
工程學(xué)
智能電網(wǎng)是工業(yè)化和信息化發(fā)展的重要組成部分，其具體場景主要有工業(yè)現(xiàn)場、智能園區(qū)、居民社區(qū)或辦公樓宇等。隨著電力業(yè)務(wù)種類的不斷增多，在保證業(yè)務(wù)隔離性的前提下，還要同時(shí)考慮網(wǎng)絡(luò)側(cè)和電力終端用戶的效用，為實(shí)際智能電網(wǎng)做出有效的資源分配策略。基于二分圖匹配的網(wǎng)絡(luò)切片資源分配算法。針對智能電網(wǎng)場景中的控制類和采集類業(yè)務(wù)，為電力終端分別制定相應(yīng)的投標(biāo)信息，可向多種類型的電力終端提供具有服務(wù)質(zhì)量保證的服務(wù)并最大化系統(tǒng)效用。
參考資料 >