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

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

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

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

Литература

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