Skojarzenie (teoria grafów)

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.

Wierzchołki będące końcami krawędzi należących do M są M-nasycone. Wierzchołki nie będące końcami krawędzi należących do M są M-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.