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

Материал из WikiGrapp
Версия от 14:49, 26 ноября 2010; KEV (обсуждение | вклад)
(разн.) ← Предыдущая версия | Текущая версия (разн.) | Следующая версия → (разн.)

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

См. также

Литература

  • Workshop. Aachen, 1995 // Lect. Notes Comp. Sci., 1995, vol. 1017.