二分圖匹配匈牙利算法和km算法簡(jiǎn)介(已修改)
2025-02-26 14:29 本頁(yè)面
【正文】 二分圖匹配 匈牙利算法和 KM算法簡(jiǎn)介 二分圖的概念 ?二分圖又稱作二部圖，是圖論中的一種特殊模型。 ?設(shè) G=(V,{R})是一個(gè)無(wú)向圖。如頂點(diǎn)集 V可分割為兩個(gè)互不相交的子集，并且圖中每條邊依附的兩個(gè)頂點(diǎn)都分屬兩個(gè)不同的子集。則稱圖 G為二分圖。 1 1 2 2 3 3 4 4 5 最大匹配 ?給定一個(gè)二分圖 G，在 G的一個(gè)子圖 M中， M的邊集 {E}中的任意兩條邊都不依附于同一個(gè)頂點(diǎn)，則稱 M是一個(gè)匹配。 ?選擇這樣的邊數(shù)最大的子集稱為圖的 最大匹配問(wèn)題 (maximal matching problem) ?如果一個(gè)匹配中，圖中的每個(gè)頂點(diǎn)都和圖中某條邊相關(guān)聯(lián)，則稱此匹配為 完全匹配 ，也稱作 完備匹配。 匈牙利算法 ?求最大匹配的一種顯而易見的算法是：先找出全部匹配，然后保留匹配數(shù)最多的。但是這個(gè)算法的復(fù)雜度為邊數(shù)的指數(shù)級(jí)函數(shù)。因此，需要尋求一種更加高效的算法。 ?增廣路的定義 (也稱增廣軌或交錯(cuò)軌 )： ?若 P是圖 G中一條連通兩個(gè)未匹配頂點(diǎn)的路徑，并且屬 M的邊和不屬 M的邊 (即已匹配和待匹配的邊 )在 P上交替出現(xiàn)，則稱 P為相對(duì)于 M的一條增廣路徑。 匈牙利算法 ?由增廣路的定義可以推出下述三個(gè)結(jié)論： ? 1－ P的路徑長(zhǎng)度必定為奇數(shù)，第一條邊和最后一條邊都不屬于 M。 ? 2－ P經(jīng)過(guò)取反操作可以得到一個(gè)更大的匹配M’。 ? 3－ M為 G的最大匹配當(dāng)且僅當(dāng)不存在相對(duì)于M的增廣路徑。 匈牙利算法 ?用增廣路求最大匹配 (稱作匈牙利算法，匈牙利數(shù)學(xué)家 Edmonds于 1965年提出 ) ?算法輪廓： ? (1)置 M為空 ? (2)找出一條增廣路徑 P，通過(guò)取反操作獲得更大的匹配 M’代替 M ? (3)重復(fù) (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
范文總結(jié)相關(guān)推薦
鄂ICP備17016276號(hào)-1