Skojarzenie (teoria grafów)

Niniejszy artykuł jest częścią cyklu teoria grafów.

Najważniejsze pojęcia graf drzewo podgraf cykl klika stopień wierzchołka stopień grafu dopełnienie grafu obwód grafu pokrycie wierzchołkowe liczba chromatyczna indeks chromatyczny izomorfizm grafów homeomorfizm grafów więcej... Wybrane klasy grafów graf pełny graf spójny drzewo graf dwudzielny graf regularny graf eulerowski graf hamiltonowski graf planarny więcej... Algorytmy grafowe A* Bellmana-Forda Dijkstry Fleury'ego Floyda-Warshalla Johnsona Kruskala Prima przeszukiwanie grafu – wszerz – w głąb najbliższego sąsiada Zagadnienia przedstawiane jako problemy grafowe problem komiwojażera problem chińskiego listonosza problem marszrutyzacji problem kojarzenia małżeństw Inne zagadnienia kod Graya diagram Hassego kod Prüfera

Skojarzenie (ang. matching) – podzbiór krawędzi grafu (ozn. ${\displaystyle M}$) o tej własności, że każdy wierzchołek jest końcem co najwyżej jednej krawędzi z ${\displaystyle M}$^[1]. Pary wierzchołków połączone bezpośrednio krawędzią należącą do ${\displaystyle M}$ są skojarzone przez ${\displaystyle M.}$ Wierzchołki będące końcami krawędzi należących do ${\displaystyle M}$ są M-nasycone. Wierzchołki niebędące końcami krawędzi należących do ${\displaystyle M}$ są M-nienasycone.

Skojarzenie maksymalne (ang. maximal matching) – takie skojarzenie w grafie ${\displaystyle G,}$ że po dodaniu dowolnej krawędzi spośród krawędzi ${\displaystyle G}$ do tego skojarzenia, przestaje ono być skojarzeniem^[2].

Skojarzenie największe (ang. maximum matching) – takie skojarzenie w grafie ${\displaystyle G,}$ że nie istnieje skojarzenie o większej liczbie krawędzi^[3].

Skojarzenie doskonałe (albo „pełne”, ang. perfect matching) – podzbiór ${\displaystyle M}$ krawędzi grafu ${\displaystyle G}$ o tej własności, że każdy wierzchołek ${\displaystyle G}$ jest M-nasycony. Aby w grafie istniało skojarzenie doskonałe, musi on mieć parzystą liczbę wierzchołków. Skojarzenie doskonałe jest zawsze skojarzeniem największym i maksymalnym. W grafie może być wiele skojarzeń doskonałych^[3].

Ścieżka przemienna (ang. alternating path) – ścieżka ułożona naprzemiennie z krawędzi grafu ${\displaystyle G}$ należących i nienależących do ${\displaystyle M}$^[4].

• 

  Skojarzenie w grafie (czerwone krawędzie)

• 

  Skojarzenie maksymalne (liczba krawędzi 3)

• 

  Skojarzenie największe (liczba krawędzi 4)

• 

  Skojarzenie doskonałe

• 

  Inne skojarzenie doskonałe

Przypisy