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

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

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

[Харари]

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