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

Материал из Викиконспекты
Перейти к: навигация, поиск
м (rollbackEdits.php mass rollback)
 
(не показаны 53 промежуточные версии 7 участников)
Строка 1: Строка 1:
 
{{Определение|
 
{{Определение|
 
definition=
 
definition=
'''Рёберное ядро''' (англ. ''core'') <tex>C_1(G)</tex> графа <tex>G</tex> {{---}} это подграф графа <tex>G</tex>, порожденный объединением таких независимых множеств <tex>Y \subset E(G)</tex>, что <tex>|Y| = \alpha_{0}(G)</tex>, где <tex>\alpha_{0}(G)</tex> {{---}} число вершинного покрытия.
+
'''Рёберное ядро''' (англ. ''core'') <tex>C_1(G)</tex> графа <tex>G</tex> {{---}} это подграф [[Основные определения теории графов#finite graph|графа]] <tex>G</tex>, порожденный объединением таких независимых множеств <tex>Y \subset E(G)</tex>, что <tex>|Y| = \alpha_{0}(G)</tex>, где <tex>\alpha_{0}(G)</tex> {{---}} число вершинного покрытия.
 
}}
 
}}
  
 
{{Определение|
 
{{Определение|
 
definition=  
 
definition=  
Множество ребер (вершин) называется '''независимым''' (англ. ''independent''), если никакие его два элемента не смежны.
+
Множество [[Основные определения теории графов#def_graph_edge_1|ребер]] (вершин) называется '''независимым''' (англ. ''independent''), если никакие его два элемента не смежны.
 
}}
 
}}
{{Определение|
+
{{Определение
definition=
+
|id=def_3
 +
|definition=
 
'''Вершинным покрытием''' (англ. ''vertex cover'') графа <tex>G</tex> называется такое множество <tex>V</tex> его вершин, что у любого ребра в <tex>G</tex> хотя бы одна из вершин лежит в <tex>V</tex>.
 
'''Вершинным покрытием''' (англ. ''vertex cover'') графа <tex>G</tex> называется такое множество <tex>V</tex> его вершин, что у любого ребра в <tex>G</tex> хотя бы одна из вершин лежит в <tex>V</tex>.
 
}}
 
}}
 
{{Определение|
 
{{Определение|
 
definition=
 
definition=
'''числом вершинного покрытия''' (англ. ''point-covering number'') называется число вершин в наименьшем вершинном покрытии графа <tex>G</tex>.
+
'''Числом вершинного покрытия''' (англ. ''point-covering number'') называется число вершин в наименьшем вершинном покрытии графа <tex>G</tex>.
 
}}
 
}}
 
==Критерий существования реберного ядра==
 
==Критерий существования реберного ядра==
 
{{Определение|
 
{{Определение|
 
definition=
 
definition=
Наименьшее вершинное покрытие M графа G с множеством вершим V называется '''внешним''' (англ. ''external vertex cover''), если для любого подмножества <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>.  
+
Наименьшее вершинное покрытие <tex>M</tex> графа <tex>G</tex> с множеством вершин <tex>V</tex> называется '''внешним''' (англ. ''external vertex cover''), если для любого подмножества <tex>M' \subseteq M</tex> выполняется неравенство <tex>|M'| \leqslant |U(M')|</tex>, где <tex>U(M') = \{v \mid \:v \in V(G) \setminus  M,  \: vu \in E(G), \: u \in M'\}</tex>.  
 
}}
 
}}
 
{{Теорема|
 
{{Теорема|
 
statement=
 
statement=
для произвольного графа <tex>G</tex> следующие утверждения эквивалентны:
+
Для произвольного графа <tex>G</tex> следующие утверждения эквивалентны:
(1) <tex>G</tex> имеет рёберное ядро. <br>
+
(1) <tex>G</tex> имеет не пустое рёберное ядро. <br>
 
(2) <tex>G</tex> имеет внешнее наименьшее вершинное покрытие.
 
(2) <tex>G</tex> имеет внешнее наименьшее вершинное покрытие.
 
(3) каждое наименьшее вершинное покрытие для <tex>G</tex> является внешним.
 
(3) каждое наименьшее вершинное покрытие для <tex>G</tex> является внешним.
Строка 31: Строка 32:
 
Докажем <tex>(1) \Rightarrow (3)</tex>. Предположим, что в <tex>G</tex> существует наименьшее вершинное покрытие <tex>M</tex>, которое не является внешним.
 
Докажем <tex>(1) \Rightarrow (3)</tex>. Предположим, что в <tex>G</tex> существует наименьшее вершинное покрытие <tex>M</tex>, которое не является внешним.
 
Это значит что <tex>\exists M' : \:  M' = \{u_1, \dots,  u_r \}, </tex> где <tex>r \leqslant \alpha_0(G)</tex>,
 
Это значит что <tex>\exists M' : \:  M' = \{u_1, \dots,  u_r \}, </tex> где <tex>r \leqslant \alpha_0(G)</tex>,
такое что <tex>|M'| > |U(M')|.</tex> Пусть <tex>U(M') = \{u_1, \dots, u_t\}, \: t < r</tex>. Так же, пусть <tex>X</tex> {{---}} максимальное множество независимое множество ребер в <tex>G</tex>. Поскольку никакие две вершины <tex>U</tex> не смежны, каждое ребро из <tex>X</tex> соединено, по крайней мере, с одной вершиной из <tex>M</tex>.
+
такое что <tex>|M'| > |U(M')|.</tex> Пусть <tex>U(M') = \{u_1, \dots, u_t\}, \: t < r</tex>. Так же, пусть <tex>X</tex> {{---}} максимальное независимое множество ребер в <tex>G</tex>. Поскольку никакие две вершины <tex>U</tex> не смежны, каждое ребро из <tex>X</tex> соединено, по крайней мере, с одной вершиной из <tex>M</tex>. Если какое-нибудь ребро из <tex>X</tex> соединено более чем с одной ввершиной из <tex>M</tex>, то <tex>|X| < \alpha_0(G)</tex> и <tex>C_1(G) = \varnothing </tex>. Так что будем считать, что каждое ребро из <tex>X</tex> смежно ровно с одной вершиной из <tex>M</tex>. Из этого сдедует, что <tex>|X| \leqslant t - r + \alpha_0(g) < \alpha_0(G)</tex>. И снова <tex>C_1(G) = \varnothing</tex>.<br>
 +
Следствие <tex>(3) \Rightarrow (2)</tex> {{---}} очевидно. <br>
 +
Докажем <tex>(2) \Rightarrow (1)</tex>.
 +
Пусть <tex>M = \{v_1, \dots, v_s\}</tex> {{---}} наименьшее внешнее вершинное покрытие. Пусть <tex>Y_i = \{u \mid u \in U, uv_i \in E(G) \}</tex>. Тогда для любого <tex>k: \:\: 1 \leqslant k \leqslant s</tex>, объединение любых <tex>k</tex> различных множеств <tex>Y_i</tex> содержит, по меньшей мере <tex>k</tex> вершин.
 +
Следовательно, по [[Теорема Холла|теореме о свадьбах (Холла)]], существует множество <tex>s</tex> различных вершин <tex>\{y_1, \dots, y_s\}, \: y_j \in Y_j</tex>. Следовательно существует набор независимых ребер <tex>y_1v_1, \dots, y_sv_s</tex>. А значит <tex>C_1(G)</tex> не может быть пустым.
 
}}
 
}}
 
[[Файл:EdgeCore.png|thumb|500px|рис. 1. a) граф <tex>H</tex>, б) реберное ядро графа <tex>H</tex> ]]
 
[[Файл:EdgeCore.png|thumb|500px|рис. 1. a) граф <tex>H</tex>, б) реберное ядро графа <tex>H</tex> ]]
В качестве примера рассмотрим граф H изображенный на рис. 1 а). Этот граф имеет два наименьших вершинных покрытия: <tex>M_1 = \{B, E, F\}</tex> и <tex>M_2 = \{B, E, G\}</tex>.
+
В качестве примера рассмотрим граф <tex>H</tex> изображенный на рис. 1 а). Этот граф имеет два наименьших вершинных покрытия: <tex>M_1 = \{B, E, F\}</tex> и <tex>M_2 = \{B, E, G\}</tex>.
 
Пусть <tex>M_1' = M_1</tex> то <tex>U(M_1') = \{A, C, D, G\}</tex>. Пусть <tex>M_1'' = \{E, F\}</tex>. Тогда <tex>U(M_1'')  =\{C, D, G\}</tex>.
 
Пусть <tex>M_1' = M_1</tex> то <tex>U(M_1') = \{A, C, D, G\}</tex>. Пусть <tex>M_1'' = \{E, F\}</tex>. Тогда <tex>U(M_1'')  =\{C, D, G\}</tex>.
 
Отсюда <tex>|M_1'| \leqslant |U(M_1')|</tex> и <tex>|M_1''| \leqslant |U(M_1'')|</tex>. И это верно для любого подмножества <tex>M_1</tex>. Значит, <tex>M_1</tex> {{---}} внешнее покрытие. Значит и <tex>M_2</tex> {{---}} внешнее покрытие.
 
Отсюда <tex>|M_1'| \leqslant |U(M_1')|</tex> и <tex>|M_1''| \leqslant |U(M_1'')|</tex>. И это верно для любого подмножества <tex>M_1</tex>. Значит, <tex>M_1</tex> {{---}} внешнее покрытие. Значит и <tex>M_2</tex> {{---}} внешнее покрытие.
Строка 40: Строка 45:
  
 
==Реберное ядро в двудольном графе==
 
==Реберное ядро в двудольном графе==
Здесь и далее будем рассматривать двудольный граф <tex>G</tex>, в котором обозначим <tex>S</tex> - множество вершин левой доли, <tex>T</tex> - множество вершин правой доли.
+
Здесь и далее будем рассматривать [[Двудольные графы|двудольный граф]] <tex>G</tex>, в котором обозначим <tex>S</tex> {{---}} множество вершин левой доли, <tex>T</tex> {{---}} множество вершин правой доли.
 
{{Определение |
 
{{Определение |
definition= <tex>G</tex> {{---}} '''полунесводимый граф''', если <tex>G</tex> имеет ровно одно вершинное покрытие <tex>M</tex>, такое что или <tex>M \cap S</tex> или <tex>M \cap T</tex> {{---}} пусто
+
definition= <tex>G</tex> {{---}} '''полунесводимый граф''' (англ. ''semi-irreducible graph''), если <tex>G</tex> имеет ровно одно вершинное покрытие <tex>M</tex>, такое что или <tex>M \cap S</tex> или <tex>M \cap T</tex> {{---}} пусто
 
}}
 
}}
 
{{Определение|
 
{{Определение|
 
definition=  
 
definition=  
<tex>G</tex> {{---}} '''несводимый''' граф, если он имеет ровно два наименьших вершинных покрытия <tex>M_1</tex> и <tex>M_2</tex>, таких что либо <tex>M_1 \cap S \cup M_2 \cap T = \varnothing </tex>, либо <tex>M_2 \cap S \cup M_1 \cap T = \varnothing</tex>
+
<tex>G</tex> {{---}} '''несводимый''' граф (англ. ''irreducible graph''), если он имеет ровно два наименьших вершинных покрытия <tex>M_1</tex> и <tex>M_2</tex>, таких что либо <tex>M_1 \cap S \cup M_2 \cap T = \varnothing </tex>, либо <tex>M_2 \cap S \cup M_1 \cap T = \varnothing</tex>
 
}}
 
}}
 
{{Определение|
 
{{Определение|
 
definition=
 
definition=
<tex>G</tex> {{---}} '''сводимый граф''' если он не является ни полунесводимым, ни сводимым.
+
<tex>G</tex> {{---}} '''сводимый граф''' (англ. ''reducible graph'') если он не является ни полунесводимым, ни несводимым.
 +
}}
 +
 
 +
{{Теорема|
 +
id=th2|
 +
statement=
 +
Если оба конца ребра <tex>w \in E(G)</tex> покрыто некоторым минимальным вершинным покрытием, то <tex>w \notin C_1(G)</tex>.
 +
|proof=
 +
Сошлемся на теорему 3 (Theorem 3)<ref>A. L. Dulmage and N. S. Mendelsohn, 1958, pp. 519.</ref> аналогичного результата для двудольных графов. То же самое доказательство можно перенести на произвольный граф.
 +
}}
 +
{{ Утверждение
 +
|about=Следствие 1
 +
|statement=Eсли <tex>G</tex> имеет минимальное вершинное покрытие, которое не является независимым, то  <tex>G \neq C_1(G)</tex>.<br>
 +
}}
 +
 
 +
{{ Утверждение
 +
|about=Следствие 2
 +
|id=proposal2
 +
|statement=Если <tex>G</tex> {{---}} сводимый связный двудольный граф, то <tex>G \neq C_1(G)</tex>.
 
}}
 
}}
 +
 +
 
{{Теорема|
 
{{Теорема|
 +
id=th3|
 
statement=
 
statement=
<tex>G</tex> и его реберное ядро <tex>C_1(G)</tex> совпадают тогда и только тогда, когда <tex>G</tex> является двудольным и не является сводимым.
+
Если <tex>G</tex> имеет непустое реберное ядро, то <tex>C_1(G) \supset G</tex>, <tex>C_1(C_1(G)) = C_1(G)</tex>, а компоненты <tex>C_1(G)</tex> являются несводимыми или полунесводимыми двудольными подграфами <tex>G</tex>
 
}}
 
}}
 +
 +
{{Теорема
 +
|id=th4
 +
|statement=
 +
<tex>G</tex> и его реберное ядро <tex>C_1(G)</tex> совпадают тогда и только тогда, когда <tex>G</tex> является двудольным и не является сводимым.
 +
}}
 +
 +
=== Примеры ===
 +
[[File:Bipartite_graph_1.png|thumb|130px|Двудольный граф <tex>G_1</tex>]]
 +
[[File:Bipartite_graph_2.png|thumb|130px|Двудольный граф <tex>G_2</tex>]]
 +
 +
Рассмотрим двудольные графы <tex>G_1</tex> и <tex>G_2</tex>, изображенные на рисунках 1 и 2. В графе <tex>G_1</tex> пусть <tex>S_1 = \{v_3, v_6\}</tex> и <tex>T_1 = \{v_1, v_2, v_4, v_5, v_7 \}</tex>. Этот граф имеет единственное наименьшее вершинное покрытие <tex>M_1 = \{v_3, v_6\}</tex> и, поскольку <tex>M_1 \cap T_1 = \varnothing</tex>, он полунесводимый; следовательно, он совпадает со своим рёберным ядром. В графе <tex>G_2</tex> пусть <tex>S_2 = \{u_1, u_4, u_5\}</tex> и <tex>T_2 = \{u_2, u_3, u_6\}</tex>. В нём два наименьших вершинных покрытия, именно <tex>M_2 = \{u_1,u_4, u_5\}</tex> и <tex>N_2 = \{u_2, u_3, u_6\}</tex>. Так как <tex>M_2 \cap T_2 = \varnothing</tex> и <tex>N_2 \cap S_2 = \varnothing</tex>, то <tex>G_2</tex> {{---}} несводимый граф и, значит, совпадает со своим рёберным ядром.
 +
<br>
 +
 +
== См. также ==
 +
* [[NP-полнота задачи о независимом множестве]]
 +
* [[Теория Рамсея]]
 +
* [[Связь максимального паросочетания и минимального вершинного покрытия в двудольных графах]]
 +
 +
==Примечания==
 +
<references />
 +
 +
== Источники информации ==
 +
 +
* [https://math.dartmouth.edu/archive/m38s12/public_html/sources/Hall1935.pdf P. Hall, On representatives of subsets, Journal of the London Mathematical Society 10 (1935) pp. 26-30.]
 +
 +
* [https://cms.math.ca/openaccess/cjm/v10/cjm1958v10.0517-0534.pdf A. L. Dulmage and N. S. Mendelsohn: Coverings of bipartite graphs, Canad J. Math., (1958), 517-534.]
 +
 +
[[Категория: Алгоритмы и структуры данных]]
 +
[[Категория: Основные определения теории графов]]

Текущая версия на 19:07, 4 сентября 2022

Определение:
Рёберное ядро (англ. 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].

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

Определение:
Наименьшее вершинное покрытие [math]M[/math] графа [math]G[/math] с множеством вершин [math]V[/math] называется внешним (англ. 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] вершин.

Следовательно, по теореме о свадьбах (Холла), существует множество [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]полунесводимый граф (англ. semi-irreducible graph), если [math]G[/math] имеет ровно одно вершинное покрытие [math]M[/math], такое что или [math]M \cap S[/math] или [math]M \cap T[/math] — пусто


Определение:
[math]G[/math]несводимый граф (англ. irreducible graph), если он имеет ровно два наименьших вершинных покрытия [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]сводимый граф (англ. reducible graph) если он не является ни полунесводимым, ни несводимым.


Теорема:
Если оба конца ребра [math]w \in E(G)[/math] покрыто некоторым минимальным вершинным покрытием, то [math]w \notin C_1(G)[/math].
Доказательство:
[math]\triangleright[/math]
Сошлемся на теорему 3 (Theorem 3)[1] аналогичного результата для двудольных графов. То же самое доказательство можно перенести на произвольный граф.
[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]G_1[/math]
Двудольный граф [math]G_2[/math]

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

См. также

Примечания

  1. A. L. Dulmage and N. S. Mendelsohn, 1958, pp. 519.

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