Вершинное ядро

Материал из WEGA
Версия от 14:09, 1 октября 2009; Glk (обсуждение | вклад) (Создана новая страница размером '''Вершинное ядро''' (''Vertex kernel'') - подграф, порожденный объединением всех ''нез...)
(разн.) ← Предыдущая версия | Текущая версия (разн.) | Следующая версия → (разн.)
Перейти к навигации Перейти к поиску

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

Литература

[Харари]