PROFILPELAJAR.COM

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

Нерешённые проблемы математики: Любой граф с максимальной степенью $\Delta$ имеет линейную древесность, не превосходящую $\lceil (\Delta +1)/2\rceil$ ?

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

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

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

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

Примечания

↑ Akiyama, Exoo, Harary, 1981.
↑ Akiyama, Exoo, Harary, 1981, с. 69–72.
↑ Ferber, Fox, Jain, 2018.
↑ Alon, Teague, Wormald, 2001, с. 11–16.
↑ Shermer, 1996, с. 234–239.
↑ Duncan, Eppstein, Kobourov, 2004, с. 340–346.

Литература

Jin Akiyama, Geoffrey Exoo, Frank Harary. Covering and packing in graphs. IV. Linear arboricity // Networks. — 1981. — Т. 11, вып. 1. — С. 69–72. — doi:10.1002/net.3230110108.
Asaf Ferber, Jacob Fox, Vishesh Jain. Towards the linear arboricity conjecture. — 2018. — arXiv:1809.04716.
Noga Alon, Teague V. J., Wormald N. C. Linear arboricity and linear k-arboricity of regular graphs // Graphs and Combinatorics. — 2001. — Т. 17, вып. 1. — С. 11–16. — doi:10.1007/PL00007233.
Thomas C. Shermer. On rectangle visibility graphs. III. External visibility and complexity // Proceedings of the 8th Canadian Conference on Computational Geometry (CCCG'96). — 1996. — С. 234–239.
Christian A. Duncan, David Eppstein, Stephen G. Kobourov. The geometric thickness of low degree graphs // Proc. 20th ACM Symposium on Computational Geometry (SoCG 2004). — 2004. — С. 340–346. — doi:10.1145/997817.997868.