Лема Берже: відмінності між версіями
| [перевірена версія] | [перевірена версія] |
Немає опису редагування |
|||
| Рядок 2: | Рядок 2: | ||
== Допоміжна лема == |
== Допоміжна лема == |
||
Розглянемо граф <math>G</math> і припустимо, що <math>M</math> і <math>M'</math> є двома паруваннями в <math>G.</math> Нехай <math>G'</math> буде графом отриманим у висліді взяття [[Симетрична_різниця_множин| |
Розглянемо граф <math>G</math> і припустимо, що <math>M</math> і <math>M'</math> є двома паруваннями в <math>G.</math> Нехай <math>G'</math> буде графом отриманим у висліді взяття [[Симетрична_різниця_множин|симетричної різниці]] <math>M</math> і <math>M';</math> тобто <math>(M - M') \cup (M' - M).</math> <math>G'</math> складатиметься із [[Компонента зв'язності графа|компонент зв'язності]], кожна з яких належить до одного з таких класів: |
||
# Ізольована вершина. |
# Ізольована вершина. |
||
# Парний [[Цикл (теорія графів)|цикл]] чиї ребра чергуються між <math>M</math> і <math>M'.</math> |
# Парний [[Цикл (теорія графів)|цикл]] чиї ребра чергуються між <math>M</math> і <math>M'.</math> |
||
Версія за 06:33, 9 квітня 2019
У теорії графів, лема Берже стверджує, що парування є найбільшим тоді і тільки тоді, якщо в немає шляхів розширення щодо
Допоміжна лема
Розглянемо граф і припустимо, що і є двома паруваннями в Нехай буде графом отриманим у висліді взяття симетричної різниці і тобто складатиметься із компонент зв'язності, кожна з яких належить до одного з таких класів:
- Ізольована вершина.
- Парний цикл чиї ребра чергуються між і
- Шлях чиї ребра чергуються між і який не є циклом.
Цю лему можна довести звернувши увага на те. що кожна вершина в може бути інцидентна не більше ніж двом ребрам: одному з і одному з Графи чиї вершини мають степені, що менші або дорівнюють 2, повинні складатись з або ізольованих вершин, або циклів, або шляхів. Більше того, кожний шлях і цикл у повинен перемежовувати ребра між і Для того, щоб цикл відповідав цій умові, він мусить мати однакову кількість ребер з і тобто парну кількість ребер.
Доведення
Припустимо існує шлях розширення щодо Розглянемо симетричну різницю Оскільки є шляхом розширення щодо також є паруванням в і Отже, протиріччя, тобто є найбільшим.
Припустимо не найбільше парування. Нехай буде найбільшим паруванням і, відповідно, маємо Розглянемо Кожна вершина в має не більше двох сусідніх, оскільки і і можуть додати по одній такій вершині. Згідно з попередньою лемою, складається з циклів парної кількості ребер, шляхів та ізольованих вершин. Отже може мати більше ребер більше тільки завдяки шляхам. Отже, існує не менше одного шляху в який має більше з ніж з Але такий шлях є шляхом розширення для
Посилання
- Клод Берже (15 вересня 1957), Дві теореми в теорії графів (PDF), Proceedings of the National Academy of Sciences of the United States of America, 43 (9): 842—844, doi:10.1073/pnas.43.9.842.