Рёберное ядро

Определение:

Рёберное ядро графа [math]G[/math] — это подграф графа [math]G[/math], порожденный объединением таких независимых множеств [math]Y \subset E(G)[/math], что [math]|Y| = \alpha_{0}(G)[/math], где [math]\alpha_{0}(G)[/math] — число вершинного покрытия.

Определение:

числом вершинного покрытия называется число вершин в наименьшем вершинном покрытии графа [math]G[/math].

Критерий существования реберного ядра

Определение:

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

Теорема:

для произвольного графа [math]G[/math] следующие утверждения эквивалентны: (1) [math]G[/math] имеет рёберное ядро. (2) [math]G[/math] имеет внешнее наименьшее вершинное покрытие. (3) каждое наименьшее вершинное покрытие для [math]G[/math] является внешним.