Skojarzenie (teoria grafów)
Z Wikipedii, wolnej encyclopedia
Skojarzenie (ang. matching) – 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 [1]. 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.
Ten artykuł dotyczy pojęcia z zakresu teorii grafów. Zobacz też: inne znaczenia słowa „skojarzenie”. |
Skojarzenie maksymalne (ang. maximal matching) – takie skojarzenie w grafie że po dodaniu dowolnej krawędzi spośród krawędzi do tego skojarzenia, przestaje ono być skojarzeniem[2].
Skojarzenie największe (ang. maximum matching) – takie skojarzenie w grafie że nie istnieje skojarzenie o większej liczbie krawędzi[3].
Skojarzenie doskonałe (albo „pełne”, ang. perfect matching) – 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[3].
Ścieżka przemienna (ang. alternating path) – ścieżka ułożona naprzemiennie z krawędzi grafu należących i nienależących do [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