Вершинная древесность: различия между версиями
Перейти к навигации
Перейти к поиску
Glk (обсуждение | вклад) (Создана новая страница размером '''Вершинная древесность''' (''Vertex-arboricity'') - наименьшее число <math>a(G)</math> подмно...) |
KEV (обсуждение | вклад) Нет описания правки |
||
| (не показана 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>. | |||
См. также ''Древесность графа''. | ==См. также== | ||
* ''[[Древесность графа]]''. | |||
==Литература== | ==Литература== | ||
* 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.