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

Материал из Викиконспекты
Перейти к: навигация, поиск
Строка 2: Строка 2:
 
definition=
 
definition=
 
'''Рёберное ядро''' графа <tex>G</tex> {{---}} это подграф графа <tex>G</tex>, порожденный объединением таких независимых множеств <tex>Y \subset E(G)</tex>, что <tex>|Y| = \alpha_{0}(G)</tex>, где <tex>\alpha_{0}(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> {{---}} число вершинного покрытия.
 +
}}
 +
{{Определение|
 +
definition=
 +
'''Вершинным покрытием''' графа <tex>G</tex> называется такое множество <tex>V</tex> его вершин, что у любого ребра в <tex>G</tex> хотя бы одна из вершин лежит в <tex>V</tex>.
 
}}
 
}}
 
{{Определение|
 
{{Определение|

Версия 16:30, 11 января 2016

Определение:
Рёберное ядро графа [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] является двудольным и не является сводимым.