Лемма Бержа: различия между версиями
Глеб (обсуждение | вклад) (Новая страница: «==Определения== Пусть дан двудольный граф $G$, Пусть есть какой-то его подграф-паросочетан...») |
|||
(не показана 1 промежуточная версия 1 участника) | |||
Строка 23: | Строка 23: | ||
2) Цикл, докажем, что все циклы в $C$ также могут быть только четной длины. Тут работает критерий двудольности, а именно мы не сможем покрасить цикл нечетной длины в два цвета. | 2) Цикл, докажем, что все циклы в $C$ также могут быть только четной длины. Тут работает критерий двудольности, а именно мы не сможем покрасить цикл нечетной длины в два цвета. | ||
− | $\Rightarrow$ мы доказали, что все объекты в $C$ - четной длины, так как они чередуются, то половина ребер из $A$ и половина из $B$, но по свойству $\bigoplus$ мы можем сказать, что $|A| = |B|$(так как если ребра нет в $C$, то ребро либо было и там и там, либо его не было ни в одном из графов), а следовательно мы только | + | $\Rightarrow$ мы доказали, что все объекты в $C$ - четной длины, так как они чередуются, то половина ребер из $A$ и половина из $B$, но по свойству $\bigoplus$ мы можем сказать, что $|A| = |B|$(так как если ребра нет в $C$, то ребро либо было и там и там, либо его не было ни в одном из графов), а следовательно мы только что доказали теорему. |
{{Автор|Глеб Лобанов|glebodin}} | {{Автор|Глеб Лобанов|glebodin}} | ||
+ | |||
+ | [[Категория:Конспект]] |
Текущая версия на 21:26, 8 мая 2020
Определения
Пусть дан двудольный граф $G$, Пусть есть какой-то его подграф-паросочетание, назовем его $G^{\prime}$
Цепь в графе $G^{\prime}$ - такой максимальный по длине реберно-простой путь в $G$, что его ребра чередуются(например четные - лежат, а нечетные - не лежат в графе $G^{\prime}$)
Удлиняющая цепь - цепь, первое и последнее ребро которой, не лежат в графе $G^{\prime}$.
Теорема
Паросочетание в графе является максимальным тогда и только тогда, когда в графе нет удлиняющих цепей.
Доказательство необходимости
Пусть в максимальном паросочетании $G^{\prime}$ есть удлиняющая цепь, тогда давайте ее инвертируем, мы можем так сделать, так как ребро, идущее за последним и перед первым ребром удлиняющей цепи не включены в граф $G^{\prime}$, следовательно если в графе есть удлиняющая цепь, тогда мы можем увеличить наше паросочетание $\Rightarrow$ противоречие.
Доказательство достаточности
Пусть есть какое-то максимальное паросочетание $A$ и какое-то паросочетание $B$, в котором нет удлиняющей цепи. Возьмем их симметрическую разность($\bigoplus$ - такой набор ребер $C$, что в него входят только ребра, которые есть либо только в $A$, либо только в $B$), рассмотрим все возможные субъекты в $C$ :
1) Путь, докажем, что пути в $С$ могут быть только четной длины. Пусть это не так и у нас есть путь нечетной длины, так как два подряд идущих ребра из $C$ не могут быть из одного и тоже паросочетаниях, то значит в этом пути ребра с четными номерами и ребра с нечетными номерами лежат в разных паросочетаниях. Но тогда рассмотрим граф, в котором лежат ребра с четными номерами, тогда мы нашли в нем удлиняющую цепь, противоречие.
2) Цикл, докажем, что все циклы в $C$ также могут быть только четной длины. Тут работает критерий двудольности, а именно мы не сможем покрасить цикл нечетной длины в два цвета.
$\Rightarrow$ мы доказали, что все объекты в $C$ - четной длины, так как они чередуются, то половина ребер из $A$ и половина из $B$, но по свойству $\bigoplus$ мы можем сказать, что $|A| = |B|$(так как если ребра нет в $C$, то ребро либо было и там и там, либо его не было ни в одном из графов), а следовательно мы только что доказали теорему.
Автор конспекта: Глеб Лобанов
По всем вопросам пишите в telegram @glebodin