Skojarzenie (teoria grafów)

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

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

Skojarzenie największe (ang. maximum matching) – takie skojarzenie w grafie $G,$ że nie istnieje skojarzenie o większej liczbie krawędzi.

Skojarzenie doskonałe (albo „pełne”, ang. perfect matching) – podzbiór $M$ krawędzi grafu $G$ o tej własności, że każdy wierzchołek $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.

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

• 
  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