Рёберное ядро — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(→‎Реберное ядро в двудольном графе)
(→‎Реберное ядро в двудольном графе)
Строка 56: Строка 56:
 
<tex>G</tex> {{---}} '''сводимый граф''' если он не является ни полунесводимым, ни сводимым.
 
<tex>G</tex> {{---}} '''сводимый граф''' если он не является ни полунесводимым, ни сводимым.
 
}}
 
}}
 +
 
{{Теорема|
 
{{Теорема|
 
id=th2|
 
id=th2|
Строка 63: Строка 64:
 
Сошлемся на теорему <tex>(3)</tex> аналогичного результата<ref>A. L. Dulmage and N. S. Mendelsohn, 1958, pp. 517-534.</ref> для двудольных графов. То же самое доказательство можно перенести на произвольный граф.
 
Сошлемся на теорему <tex>(3)</tex> аналогичного результата<ref>A. L. Dulmage and N. S. Mendelsohn, 1958, pp. 517-534.</ref> для двудольных графов. То же самое доказательство можно перенести на произвольный граф.
 
}}
 
}}
−
'''Следствие 1:''' если <tex>G</tex> имеет минимальное вершинное покрытие, которое не является независимым, то  <tex>G \neq C_1(G)</tex>.<br>
+
{{ Утверждение
 +
|about=Следствие 1
 +
|statement=Eсли <tex>G</tex> имеет минимальное вершинное покрытие, которое не является независимым, то  <tex>G \neq C_1(G)</tex>.<br>
 +
}}
 +
 
 +
{{ Утверждение
 +
|about=Следствие 2
 +
|statement=Если <tex>G</tex> {{---}} сводимый связный двудольный граф, то <tex>G \neq C_1(G)</tex>.
 +
}}
  
−
'''Следствие 2:''' если <tex>G</tex> {{---}} сводимый связный двудольный граф, то <tex>G \neq C_1(G)</tex>.
 
  
 
{{Теорема|
 
{{Теорема|

Версия 20:15, 4 октября 2018

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


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


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


Определение:
Числом вершинного покрытия (англ. point-covering number) называется число вершин в наименьшем вершинном покрытии графа [math]G[/math].

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

Определение:
Наименьшее вершинное покрытие M графа G с множеством вершин V называется внешним (англ. external vertex cover), если для любого подмножества [math]M' \subseteq M[/math] выполняется неравенство [math]|M'| \leqslant |U(M')|[/math], где [math]U(M') = \{v \mid \: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]\triangleright[/math]

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

Следовательно, по теореме Холла[1], существует множество [math]s[/math] различных вершин [math]\{y_1, \dots, y_s\}, \: y_j \in Y_j[/math]. Следовательно существует набор независимых ребер [math]y_1v_1, \dots, y_sv_s[/math]. А значит [math]C_1(G)[/math] не может быть пустым.
[math]\triangleleft[/math]
рис. 1. a) граф [math]H[/math], б) реберное ядро графа [math]H[/math]

В качестве примера рассмотрим граф [math]H[/math] изображенный на рис. 1 а). Этот граф имеет два наименьших вершинных покрытия: [math]M_1 = \{B, E, F\}[/math] и [math]M_2 = \{B, E, G\}[/math]. Пусть [math]M_1' = M_1[/math] то [math]U(M_1') = \{A, C, D, G\}[/math]. Пусть [math]M_1'' = \{E, F\}[/math]. Тогда [math]U(M_1'') =\{C, D, G\}[/math]. Отсюда [math]|M_1'| \leqslant |U(M_1')|[/math] и [math]|M_1''| \leqslant |U(M_1'')|[/math]. И это верно для любого подмножества [math]M_1[/math]. Значит, [math]M_1[/math] — внешнее покрытие. Значит и [math]M_2[/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]w \in E(G)[/math] покрыто некоторым минимальным вершинным покрытием, то [math]w \notin C_1(G)[/math].
Доказательство:
[math]\triangleright[/math]
Сошлемся на теорему [math](3)[/math] аналогичного результата[2] для двудольных графов. То же самое доказательство можно перенести на произвольный граф.
[math]\triangleleft[/math]
Утверждение (Следствие 1):
Eсли [math]G[/math] имеет минимальное вершинное покрытие, которое не является независимым, то [math]G \neq C_1(G)[/math].
Утверждение (Следствие 2):
Если [math]G[/math] — сводимый связный двудольный граф, то [math]G \neq C_1(G)[/math].


Теорема:
если [math]G[/math] имеет непустое реберное ядро, то [math]C_1(G) \supset G[/math], [math]C_1(C_1(G)) = C_1(G)[/math], а компоненты [math]C_1(G)[/math] являются несводимыми или полунесводимыми двудольными подграфами [math]G[/math]
Теорема:
[math]G[/math] и его реберное ядро [math]C_1(G)[/math] совпадают тогда и только тогда, когда [math]G[/math] является двудольным и не является сводимым.
Доказательство:
[math]\triangleright[/math]

[math]\Rightarrow[/math] Пусть [math]G = C_1(G)[/math] тогда по предыдущей теореме [math]G[/math] является несводимым или полунесводимым двудольным графом.

[math]\Leftarrow[/math] Пусть выполнено следствие
[math]\triangleleft[/math]

Примечания

  1. ↑ Hall, 1935, pp. 26-30.
  2. ↑ A. L. Dulmage and N. S. Mendelsohn, 1958, pp. 517-534.

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

Источник — «http://neerc.ifmo.ru/wiki/index.php?title=Рёберное_ядро&oldid=66404»