Изменения

'''Рёберное ядро''' (англ. ''core'') <tex>C_1(G)</tex> графа <tex>G</tex> {{---}} это подграф [[Основные определения теории графов#finite graph|графа ]] <tex>G</tex>, порожденный объединением таких независимых множеств <tex>Y \subset E(G)</tex>, что <tex>|Y| = \alpha_{0}(G)</tex>, где <tex>\alpha_{0}(G)</tex> {{---}} число вершинного покрытия.

Множество [[Основные определения теории графов#def_graph_edge_1|ребер ]] (вершин) называется '''независимым''' (англ. ''independent''), если никакие его два элемента не смежны.

{{Определение|id=def_3|definition=

Наименьшее вершинное покрытие <tex>M </tex> графа <tex>G </tex> с множеством вершин <tex>V </tex> называется '''внешним''' (англ. ''external vertex cover''), если для любого подмножества <tex>M' \subseteq M</tex> выполняется неравенство <tex>|M'| \leqslant |U(M')|</tex>, где <tex>U(M') = \{v \mid \:v \in V(G) \setminus M, \: vu \in E(G), \: u \in M'\}</tex>.

для Для произвольного графа <tex>G</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> не может быть пустым.

Здесь и далее будем рассматривать [[Двудольные графы|двудольный граф ]] <tex>G</tex>, в котором обозначим <tex>S</tex> {{---}} множество вершин левой доли, <tex>T</tex> {{---}} множество вершин правой доли.

definition= <tex>G</tex> {{---}} '''полунесводимый граф'''(англ. ''semi-irreducible graph''), если <tex>G</tex> имеет ровно одно вершинное покрытие <tex>M</tex>, такое что или <tex>M \cap S</tex> или <tex>M \cap T</tex> {{---}} пусто

<tex>G</tex> {{---}} '''несводимый''' граф(англ. ''irreducible graph''), если он имеет ровно два наименьших вершинных покрытия <tex>M_1</tex> и <tex>M_2</tex>, таких что либо <tex>M_1 \cap S \cup M_2 \cap T = \varnothing </tex>, либо <tex>M_2 \cap S \cup M_1 \cap T = \varnothing</tex>

<tex>G</tex> {{---}} '''сводимый граф''' (англ. ''reducible graph'') если он не является ни полунесводимым, ни сводимымнесводимым.

Сошлемся на теорему <tex>3 (Theorem 3)</tex> аналогичного результата<ref>A. L. Dulmage, and N. S. Mendelsohn "Coverings of bipartite graphs"[https://cms.math.ca/openaccess/cjm/v10/cjm1958v10, 1958, pp.0517-0534519.pdf]</ref> аналогичного результата для двудольных графов. То же самое доказательство можно перенести на произвольный граф.

'''{{ Утверждение|about=Следствие 1''' если |statement=Eсли <tex>G</tex> имеет минимальное вершинное покрытие, которое не является независимым, то <tex>G \neq C_1(G)</tex>.<br>'''}} {{ Утверждение|about=Следствие 2''' если |id=proposal2|statement=Если <tex>G</tex> {{---}} сводимый связный двудольный граф, то <tex>G \neq C_1(G)</tex>.}}  

если Если <tex>G</tex> имеет непустое реберное ядро, то <tex>C_1(G) \supset G</tex>, <tex>C_1(C_1(G)) = C_1(G)</tex>, а компоненты <tex>C_1(G)</tex> являются несводимыми или полунесводимыми двудольными подграфами <tex>G</tex>

{{Теорема|id=th4 |statement=

}} === Примеры ===[[File:Bipartite_graph_1.png|thumb|130px|Двудольный граф <tex>G_1</tex>]][[File:Bipartite_graph_2.png|thumb|130px|proofДвудольный граф <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 = \Rightarrow{u_2, u_3, u_6\}</tex> Пусть . В нём два наименьших вершинных покрытия, именно <tex>G M_2 = C_1(G)\{u_1,u_4, u_5\}</tex> тогда по [[#th3|предыдущей теореме]] и <tex>GN_2 = \{u_2, u_3, u_6\}</tex> является несводимым или полунесводимым двудольным графом.Так как <brtex>M_2 \cap T_2 = \varnothing</tex>и <tex>N_2 \cap S_2 = \Leftarrowvarnothing</tex> Пусть выполнено следствие, то <tex>G_2</tex> {{---}} несводимый граф и, значит, совпадает со своим рёберным ядром.<br>