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

Материал из Викиконспекты
Перейти к: навигация, поиск
м (rollbackEdits.php mass rollback)
 
(не показано 26 промежуточных версий 3 участников)
Строка 6: Строка 6:
 
{{Определение|
 
{{Определение|
 
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>.
 
}}
 
}}
Строка 19: Строка 20:
 
{{Определение|
 
{{Определение|
 
definition=
 
definition=
Наименьшее вершинное покрытие M графа G с множеством вершин V называется '''внешним''' (англ. ''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>.  
+
Наименьшее вершинное покрытие <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> имеет внешнее наименьшее вершинное покрытие.
Строка 35: Строка 36:
 
Докажем <tex>(2) \Rightarrow (1)</tex>.
 
Докажем <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>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> вершин.  
Следовательно, по теореме Холла<ref>Hall, 1935, pp. 26-30.</ref>, существует множество <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> не может быть пустым.
+
Следовательно, по [[Теорема Холла|теореме о свадьбах (Холла)]], существует множество <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> ]]
Строка 46: Строка 47:
 
Здесь и далее будем рассматривать [[Двудольные графы|двудольный граф]] <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'') если он не является ни полунесводимым, ни несводимым.
 
}}
 
}}
  
Строка 62: Строка 63:
 
Если оба конца ребра <tex>w \in E(G)</tex> покрыто некоторым минимальным вершинным покрытием, то <tex>w \notin C_1(G)</tex>.
 
Если оба конца ребра <tex>w \in E(G)</tex> покрыто некоторым минимальным вершинным покрытием, то <tex>w \notin C_1(G)</tex>.
 
|proof=
 
|proof=
Сошлемся на теорему <tex>(3)</tex> аналогичного результата<ref>A. L. Dulmage and N. S. Mendelsohn, 1958, pp. 517-534.</ref> для двудольных графов. То же самое доказательство можно перенести на произвольный граф.
+
Сошлемся на теорему 3 (Theorem 3)<ref>A. L. Dulmage and N. S. Mendelsohn, 1958, pp. 519.</ref> аналогичного результата для двудольных графов. То же самое доказательство можно перенести на произвольный граф.
 
}}
 
}}
 
{{ Утверждение
 
{{ Утверждение
Строка 79: Строка 80:
 
id=th3|
 
id=th3|
 
statement=
 
statement=
если <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>
+
Если <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 |
+
|id=th4
statement=
+
|statement=
 
<tex>G</tex> и его реберное ядро <tex>C_1(G)</tex> совпадают тогда и только тогда, когда <tex>G</tex> является двудольным и не является сводимым.
 
<tex>G</tex> и его реберное ядро <tex>C_1(G)</tex> совпадают тогда и только тогда, когда <tex>G</tex> является двудольным и не является сводимым.
|proof=
+
}}
<tex>\Rightarrow</tex> Пусть <tex>G = C_1(G)</tex> тогда по [[#th3|предыдущей теореме]] <tex>G</tex> является несводимым или полунесводимым двудольным графом.<br>
+
 
<tex>\Leftarrow</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-полнота задачи о независимом множестве]]
 +
* [[Теория Рамсея]]
 +
* [[Связь максимального паросочетания и минимального вершинного покрытия в двудольных графах]]
  
 
==Примечания==
 
==Примечания==
Строка 100: Строка 109:
  
 
* [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.]
 
* [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) C1(G) графа G — это подграф графа G, порожденный объединением таких независимых множеств YE(G), что |Y|=α0(G), где α0(G) — число вершинного покрытия.


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


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


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

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

Определение:
Наименьшее вершинное покрытие M графа G с множеством вершин V называется внешним (англ. external vertex cover), если для любого подмножества MM выполняется неравенство |M||U(M)|, где U(M)={vvV(G)M,vuE(G),uM}.
Теорема:
Для произвольного графа G следующие утверждения эквивалентны:

(1) G имеет не пустое рёберное ядро.
(2) G имеет внешнее наименьшее вершинное покрытие.

(3) каждое наименьшее вершинное покрытие для G является внешним.
Доказательство:

Обозначим минимальное вершинное покрытие G как M. Пусть U=V(G)M.
Докажем (1)(3). Предположим, что в G существует наименьшее вершинное покрытие M, которое не является внешним. Это значит что M:M={u1,,ur}, где rα0(G), такое что |M|>|U(M)|. Пусть U(M)={u1,,ut},t<r. Так же, пусть X — максимальное независимое множество ребер в G. Поскольку никакие две вершины U не смежны, каждое ребро из X соединено, по крайней мере, с одной вершиной из M. Если какое-нибудь ребро из X соединено более чем с одной ввершиной из M, то |X|<α0(G) и C1(G)=. Так что будем считать, что каждое ребро из X смежно ровно с одной вершиной из M. Из этого сдедует, что |X|tr+α0(g)<α0(G). И снова C1(G)=.
Следствие (3)(2) — очевидно.
Докажем (2)(1). Пусть M={v1,,vs} — наименьшее внешнее вершинное покрытие. Пусть Yi={uuU,uviE(G)}. Тогда для любого k:1ks, объединение любых k различных множеств Yi содержит, по меньшей мере k вершин.

Следовательно, по теореме о свадьбах (Холла), существует множество s различных вершин {y1,,ys},yjYj. Следовательно существует набор независимых ребер y1v1,,ysvs. А значит C1(G) не может быть пустым.
рис. 1. a) граф H, б) реберное ядро графа H

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

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

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

Определение:
Gполунесводимый граф (англ. semi-irreducible graph), если G имеет ровно одно вершинное покрытие M, такое что или MS или MT — пусто


Определение:
Gнесводимый граф (англ. irreducible graph), если он имеет ровно два наименьших вершинных покрытия M1 и M2, таких что либо M1SM2T=, либо M2SM1T=


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


Теорема:
Если оба конца ребра wE(G) покрыто некоторым минимальным вершинным покрытием, то wC1(G).
Доказательство:
Сошлемся на теорему 3 (Theorem 3)[1] аналогичного результата для двудольных графов. То же самое доказательство можно перенести на произвольный граф.
Утверждение (Следствие 1):
Eсли G имеет минимальное вершинное покрытие, которое не является независимым, то GC1(G).
Утверждение (Следствие 2):
Если G — сводимый связный двудольный граф, то GC1(G).


Теорема:
Если G имеет непустое реберное ядро, то C1(G)G, C1(C1(G))=C1(G), а компоненты C1(G) являются несводимыми или полунесводимыми двудольными подграфами G
Теорема:
G и его реберное ядро C1(G) совпадают тогда и только тогда, когда G является двудольным и не является сводимым.

Примеры

Двудольный граф G1
Двудольный граф G2

Рассмотрим двудольные графы G1 и G2, изображенные на рисунках 1 и 2. В графе G1 пусть S1={v3,v6} и T1={v1,v2,v4,v5,v7}. Этот граф имеет единственное наименьшее вершинное покрытие M1={v3,v6} и, поскольку M1T1=, он полунесводимый; следовательно, он совпадает со своим рёберным ядром. В графе G2 пусть S2={u1,u4,u5} и T2={u2,u3,u6}. В нём два наименьших вершинных покрытия, именно M2={u1,u4,u5} и N2={u2,u3,u6}. Так как M2T2= и N2S2=, то G2 — несводимый граф и, значит, совпадает со своим рёберным ядром.

См. также

Примечания

  1. Перейти A. L. Dulmage and N. S. Mendelsohn, 1958, pp. 519.

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