4194
правки
Вершинная древесность: различия между версиями
Перейти к навигации
Перейти к поиску
нет описания правки
KEV (обсуждение | вклад) Нет описания правки |
KEV (обсуждение | вклад) Нет описания правки |
||
| Строка 1: | Строка 1: | ||
'''Вершинная древесность''' (''[[Vertex-arboricity]]'') | '''Вершинная древесность''' (''[[Vertex-arboricity]]'') — наименьшее число <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. | |||