İki parçalı eşleştirme

İ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.

Örnek çözümü göster

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']))

Kendini test et

eşleştirme tanımı

match = ____
# match[v] = u

Cevabı göster

match = {}
# match[v] = u

İki parçalı eşleştirme kavramları

U kümesi

Sol taraf
V kümesi

Sağ taraf
eşleştirme

Birebir kenar
maksimum

En büyük eşleme
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
- U kümesinin boyutuna
- Toplam kenar sayısına
Cevabı göster

Bulunan artırıcı yol sayısına — Her artırıcı yol bir eşleşme ekler.

Sıradaki ders: Özet - Network flow

Deneyiminizi Geliştiriyoruz

Çerez Tercihleri

Kesinlikle Gerekli Çerezler

Analitik Çerezler