Лема Берже: відмінності між версіями
| [перевірена версія] | [перевірена версія] |
Немає опису редагування |
|||
| Рядок 10: | Рядок 10: | ||
== Доведення == |
== Доведення == |
||
Припустимо існує шлях розширення <math>P</math> щодо <Math>M.</math> Розглянемо симетричну різницю <Math>M\oplus P.</math> |
Припустимо існує шлях розширення <math>P</math> щодо <Math>M.</math> Розглянемо [[симетрична різниця|симетричну різницю]] <Math>M\oplus P.</math> Тому що <math>P</math> — це шлях розширення щодо <Math>M',</math> <math>M\oplus P</math> також є паруванням в <math>G</math> і <Math>|M\oplus P| = |M| + 1.</math> Отже, протиріччя, тобто <Math>M</math> — найбільше. |
||
Припустимо <math>M</math> не найбільше парування. Нехай <math>M'</math> буде найбільшим паруванням і, відповідно, маємо <math>|M'|>|M|.</math> Розглянемо <math>M\ |
Припустимо <math>M</math> не найбільше парування. Нехай <math>M'</math> буде найбільшим паруванням і, відповідно, маємо <math>|M'|>|M|.</math> Розглянемо <math>M\oplus M'.</math> Кожна вершина в <math>M\oplus M'</math> має не більше двох сусідніх, оскільки і <math>M,</math> і <math>M'</math> можуть додати по одній такій вершині. Згідно з попередньою лемою, <Math>M\oplus M'</math> складається з циклів парної кількості ребер, шляхів та ізольованих вершин. Отже <math>M</math> може мати більше ребер більше <Math>M'</math> тільки завдяки шляхам. Отже, існує не менше одного шляху в <math>M\oplus M',</math> який має більше з <math>M'</math> ніж з <math>M.</math> Але такий шлях є шляхом розширення для <Math>M.</math> |
||
== Посилання == |
== Посилання == |
||
Версія за 06:38, 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.