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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Новая страница: «{{Определение| definition= '''Рёберное ядро''' графа <tex>G</tex> {{---}} это подграф графа <tex>G</tex>, порожд...»)
(нет различий)

Версия 21:17, 12 ноября 2015

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

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

Определение:
Наименьшее вершинное покрытие 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] является внешним.