匹配覆蓋獨立集

匹配、邊覆蓋、點覆蓋、獨立集定義5.7.1設(shè)是圖的一個點子集，若中的每一條邊至少有一個端點在中，則稱是的一個點覆蓋。若中不存在滿足的點覆蓋，則稱是的一個最小點覆蓋。的最小點覆蓋集的點數(shù)稱為的點覆蓋數(shù)，記為一、點覆蓋Vertexcovering一個圖的點覆蓋數(shù)和最大匹配的邊數(shù)之間的關(guān)系：設(shè)G的最大匹配為M，則令引理5.7.1設(shè)是的一個匹配，是的一個覆蓋，且，則是的最大匹配，是的一個最小點覆蓋。分析：取出最大匹配和最小點覆蓋進行比較。點覆蓋數(shù)大于等于最大對集的邊數(shù)。定理5.7.2對每一個二部圖，有證明：取出最大匹配，分兩種情況討論：Case1飽和中所以頂點.則由于構(gòu)成的一個點覆蓋，并且，由引理5.7.1，是G的最小點覆蓋，故定理成立。Case2不飽和中所有頂點，記是中所有非飽和點。置約定由于中頂點與B中頂點在下配對。因此由定理5.3.1類似證明，知,因此G中每一條邊至少有一個端點屬于或,從而構(gòu)成G的點覆蓋。根據(jù)U定義：可見K是G的最小點覆蓋，故證畢。二、獨立集定義5.7.2設(shè)是的一個點子集，若中任意兩個頂點不相鄰，則稱是的一個獨立集，若中不存在滿足的獨立集,則稱是的最大獨立集。最大獨立集的點數(shù)稱為的獨立數(shù)，記為定理5.7.3圖的一個點子集是的獨立集當且僅當是的點覆蓋。說明:圖G的最大獨立集不唯一.independentset推論5.7.4若階圖沒有孤立頂點，則圖的階數(shù)指圖的頂點數(shù)定義5.7.3設(shè)是圖的一個邊子集，若的每一個頂點至少與中的一條邊關(guān)聯(lián)，則稱是的一個邊覆蓋。若不含有滿足的邊覆蓋,則稱是的最小邊覆蓋，它的邊數(shù)稱為的邊覆蓋數(shù)，記為三、邊覆蓋edgecovering定理5.7.5設(shè)是階無孤立頂點的圖，則推論5.7.6對任一個二部圖，如果G沒有孤立頂點，則暈了么？總結(jié)點覆蓋數(shù)邊覆蓋數(shù)獨立數(shù)最大匹配的邊數(shù)也稱‘邊獨立數(shù)’推論5.7.4若階圖沒有孤立頂點，則定理5.7.5設(shè)是階無孤立頂點的圖，則定理5.7.2對每一個二部圖，有推論若G是沒有孤立頂點的二部圖，則注意：不同書中可能字母符號不同所以，對于沒有孤立頂點的二部圖，得到了最大匹配的邊數(shù)，其他三個參數(shù)都可以得到。案例

打獵獵人要在n*n的格子里打鳥,他可以在某一行中打一槍,這樣此行中的所有鳥都被打掉，也可以在某一列中打,這樣此列中的所有鳥都打掉.問至少打幾槍,才能打光所有的鳥？建圖：二分圖的X部為每一行，Y部為每一列，如果(i,j)有一只鳥，那么連接X部的i與Y部的j。求該二分圖的點覆蓋數(shù)該二分圖最大匹配數(shù)既是最少要打的槍數(shù)。利用匈牙利算法求最大匹配案例Pl送ac汁e慎th秒e加Ro濫bo多ts問題曠描述有一液個N*雀M(務(wù)N,槍M<鐘=5重0)的棋夠盤，寬棋盤購的每蜘一格戰(zhàn)是三倒種類盾型之拌一：鉤空地黃、草繡地、即墻。城機器告人只袖能放燥在空躺地上凈。在塔同一礙行或踏同一牛列的屠兩個餓機器響人，鑄若它吸們之悅間沒雨有墻圾，則轎它們期可以菌互相床攻擊濃。問逐給定低的棋碼盤，牛最多喪可以好放置摟多少隙個機量器人答，使油它們宇不能遷互相俗攻擊層。WallGrassEmpty我們抬將每待一行寨，每截一列乖被墻從隔開蟻，且推包含慢空地鍛的連懷續(xù)區(qū)醉域稱勾作“底塊”鑒。顯貪然，奸在一停個塊蹈之中絡(luò)，最紡多只變能放眼一個你機器慎人。迎我們破把這嬌些塊痕編上哄號。同樣潔，把槳豎直晉方向講的塊涌也編旨上號疲。案例Pl棒ac懇e內(nèi)th沿e裂Ro剛bo葵ts模型123451234案例Pl資ac程e類th霸e滅Ro謹bo擋ts模型123451234把每旦個橫朗向塊災(zāi)看作X部的鍬點，揚豎向罷塊看砌作Y部的口點，競?cè)魞芍饌€塊棚有公距共的糕空地妥，則君在它爺們之豈間連輕邊。于是尋，問目題轉(zhuǎn)業(yè)化成蓮這樣婦的一軟個二畢部圖宜：112233445由于花每條牽邊表木示一請個空親地，機器翻人只腐能放減在空湊地上犁。選扒一條抽邊意線味著屯選了利一個畏空地反，放啄了一技個機扶器人除，則買該行頌、該給列“餐連續(xù)鍵的空孕快”慣上不匯能再算放機俱器人鞠。有沖樂突的電空地凱之間丈必有吐公共遇頂點沸，所提以問憂