Вершинное ядро: различия между версиями

Материал из WEGA
Перейти к навигации Перейти к поиску
(Создана новая страница размером '''Вершинное ядро''' (''Vertex kernel'') - подграф, порожденный объединением всех ''нез...)
 
Нет описания правки
 
(не показана 1 промежуточная версия этого же участника)
Строка 1: Строка 1:
'''Вершинное ядро''' (''Vertex kernel'') -
'''Вершинное ядро''' (''[[Vertex kernel]]'') — [[подграф]], порожденный объединением всех ''независимых множеств'' [[граф|графа]], мощность которых равна ''[[число реберного покрытия|числу реберного покрытия]]'' графа.
подграф, порожденный объединением всех ''независимых множеств'' графа, мощность которых равна ''числу реберного покрытия'' графа.
Граф содержит '''вершинное ядро''' тогда и только тогда, когда он имеет ''[[реберное ядро]]''.
Граф содержит '''В.я.''' тогда и только тогда, когда он имеет ''реберное ядро''.
==Литература==
==Литература==
[Харари]
* Харари Ф. Теория графов. —  М.: Мир, 1973.

Текущая версия от 15:26, 26 ноября 2010

Вершинное ядро (Vertex kernel) — подграф, порожденный объединением всех независимых множеств графа, мощность которых равна числу реберного покрытия графа. Граф содержит вершинное ядро тогда и только тогда, когда он имеет реберное ядро.

Литература

  • Харари Ф. Теория графов. — М.: Мир, 1973.