Skojarzenie () – podzbiór krawędzi grafu (ozn. ) o tej własności, że każdy wierzchołek jest końcem co najwyżej jednej krawędzi z . Pary wierzchołków połączone bezpośrednio krawędzią należącą do są skojarzone przez Wierzchołki będące końcami krawędzi należących do są M-nasycone. Wierzchołki niebędące końcami krawędzi należących do są M-nienasycone.
Rodzaje skojarzeń
Skojarzenie maksymalne () – takie skojarzenie w grafie że po dodaniu dowolnej krawędzi spośród krawędzi do tego skojarzenia, przestaje ono być skojarzeniem.
Skojarzenie największe () – takie skojarzenie w grafie że nie istnieje skojarzenie o większej liczbie krawędzi.
Skojarzenie doskonałe (albo „pełne”, ) – podzbiór krawędzi grafu o tej własności, że każdy wierzchołek 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 () – ścieżka ułożona naprzemiennie z krawędzi grafu należących i nienależących do .
Przypisy
Kategoria:Teoria grafów