Лемма Бержа: различия между версиями

Материал из Algocode wiki
Перейти к: навигация, поиск
(Новая страница: «==Определения== Пусть дан двудольный граф $G$, Пусть есть какой-то его подграф-паросочетан...»)
 
Строка 23: Строка 23:
 
2) Цикл, докажем, что все циклы в $C$ также могут быть только четной длины. Тут работает критерий двудольности, а именно мы не сможем покрасить цикл нечетной длины в два цвета.
 
2) Цикл, докажем, что все циклы в $C$ также могут быть только четной длины. Тут работает критерий двудольности, а именно мы не сможем покрасить цикл нечетной длины в два цвета.
  
$\Rightarrow$ мы доказали, что все объекты в $C$ - четной длины, так как они чередуются, то половина ребер из $A$ и половина из $B$, но по свойству $\bigoplus$ мы можем сказать, что $|A| = |B|$(так как если ребра нет в $C$, то ребро либо было и там и там, либо его не было ни в одном из графов), а следовательно мы только, что доказали теорему.
+
$\Rightarrow$ мы доказали, что все объекты в $C$ - четной длины, так как они чередуются, то половина ребер из $A$ и половина из $B$, но по свойству $\bigoplus$ мы можем сказать, что $|A| = |B|$(так как если ребра нет в $C$, то ребро либо было и там и там, либо его не было ни в одном из графов), а следовательно мы только что доказали теорему.
  
 
{{Автор|Глеб Лобанов|glebodin}}
 
{{Автор|Глеб Лобанов|glebodin}}

Версия 09:44, 12 февраля 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