İki parçalı eşleştirme
- Algoritmalar kursu
- Uzman seviye
- Ders 29/41
- 4 dk
İki parçalı grafikte maksimum eşleştirme öğrenirsin.
İki parçalı eşleştirme
İki parçalı graf, düğümleri U ve V olarak ikiye ayrılabilen ve yalnızca U'dan V'ye kenar içeren graftır. Eşleştirme, her düğüme en fazla bir kenar düşecek şekilde seçilmiş kenar kümesidir.
Maksimum eşleştirme, olası en büyük eşleştirmedir. İş ilanları ve adaylar, ders ve öğrenci gibi birçok gerçek sorun bu modele uyar.
İki parçalı maksimum eşleştirme, akış ağına indirgenebilir: kaynaktan U'ya, U'dan V'ye, V'den hedefe kenarlar eklenir.
Artırıcı yol yöntemi
İki parçalı maksimum eşleştirme, artırıcı yol (augmenting path) yöntemiyle bulunur. Bir artırıcı yol, eşleşmemiş bir U düğümünden başlayıp eşleşmemiş bir V düğümünde biten, eşleşen ve eşleşmeyen kenarları sırayla içeren yoldur.
Her artırıcı yol bulunduğunda eşleştirme bir artırılır. Artırıcı yol kalmadığında eşleştirme maksimumdur.
Bu yöntem, Ford-Fulkerson'ın iki parçalı graf özel halidir.
Uygulama bipartite_matching fonksiyonu
bipartite_matching(graph, left) yaz. graph U düğümlerinden V listelerine eşleme; left U düğümleri. Maksimum eşleştirme sayısını döndür. print(bipartite_matching({'a': [1, 2], 'b': [1], 'c': [2, 3]}, ['a', 'b', 'c'])) ile 3 yazdır.
Başlangıç kodu
def bipartite_matching(graph, left):
# İki parçalı maksimum eşleştirmeÖrnek çözüm
def bipartite_matching(graph, left):
# İki parçalı maksimum eşleştirme
match = {}
def augment(u, visited):
for v in graph[u]:
if v not in visited:
visited.add(v)
if v not in match or augment(match[v], visited):
match[v] = u
return True
return False
result = 0
for u in left:
if augment(u, set()):
result += 1
return result
print(bipartite_matching({'a': [1, 2], 'b': [1], 'c': [2, 3]}, ['a', 'b', 'c']))Beklenen çıktı
3
Soru ve cevaplar
Dersin sorularını cevaplarıyla birlikte inceleyebilirsin. Kendini denemek istersen dersi interaktif olarak çöz.
1 eşleştirme tanımı
match = ____
# match[v] = umatch = {}
# match[v] = uAçıklama: match bir dict olarak başlatılır.
2 İki parçalı eşleştirme kavramları
| Kavram | Anlamı |
|---|---|
U kümesi |
Sol taraf |
V kümesi |
Sağ taraf |
eşleştirme |
Birebir kenar |
maksimum |
En büyük eşleme |
3 Maksimum eşleştirme neye eşittir?
if augment(u, set()):
result += 1- En kısa yola
- Bulunan artırıcı yol sayısına Doğru cevap
- U kümesinin boyutuna
- Toplam kenar sayısına
Açıklama: Her artırıcı yol bir eşleşme ekler.