... | @@ -52,6 +52,8 @@ $`M_2`$ -- совершенное паросочетание на $`G^* + yw`$ |
... | @@ -52,6 +52,8 @@ $`M_2`$ -- совершенное паросочетание на $`G^* + yw`$ |
|
Тогда пусть $`H`$ -- объединение $`M_1`$ и $`M_2`$. Т.е. $`H = M_1 \Delta M_2`$.
|
|
Тогда пусть $`H`$ -- объединение $`M_1`$ и $`M_2`$. Т.е. $`H = M_1 \Delta M_2`$.
|
|
Т.к. $`M_1`$ и $`M_2`$ -- совершенные паросочетания $`H`$ -- объединение чётных циклов, в которых чередуются рёбра из $`M_1`$ и $`M_2`$.
|
|
Т.к. $`M_1`$ и $`M_2`$ -- совершенные паросочетания $`H`$ -- объединение чётных циклов, в которых чередуются рёбра из $`M_1`$ и $`M_2`$.
|
|
|
|
|
|
|
|
<img src="uploads/619058b50bee0e8759281e4f1dec2e61/tatt-theorem-4.png" width="50%" height="50%">
|
|
|
|
|
|
Понятно, что наши рёбра $`zx`$ и $`yw`$ тоже попали в $`H`$. Потому что они были в $`M_1`$ и $`M_2`$ и не могли пропасть, потому что каждое было только в одном паросочетании. Но они могли попасть либо, в один либо в разные циклы. (См картинку)
|
|
Понятно, что наши рёбра $`zx`$ и $`yw`$ тоже попали в $`H`$. Потому что они были в $`M_1`$ и $`M_2`$ и не могли пропасть, потому что каждое было только в одном паросочетании. Но они могли попасть либо, в один либо в разные циклы. (См картинку)
|
|
|
|
|
|
<img src="uploads/dca43c9871081e8a8dce33aeb4a4eaf1/tatt-theorem-5.png" width="100%" height="100%">
|
|
<img src="uploads/dca43c9871081e8a8dce33aeb4a4eaf1/tatt-theorem-5.png" width="100%" height="100%">
|
... | | ... | |