Skojarzenie (teoria grafów)
Z Wikipedii
Skojarzeniem grafu nazywa się nie zawierający pętli podzbiór M krawędzi grafu E taki, że żadne dwie krawędzie w M nie są sąsiednie, tj. nie spotykają się w jednym wierzchołku.
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.