Линейная древовидность неориентированного графа — это наименьшее число линейных лесов, на которые может быть разбит граф. Здесь линейный лес — это ациклический граф с максимальной степенью два, то есть дизъюнктное объединение путей.
Линейная древовидность графа с максимальной степенью всегда не меньше , поскольку каждый линейный лес может использовать только два из рёбер вершины максимальной степени. Гипотеза о линейной древесности Акиямы, Экзоо и Харари утверждает, чта это нижняя граница точна. Согласно этой гипотезе любой граф имеет линейную древовидность, не превосходящую . Однако гипотеза остаётся недоказанной, и лучшая доказанная верхняя грань линейной древесности несколько выше, с некоторой константой (согласно Ферберу, Фоксу и Джейну).
В регулярном графе линейная древовидность не может быть равна , поскольку конечные точки любого пути в одном из линейных лесов не могут иметь две смежные вершины, использованные в этом лесе. Поэтому, для регулярных графов, из гипотезы о линейной древесности следует, что линейная древовидность в точности равна .
Линейная древовидность является вариацией древесности графа, минимального числа лесов, на которые могут быть разбиты рёбра графа. Исследовалась также линейная -древовидность, вариант линейной древесности, в которой любой путь в линейном лесе может иметь не более рёбер.
В отличие от древесности, которая может быть установлена за полиномиальное время, задача установления линейной древесности NP-трудна. Даже распознавание графов с линейной древовидностью два является NP-полной задачей. Однако для кубических графов и других графов с максимальной степенью три линейная древовидность всегда равна двум, а разложение на два линейных леса может быть найдено за линейное время с помощью алгоритма, основанного на поиске в глубину.
Примечания
Литература
Категория:Инварианты графов