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

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

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

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

Множество ребер (вершин) называется независимым (англ. independent), если никакие его два элемента не смежны.

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

Вершинным покрытием (англ. vertex cover) графа $G$ называется такое множество $V$ его вершин, что у любого ребра в $G$ хотя бы одна из вершин лежит в $V$.

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

Числом вершинного покрытия (англ. point-covering number) называется число вершин в наименьшем вершинном покрытии графа $G$.

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

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

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

Теорема:

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

Доказательство:

$\triangleright$

Обозначим минимальное вершинное покрытие $G$ как $M$. Пусть $U = V(G) \setminus M$. Докажем $(1) \Rightarrow (3)$. Предположим, что в $G$ существует наименьшее вершинное покрытие $M$, которое не является внешним. Это значит что $\exists M' : \: M' = \{u_1, \dots, u_r \},$ где $r \leqslant \alpha_0(G)$, такое что $|M'| \gt |U(M')|.$ Пусть $U(M') = \{u_1, \dots, u_t\}, \: t \lt r$. Так же, пусть $X$ — максимальное независимое множество ребер в $G$. Поскольку никакие две вершины $U$ не смежны, каждое ребро из $X$ соединено, по крайней мере, с одной вершиной из $M$. Если какое-нибудь ребро из $X$ соединено более чем с одной ввершиной из $M$, то $|X| \lt \alpha_0(G)$ и $C_1(G) = \varnothing$. Так что будем считать, что каждое ребро из $X$ смежно ровно с одной вершиной из $M$. Из этого сдедует, что $|X| \leqslant t - r + \alpha_0(g) \lt \alpha_0(G)$. И снова $C_1(G) = \varnothing$. Следствие $(3) \Rightarrow (2)$ — очевидно. Докажем $(2) \Rightarrow (1)$. Пусть $M = \{v_1, \dots, v_s\}$ — наименьшее внешнее вершинное покрытие. Пусть $Y_i = \{u \mid u \in U, uv_i \in E(G) \}$. Тогда для любого $k: \:\: 1 \leqslant k \leqslant s$, объединение любых $k$ различных множеств $Y_i$ содержит, по меньшей мере $k$ вершин. Следовательно, по теореме о свадьбах (Холла), существует множество $s$ различных вершин $\{y_1, \dots, y_s\}, \: y_j \in Y_j$. Следовательно существует набор независимых ребер $y_1v_1, \dots, y_sv_s$. А значит $C_1(G)$ не может быть пустым.

$\triangleleft$

рис. 1. a) граф $H$, б) реберное ядро графа $H$

В качестве примера рассмотрим граф $H$ изображенный на рис. 1 а). Этот граф имеет два наименьших вершинных покрытия: $M_1 = \{B, E, F\}$ и $M_2 = \{B, E, G\}$. Пусть $M_1' = M_1$ то $U(M_1') = \{A, C, D, G\}$. Пусть $M_1'' = \{E, F\}$. Тогда $U(M_1'') =\{C, D, G\}$. Отсюда $|M_1'| \leqslant |U(M_1')|$ и $|M_1''| \leqslant |U(M_1'')|$. И это верно для любого подмножества $M_1$. Значит, $M_1$ — внешнее покрытие. Значит и $M_2$ — внешнее покрытие.

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

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

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

$G$ — полунесводимый граф (англ. semi-irreducible graph), если $G$ имеет ровно одно вершинное покрытие $M$, такое что или $M \cap S$ или $M \cap T$ — пусто

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

$G$ — несводимый граф (англ. irreducible graph), если он имеет ровно два наименьших вершинных покрытия $M_1$ и $M_2$, таких что либо $M_1 \cap S \cup M_2 \cap T = \varnothing$, либо $M_2 \cap S \cup M_1 \cap T = \varnothing$

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

$G$ — сводимый граф (англ. reducible graph) если он не является ни полунесводимым, ни несводимым.

Теорема:

Если оба конца ребра $w \in E(G)$ покрыто некоторым минимальным вершинным покрытием, то $w \notin C_1(G)$.

Доказательство:

$\triangleright$

Сошлемся на теорему 3 (Theorem 3) аналогичного результата для двудольных графов. То же самое доказательство можно перенести на произвольный граф.

$\triangleleft$

Утверждение (Следствие 1):

Eсли $G$ имеет минимальное вершинное покрытие, которое не является независимым, то $G \neq C_1(G)$.

Утверждение (Следствие 2):

Если $G$ — сводимый связный двудольный граф, то $G \neq C_1(G)$.

Теорема:

Если $G$ имеет непустое реберное ядро, то $C_1(G) \supset G$, $C_1(C_1(G)) = C_1(G)$, а компоненты $C_1(G)$ являются несводимыми или полунесводимыми двудольными подграфами $G$

Теорема:

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

Примеры

Двудольный граф $G_1$

Двудольный граф $G_2$

Рассмотрим двудольные графы $G_1$ и $G_2$, изображенные на рисунках 1 и 2. В графе $G_1$ пусть $S_1 = \{v_3, v_6\}$ и $T_1 = \{v_1, v_2, v_4, v_5, v_7 \}$. Этот граф имеет единственное наименьшее вершинное покрытие $M_1 = \{v_3, v_6\}$ и, поскольку $M_1 \cap T_1 = \varnothing$, он полунесводимый; следовательно, он совпадает со своим рёберным ядром. В графе $G_2$ пусть $S_2 = \{u_1, u_4, u_5\}$ и $T_2 = \{u_2, u_3, u_6\}$. В нём два наименьших вершинных покрытия, именно $M_2 = \{u_1,u_4, u_5\}$ и $N_2 = \{u_2, u_3, u_6\}$. Так как $M_2 \cap T_2 = \varnothing$ и $N_2 \cap S_2 = \varnothing$, то $G_2$ — несводимый граф и, значит, совпадает со своим рёберным ядром.

См. также

• NP-полнота задачи о независимом множестве
• Теория Рамсея
• Связь максимального паросочетания и минимального вершинного покрытия в двудольных графах

Источники информации

• P. Hall, On representatives of subsets, Journal of the London Mathematical Society 10 (1935) pp. 26-30.

• A. L. Dulmage and N. S. Mendelsohn: Coverings of bipartite graphs, Canad J. Math., (1958), 517-534.