Лема Берже

У теорії графів, лема Берже стверджує, що парування є найбільшим тоді і тільки тоді, якщо в немає шляхів розширення щодо

Допоміжна лема

Розглянемо граф і припустимо, що і є двома паруваннями в Нехай буде графом отриманим у висліді взяття симетричної різниці і тобто складатиметься із компонент зв'язності, кожна з яких належить до одного з таких класів:

  1. Ізольована вершина.
  2. Парний цикл чиї ребра чергуються між і
  3. Шлях чиї ребра чергуються між і який не є циклом.

Цю лему можна довести звернувши увагу на те, що кожна вершина в може бути інцидентна не більше ніж двом ребрам: одному з і одному з Графи чиї вершини мають степені, що менші або дорівнюють 2, повинні складатись з або ізольованих вершин, або циклів, або шляхів. Більше того, кожний шлях і цикл у повинен перемежовувати ребра між і Для того, щоб цикл відповідав цій умові, він мусить мати однакову кількість ребер з і тобто парну кількість ребер.

Доведення

Припустимо існує шлях розширення щодо Розглянемо симетричну різницю Тому що  — це шлях розширення щодо також є паруванням в і Отже, протиріччя, тобто  — найбільше.

Припустимо не найбільше парування. Нехай буде найбільшим паруванням і, відповідно, маємо Розглянемо Кожна вершина в має не більше двох сусідніх, оскільки і і можуть додати по одній такій вершині. Згідно з попередньою лемою, складається з циклів парної кількості ребер, шляхів та ізольованих вершин. Отже може мати більше ребер більше тільки завдяки шляхам. Отже, існує не менше одного шляху в який має більше з ніж з Але такий шлях є шляхом розширення для

Посилання

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.