Число парування

розмір найбільшого парування в графі

Число́ парува́ння графа  — розмір найбільшого парування в ньому.

У довільному графі число парування можна знайти за допомогою алгоритму Едмондса[en] за час . Мікалі й Вазірані показали алгоритм, який будує найбільше парування за час . Інший (рандомізований) алгоритм, розроблений Муча і Санковським (Mucha, Sankowski), заснований на швидкому множенні матриць, дає складність .

У графі без ізольованих вершин число парування пов'язане з числом реберного покриття другою тотожністю Галлаї: , з якої, в свою чергу, випливає нерівність . Якщо в графі існує досконале парування, то .

У будь-якому графі також виконується нерівність , де  — число вершинного покриття графа . У двочастковому графі , внаслідок теореми Кеніга, .

ПосиланняРедагувати