Парування (теорія графів)

Парування, або незалежний набір ребер, або паросполука графу — множина ребер без спільних вершин (несуміжних).

Означення

Дано граф G = (V,E), тоді паруванням M в G називається множина попарно несуміжних ребер; тобто таких, що не мають спільних вершин.

Вершина нанизана, якщо вона є кінцевою для якогось з ребер в паруванні. Інакше вершина ненанизана або вільна.

Максимальне парування (англ. maximal matching) — це парування M графу G з властивістю, що якщо будь-яке ребро не з M додати до M, тоді M більше не парування, тобто M є повним якщо воно не є властивою підмножиною будь-якого іншого парування графу G. Інакше кажучи, парування M графу G максимальне, якщо кожне ребро в G суміжне до хоча б одного з ребер з M. Наступний малюнок подає приклади максимального парування (червоним) в трьох графах.

Максимум парувань (англ. maximum matching) — це парування, що містить найбільшу можливу кількість ребер. Максимумів може бути декілька. Число парування $\nu (G)$ графу $G$  — розмір максимуму парувань. Зважте, що кожне максимум парувань є максимальним, але не навпаки. Наступний малюнок показує приклади максимумів парувань у трьох графах.

Досконале парування (англ. perfect matching, 1-factor) — це парування яке покриває всі вершини графу. Тобто кожна з вершин графу інцидентна одному з ребер в паруванні. Малюнок (b) згори є прикладом досконалого парування. Кожне досконале парування є найбільшим і максимальним. В малюнку нагорі лише (b) показує досконале парування. Досконале парування також є реберним покриттям. Таким чином, ν(G) ≤ ρ(G) , тобто розмір максимального парування не більше ніж розмір мінімального реберного покриття.

Майже досконале парування (англ. near-perfect matching) — це таке парування, коли рівно одна вершина ненанизана. Це може статися лише коли граф має непарну кількість вершин, і таке парування має бути максимальним. У фігурі згори (c) показує майже досконале парування. Якщо для кожної вершини графу існує майже досконале парування, що не нанизує саме цю вершину, граф також називається (англ. factor-critical).

Для парування M,

• переміжний шлях (англ. alternating path) — це шлях, в якому ребра належать до парування через одне.
• шлях розширення (англ. augmenting path) — це переміжний шлях, що починається і завершується вільними вершинами.

Можна довести, що парування є максимальним тоді і лише тоді, коли не існує шляху розширення. (Цей вислід іноді називають лемою Берже.)