Изменения
Нет описания правки
{{Определение|
definition=
'''Рёберное ядро''' (англ. ''core'') <tex>C_1(G)</tex> графа <tex>G</tex> {{---}} это подграф графа <tex>G</tex>, порожденный объединением таких независимых множеств <tex>Y \subset E(G)</tex>, что <tex>|Y| = \alpha_{0}(G)</tex>, где <tex>\alpha_{0}(G)</tex> {{---}} число вершинного покрытия.
}}
{{Определение|
definition=
'''Вершинным покрытием''' (англ. ''vertex cover'') графа <tex>G</tex> называется такое множество <tex>V</tex> его вершин, что у любого ребра в <tex>G</tex> хотя бы одна из вершин лежит в <tex>V</tex>.
}}
{{Определение|
definition=
'''числом вершинного покрытия''' (англ. ''point-covering number'') называется число вершин в наименьшем вершинном покрытии графа <tex>G</tex>.
}}
==Критерий существования реберного ядра==
{{Определение|
definition=
Наименьшее вершинное покрытие M графа G с множеством вершим V называется '''внешним'''(англ. ''external vertex cover''), если для любого подмножества <tex>M' \subseteq M</tex> выполняется неравнство <tex>|M'| \leqslant |U(M')|</tex>, где <tex>U(M') = \{v| \:v \in V(G) \setminus M, \: vu \in E(G), \: u \in M'\}</tex>.
}}
{{Теорема|
(2) <tex>G</tex> имеет внешнее наименьшее вершинное покрытие.
(3) каждое наименьшее вершинное покрытие для <tex>G</tex> является внешним.
|proof=
Докажем <tex>(1) \Rightarrow (3)</tex>. Предположим, что в <tex>G</tex> существует наименьшее вершинное покрытие, которое не является внешним.
Это значит что <tex>\exists M' : \: M' = \{u_1, \dots, u_r \}, </tex> где <tex>r \leqslant \alpha_0(G)</tex>.
}}
[[Файл:EdgeCore.png|thumb|500px|рис. 1. a) граф <tex>H</tex>, б) реберное ядро графа <tex>H</tex> ]]
