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

Материал из WEGA
Перейти к навигации Перейти к поиску
(Создана новая страница размером '''Вершинная древесность''' (''Vertex-arboricity'') - наименьшее число <math>a(G)</math> подмно...)
 
Нет описания правки
 
(не показана 1 промежуточная версия этого же участника)
Строка 1: Строка 1:
'''Вершинная древесность''' (''Vertex-arboricity'') -
'''Вершинная древесность''' (''[[Vertex-arboricity]]'') наименьшее число <math>a(G)</math> подмножеств, на которые можно разбить множество [[вершина|вершин]] [[граф|графа]] так, чтобы каждое подмножество порождало [[лес]].  
наименьшее число <math>a(G)</math> подмножеств, на которые можно разбить
Известно, что для [[плоский граф|плоского графа]] <math>a(G) \leq 3</math>.
множество вершин графа так, чтобы каждое подмножество порождало лес.
Известно, что для плоского графа <math>a(G) \leq 3</math>.


См. также ''Древесность графа''.
==См. также==
* ''[[Древесность графа]]''.
==Литература==
==Литература==
[WG'95]
* Workshop. Aachen, 1995 // Lect. Notes Comp. Sci., 1995, vol. 1017.

Текущая версия от 14:49, 26 ноября 2010

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

См. также

Литература

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