Skojarzenie (teoria grafów)

Z Wikipedii, wolnej encyklopedii
Skocz do: nawigacji, wyszukiwania

Skojarzeniem grafu nazywa się niezawierający pętli podzbiór krawędzi grafu (ozn. M) taki, że każdy wierzchołek jest końcem co najwyżej jednej krawędzi z M, tj. każdy wierzchołek jest połączony krawędzią z dokładnie jednym innym wierzchołkiem albo wcale.

Maximal-matching.svg

Wierzchołki będące końcami krawędzi należących do MM-nasycone. Wierzchołki nie będące końcami krawędzi należących do MM-nienasycone.

Skojarzenie doskonałe to podzbiór M krawędzi grafu G, taki, że każdy wierzchołek G jest M-nasycony.

Skojarzenie doskonałe jest zawsze skojarzeniem największym, tj. takim, że nie istnieje skojarzenie grafu G o większej liczbie krawędzi.

Pary wierzchołków połączone bezpośrednio krawędzią należącą do M są skojarzone przez M.

M-przemienna ścieżka to ścieżka ułożona naprzemiennie z krawędzi należących i nienależących do M.