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

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

У довільному графі число парування можна знайти за допомогою ^[en] за час ${\displaystyle O(|E||V|^{2})}$. Мікалі й Вазірані показали алгоритм, який будує найбільше парування за час ${\displaystyle O(|E||V|^{1/2})}$. Інший (рандомізований) алгоритм, розроблений Муча і Санковським (Mucha, Sankowski), заснований на швидкому множенні матриць, дає складність ${\displaystyle O(V^{2.376})}$.

У графі ${\displaystyle G=(V,E)}$ без ізольованих вершин число парування ${\displaystyle \nu (G)}$ пов'язане з числом реберного покриття ${\displaystyle \rho (G)}$ другою тотожністю Галлаї: ${\displaystyle \nu (G)+\rho (G)=|V|}$, з якої, в свою чергу, випливає нерівність ${\displaystyle \nu (G)\leq \rho (G)}$. Якщо в графі існує досконале парування, то ${\displaystyle \nu (G)=\rho (G)=|V|/2}$.

У будь-якому графі ${\displaystyle G}$ також виконується нерівність ${\displaystyle \nu (G)\leq \tau (G)}$, де ${\displaystyle \tau (G)}$ — число вершинного покриття графа ${\displaystyle G}$. У двочастковому графі ${\displaystyle G}$, внаслідок теореми Кеніга, ${\displaystyle \nu (G)=\tau (G)}$.

Посилання

• László Lovász, ^[en]. Matching Theory. — North-Holland, 1986. — .