Skojarzenie (teoria grafów)

Szablon:Inne znaczenia Skojarzenie (Szablon:Ang.) – 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$ ^[1]. 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 (Szablon:Ang.) – takie skojarzenie w grafie $G,$ że po dodaniu dowolnej krawędzi spośród krawędzi $G$ do tego skojarzenia, przestaje ono być skojarzeniem^[2].

Skojarzenie największe (Szablon:Ang.) – takie skojarzenie w grafie $G,$ że nie istnieje skojarzenie o większej liczbie krawędzi^[3].

Skojarzenie doskonałe (albo „pełne”, Szablon:Ang.) – 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łychSzablon:R.

Ścieżka przemienna (Szablon:Ang.) – ścieżka ułożona naprzemiennie z krawędzi grafu $G$ należących i nienależących do $M$ ^[4].