Изменения
Нет описания правки
(2) <tex>G</tex> имеет внешнее наименьшее вершинное покрытие.
(3) каждое наименьшее вершинное покрытие для <tex>G</tex> является внешним.
}}
==Ребероне ядро в двудольном графе==
Здесь и далее будем рассматривать двудольный граф <tex>G</tex>, в котором обозначим <tex>S</tex> - множество вершин левой доли, <tex>T</tex> - множество вершин правой доли.
{{Определение |
definition= <tex>G</tex> {{---}} '''полунесводимый граф''', если <tex>G</tex> имеет ровно одно вершинное покрытие <tex>M</tex>, такое что или <tex>M \cap S</tex> или <tex>M \cap T</tex> {{---}} пусто
}}
{{Определение|
definition=
<tex>G</tex> {{---}} '''несводимый''' граф, если он имеет ровно два наименьших вершинных покрытия <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>
}}
{{Определение|
definition=
<tex>G</tex> {{---}} '''сводимый граф''' если он не является ни полунесводимым, ни сводимым.
}}
{{Теорема|
statement=
<tex>G</tex> и его реберное ядро <tex>C_1(G)</tex> совпадают тогда и только тогда, когда <tex>G</tex> является двудольным и не является сводимым.
}}
