200
правок
Изменения
→Критерий существования реберного ядра
Докажем <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> аналогичного результата для двудольных графов. То же самое доказательство можно перенести на произвольный граф.
}}
{{ Утверждение
=== Примеры ===
[[File:Bipartite_graph_1.png|thumb|130px|Двудольный граф <tex>G_1</tex>]][[File:Bipartite_graph_2.png|thumb|130px|Двудольный граф <tex>G_2</tex>]] Рассмотрим двудольные графы <tex>G_1</tex> и <tex>G_2</tex>, изображенные на рисункерисунках 1 и 2. В графе <tex>G_1</tex> пусть <tex>S_1 = \{v_3, v_6\}</tex> и <tex>T_1 = \{v_1, v_2, v_4, v_5, v_7 \}</tex>. Этот граф имеет единственное наименьшее вершинное покрытие <tex>M_1 = \{v_3, v_6\}</tex> и, поскольку <tex>M_1 об \cap T_1 = пуст\varnothing</tex>, он полунесводимый; сдеовательноследовательно, он совпадает со своим рёберным графомядром. В графе <tex>G_2</tex> пусть <tex>S_2 = \{u_1, u_4, u_5\}</tex> и <tex>T_2 = \{u_2, u_3, u_6\}</tex>.В нём два наименьших вершинных покрытия, именно <tex>M_2 = \{u_1,u_4, u_5\}</tex> и <tex>N_2 = \{u_2, u_3, u_6\}</tex>.Так как <tex>M_2 \cap T_2 = \varnothing</tex> и <tex>N_2 \cap S_2 = \varnothing</tex>, то <tex>G_2</tex> {{---}} несводимый граф и, значит, совпадает со своим рёберным ядром.<br>
== См. также ==
