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

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

Версия от 15:44, 7 октября 2009

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

Литература

[Харари]