Skojarzenia

https://en.wikipedia.org/wiki/Matching_(graph_theory)

https://en.wikipedia.org/wiki/Blossom_algorithm

WPROWADZENIE

Skojarzenie (ang. matching) w grafie nieskierowanym G=(V,E) jest to taki podzbiór krawędzi M, że każdy wierzchołek z V jest końcem co najwyżej jednej krawędzi z M. Czasem używana jest nazwa zbiór niezależny krawędzi (ang. independent edge set). Skojarzenie jest maksymalne (ang. maximal matching), jeżeli nie jest podzbiorem żadnego innego skojarzenia. Skojarzenie jest największe (najliczniejsze) (ang. maximum matching), jeżeli w grafie nie istnieje skojarzenie o większej liczbie krawędzi. Skojarzenie jest doskonałe (ang. perfect matching), kiedy każdy wierzchołek grafu jest końcem pewnej krawędzi należącej do tego skojarzenia. Skojarzenie doskonałe może istnieć tylko dla grafu o parzystej liczbie wierzchołków. Skojarzenie doskonałe jest maksymalne i największe.

Skojarzenie największe w grafach dwudzialnych może być znalezione algorytmem Hopcrofta-Karpa w czasie O(sqrt(n)*m). W ogólnych grafach można użyć algorytmu kwiatowego Edmondsa.

W grafach ważonych rozważa się problem skojarzenia o najmniejszej wadze.

Istnieje kilka sposobów zaimplementowania skojarzenia. Może to być zbiór krawędzi albo słownik, w którym klucze to wierzchołki grafu. a wartości to wierzchołki lub None.

# Testowanie skojarzenia.
# Skojarzenie to słownik mate, który dla krawędzi (source, target)
# należącej do skojarzenia zawiera
# mate[source] = target
# mate[target] = source
# mate[node] = None, jeżeli node nie jest końcem krawędzi ze skojarzenia.

import unittest

def find_matching(graph):
    pass

class TestMatching(unittest.TestCase):

    def setUp(self):
        self.G = dict()
        self.edges = []   # wstawiamy 3-krotki, graf ważony
        # Wstawiamy wierzchołki i krawędzie do G.

    def test_matching(self):
        mate = find_matching(self.G)
        for source in mate:
            if mate[source] is not None:
                target = mate[source]
                self.assertEqual(mate[target], source)

SKOJARZENIE DOSKONAŁE JAKO PROBLEM DOKŁADNEGO POKRYCIA ZBIORU

Znajdowanie skojarzenia doskonałego w grafie można zapisać jako problem znajdowania dokładnego pokrycia zbioru. Należy jednak pamiętać, że istnieją algorytmy znajdujące skojarzenie doskonałe w czasie wielomianowym, natomiast problem znajdowania dokładnego pokrycia jest w ogólności NP-zupełny.

# Przykładowy graf
# A---B---C---D
#   \ |   |
#     E---F
# Krawędzie skojarzenia doskonałego: AB, CD, EF
+------------+-------------+
| Kolumna    | A B C D E F |
+------------+-------------+
| Krawędź AB | 1 1 0 0 0 0 | *
| Krawędź AE | 1 0 0 0 1 0 |
| Krawędź BC | 0 1 1 0 0 0 |
| Krawędź BE | 0 1 0 0 1 0 |
| Krawędź CD | 0 0 1 1 0 0 | *
| Krawędź CF | 0 0 1 0 0 1 |
| Krawędź EF | 0 0 0 0 1 1 | *
+------------+-------------+