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

Означення

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

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

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

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

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

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

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

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

Джерела