Вершинная древесность
Материал из WikiGrapp
Вершинная древесность (Vertex-arboricity) — наименьшее число подмножеств, на которые можно разбить множество вершин графа так, чтобы каждое подмножество порождало лес.
Известно, что для плоского графа
.
См. также
Литература
- Workshop. Aachen, 1995 // Lect. Notes Comp. Sci., 1995, vol. 1017.