二分圖匹配匈牙利算法和km算法簡介(已修改)
2025-02-26 14:29 本頁面
【正文】 二分圖匹配 匈牙利算法和 KM算法簡介 二分圖的概念 ?二分圖又稱作二部圖，是圖論中的一種特殊模型。 ?設 G=(V,{R})是一個無向圖。如頂點集 V可分割為兩個互不相交的子集，并且圖中每條邊依附的兩個頂點都分屬兩個不同的子集。則稱圖 G為二分圖。 1 1 2 2 3 3 4 4 5 最大匹配 ?給定一個二分圖 G，在 G的一個子圖 M中， M的邊集 {E}中的任意兩條邊都不依附于同一個頂點，則稱 M是一個匹配。 ?選擇這樣的邊數(shù)最大的子集稱為圖的 最大匹配問題 (maximal matching problem) ?如果一個匹配中，圖中的每個頂點都和圖中某條邊相關聯(lián)，則稱此匹配為 完全匹配 ，也稱作 完備匹配。 匈牙利算法 ?求最大匹配的一種顯而易見的算法是：先找出全部匹配，然后保留匹配數(shù)最多的。但是這個算法的復雜度為邊數(shù)的指數(shù)級函數(shù)。因此，需要尋求一種更加高效的算法。 ?增廣路的定義 (也稱增廣軌或交錯軌 )： ?若 P是圖 G中一條連通兩個未匹配頂點的路徑，并且屬 M的邊和不屬 M的邊 (即已匹配和待匹配的邊 )在 P上交替出現(xiàn)，則稱 P為相對于 M的一條增廣路徑。 匈牙利算法 ?由增廣路的定義可以推出下述三個結論： ? 1－ P的路徑長度必定為奇數(shù)，第一條邊和最后一條邊都不屬于 M。 ? 2－ P經過取反操作可以得到一個更大的匹配M’。 ? 3－ M為 G的最大匹配當且僅當不存在相對于M的增廣路徑。 匈牙利算法 ?用增廣路求最大匹配 (稱作匈牙利算法，匈牙利數(shù)學家 Edmonds于 1965年提出 ) ?算法輪廓： ? (1)置 M為空 ? (2)找出一條增廣路徑 P，通過取反操作獲得更大的匹配 M’代替 M ? (3)重復 (2)操作直到找不出增廣路徑為止 匈牙利算法 ?程序清單： ? Function find(k:integer):integer。 ? var st,sf,i,j,t:integer。 ? queue,father:array[1..100] of integer。 ? begin ? queue[1] := k。 st := 1。 sf := 1。 ? fillchar(father,sizeof(fa
范文總結相關推薦
鄂ICP備17016276號-1