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

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до: навігація, пошук

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

Означення[ред.ред. код]

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

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

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

Maximal-matching.svg

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

Maximum-matching-labels.svg

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

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

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

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

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