Линейная древесность

Разбиение графа ромбододекаэдра на два линейных леса , показывающее, что его линейная древесность равна двум

В теории графов , разделе математики, линейная древесность неориентированного графа — это наименьшее количество линейных лесов, на которые можно разбить его ребра. Здесь линейный лес — это ациклический граф максимальной степени два; то есть это непересекающееся объединение графов путей . Линейная древесность — вариант древесности , минимальное количество лесов, на которые можно разделить опушки.

Линейная древесность любого графа максимальной степени $\Delta$ известно как минимум $\lceil \Delta /2\rceil$ и предполагается, что это не более $\lceil (\Delta +1)/2\rceil$. Эта гипотеза определила бы линейную древесность именно для графов нечетной степени, поскольку в этом случае оба выражения равны. Для графов четной степени это означало бы, что линейная древесность должна быть одним из двух возможных значений, но определение точного значения среди этих двух вариантов является NP-полным .

Отношение к степени

Нерешенная задача по математике :

Каждый ли граф максимальной степени $\Delta$ имеют не более линейной древесности $\lceil (\Delta +1)/2\rceil$?

(еще нерешенные задачи по математике)

Линейная древесность графа $G$ с максимальной степенью $\Delta$ всегда как минимум $\lceil \Delta /2\rceil$, поскольку каждый линейный лес может использовать только два ребра в вершине максимальной степени. Гипотеза линейной древесности о Акиямы, Эксоо и Харари (1981) заключается в том, что эта нижняя граница также точна: согласно их гипотезе, каждый граф имеет линейную древесность не более $\lceil (\Delta +1)/2\rceil$. Однако это остается недоказанным: наиболее доказанная верхняя граница линейной древесности несколько больше: $\Delta /2+O(\Delta ^{2/3-c})$ для некоторой константы $c>0$ благодаря Ферберу, Фоксу и Джайну.

Чтобы линейная древесность графа была равна $\Delta /2$, $\Delta$ должен быть четным и каждый линейный лес должен иметь по два ребра, инцидентных каждой вершине степени $\Delta$. Но в вершине, которая находится в конце пути, лес, содержащий этот путь, имеет только одно инцидентное ребро, поэтому степень в этой вершине не может равняться $\Delta$. Таким образом, граф, линейная древесность которого равна $\Delta /2$ должно иметь несколько вершин, степень которых меньше максимальной. В регулярном графе таких вершин нет и линейная древесность не может равняться $\Delta /2$. Следовательно, для регулярных графов гипотеза о линейной древесности означает, что линейная древесность в точности равна $\lceil (\Delta +1)/2\rceil$.

Связанные проблемы

Линейная древесность — это разновидность древесности , минимального количества лесов, на которые могут быть разбиты ребра графа. Исследователи также изучили линейную k -древесность, вариант линейной древесности, при котором каждый путь в линейном лесу может иметь не более k ребер.

Другая связанная с этим проблема — гамильтонова разложение , проблема разложения регулярного графа четной степени. $\Delta$ точно в $\Delta /2$ Гамильтоновы циклы . Данный граф имеет гамильтоново разложение тогда и только тогда, когда подграф, образованный удалением произвольной вершины из графа, имеет линейную древесность. $\Delta /2$.

Вычислительная сложность

В отличие от древесности, которую можно определить за полиномиальное время , линейная древесность является NP-трудной . Даже признание графов линейной древесности два является NP-полным . Однако для кубических графов и других графов максимальной степени три линейная древесность всегда равна двум, а разложение на два линейных леса можно найти за линейное время с помощью алгоритма, основанного на поиске в глубину .