1632
правки
Изменения
м
rollbackEdits.php mass rollback
Докажем <tex>(2) \Rightarrow (1)</tex>.
Пусть <tex>M = \{v_1, \dots, v_s\}</tex> {{---}} наименьшее внешнее вершинное покрытие. Пусть <tex>Y_i = \{u \mid u \in U, uv_i \in E(G) \}</tex>. Тогда для любого <tex>k: \:\: 1 \leqslant k \leqslant s</tex>, объединение любых <tex>k</tex> различных множеств <tex>Y_i</tex> содержит, по меньшей мере <tex>k</tex> вершин.
Следовательно, по [[Теорема Холла|теореме о свадьбах (Холла<ref>Hall, 1935, pp. 26-30.</ref>)]], существует множество <tex>s</tex> различных вершин <tex>\{y_1, \dots, y_s\}, \: y_j \in Y_j</tex>. Следовательно существует набор независимых ребер <tex>y_1v_1, \dots, y_sv_s</tex>. А значит <tex>C_1(G)</tex> не может быть пустым.
}}
[[Файл:EdgeCore.png|thumb|500px|рис. 1. a) граф <tex>H</tex>, б) реберное ядро графа <tex>H</tex> ]]
{{Определение|
definition=
<tex>G</tex> {{---}} '''сводимый граф''' (англ. ''reducible graph'') если он не является ни полунесводимым, ни сводимымнесводимым.
}}
Если оба конца ребра <tex>w \in E(G)</tex> покрыто некоторым минимальным вершинным покрытием, то <tex>w \notin C_1(G)</tex>.
|proof=
Сошлемся на теорему <tex>3 (Theorem 3)</tex> аналогичного результата<ref>A. L. Dulmage and N. S. Mendelsohn, 1958, pp. 517-534519.</ref> аналогичного результата для двудольных графов. То же самое доказательство можно перенести на произвольный граф.
}}
{{ Утверждение
