| ... | ... | @@ -8,7 +8,7 @@ |
|
|
|
Доказательство:
|
|
|
|
|
|
|
|
($`\Rightarrow `$)
|
|
|
|
Докажем, что если в графе есть совершенное паросочетание выполняется условие: $`\Leftrightarrow ∀S \in V(G) o(G-S) ≥ |S|`$.
|
|
|
|
Докажем, что если в графе есть совершенное паросочетание выполняется условие: $`∀S \in V(G) o(G-S) ≥ |S|`$.
|
|
|
|
|
|
|
|
Заметим, что без S граф G разваливается на чётные и нечётные компоненты связности. Нечётные компоненты нельзя покрыть паросочетанием (потому что нечётное число нельзя разбить на пары), а совершенное паросочетание у нас всё таки есть, значит из каждой нечётной компоненты шло хотя бы одно ребро в вершины из S (это ребро мы и брали в паросочетание). Но тогда вершин в S не меньше, чем нечётных компонент связности в G-S. Т.е. $`o(G-S) ≥ |S|`$.
|
|
|
|
|
| ... | ... | |
