Изменения
Новая страница: «{{Определение| definition= '''Рёберное ядро''' графа <tex>G</tex> {{---}} это подграф графа <tex>G</tex>, порожд...»
{{Определение|
definition=
'''Рёберное ядро''' графа <tex>G</tex> {{---}} это подграф графа <tex>G</tex>, порожденный объединением таких независимых множеств <tex>Y \subset E(G)</tex>, что <tex>|Y| = \alpha_{0}(G)</tex>, где <tex>\alpha_{0}(G)</tex> {{---}} число вершинного покрытия.
}}
{{Определение|
definition=
'''числом вершинного покрытия''' называется число вершин в наименьшем вершинном покрытии графа <tex>G</tex>.
}}
==Критерий существования реберного ядра==
{{Определение|
definition=
Наименьшее вершинное покрытие M графа G с множеством вершим V называется '''внешним''', если для любого подмножества <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>
}}
{{Теорема|
statement=
для произвольного графа <tex>G</tex> следующие утверждения эквивалентны:
(1) <tex>G</tex> имеет рёберное ядро. <br>
(2) <tex>G</tex> имеет внешнее наименьшее вершинное покрытие.
(3) каждое наименьшее вершинное покрытие для <tex>G</tex> является внешним.
}}
definition=
'''Рёберное ядро''' графа <tex>G</tex> {{---}} это подграф графа <tex>G</tex>, порожденный объединением таких независимых множеств <tex>Y \subset E(G)</tex>, что <tex>|Y| = \alpha_{0}(G)</tex>, где <tex>\alpha_{0}(G)</tex> {{---}} число вершинного покрытия.
}}
{{Определение|
definition=
'''числом вершинного покрытия''' называется число вершин в наименьшем вершинном покрытии графа <tex>G</tex>.
}}
==Критерий существования реберного ядра==
{{Определение|
definition=
Наименьшее вершинное покрытие M графа G с множеством вершим V называется '''внешним''', если для любого подмножества <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>
}}
{{Теорема|
statement=
для произвольного графа <tex>G</tex> следующие утверждения эквивалентны:
(1) <tex>G</tex> имеет рёберное ядро. <br>
(2) <tex>G</tex> имеет внешнее наименьшее вершинное покрытие.
(3) каждое наименьшее вершинное покрытие для <tex>G</tex> является внешним.
}}
