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

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

Рёберное ядро графа [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] называется такое множество [math]V[/math] его вершин, что у любого ребра в [math]G[/math] хотя бы одна из вершин лежит в [math]V[/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] является внешним.

Ребероне ядро в двудольном графе

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

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

[math]G[/math] — полунесводимый граф, если [math]G[/math] имеет ровно одно вершинное покрытие [math]M[/math], такое что или [math]M \cap S[/math] или [math]M \cap T[/math] — пусто

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

[math]G[/math] — несводимый граф, если он имеет ровно два наименьших вершинных покрытия [math]M_1[/math] и [math]M_2[/math], таких что либо [math]M_1 \cap S \cup M_2 \cap T = \varnothing [/math], либо [math]M_2 \cap S \cup M_1 \cap T = \varnothing[/math]

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

[math]G[/math] — сводимый граф если он не является ни полунесводимым, ни сводимым.

Теорема:

[math]G[/math] и его реберное ядро [math]C_1(G)[/math] совпадают тогда и только тогда, когда [math]G[/math] является двудольным и не является сводимым.