Вершинная древесность

Материал из WEGA
Версия от 13:38, 1 октября 2009; Glk (обсуждение | вклад) (Создана новая страница размером '''Вершинная древесность''' (''Vertex-arboricity'') - наименьшее число <math>a(G)</math> подмно...)
(разн.) ← Предыдущая версия | Текущая версия (разн.) | Следующая версия → (разн.)

Вершинная древесность (Vertex-arboricity) - наименьшее число [math]\displaystyle{ a(G) }[/math] подмножеств, на которые можно разбить множество вершин графа так, чтобы каждое подмножество порождало лес. Известно, что для плоского графа [math]\displaystyle{ a(G) \leq 3 }[/math].

См. также Древесность графа.

Литература

[WG'95]