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

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

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

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

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

Нерешенная проблема в математике: Каждый ли график максимальной степени ${\displaystyle \Delta }$ иметь линейное древовидность не более ${\displaystyle \lceil (\Delta +1)/2\rceil }$? (больше нерешенных задач по математике)

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

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

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

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

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

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

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

Рекомендации

1. Акияма, Джин; Экзу, Джеффри; Харари, Фрэнк (1981), "Покрытие и упаковка в графах. IV. Линейная древовидность", Сети, 11 (1): 69–72, Дои:10.1002 / нетто.3230110108, МИСТЕР  0608921.
2. Фербер, Асаф; Фокс, Джейкоб; Джайн, Вишеш (2018), К гипотезе линейной древовидности, arXiv:1809.04716.
3. Алон, Нога; Тиг, В. Дж.; Вормолд, Н.С. (2001), «Линейная древовидность и линейная k-арборичность регулярных графов », Графы и комбинаторика, 17 (1): 11–16, Дои:10.1007 / PL00007233, МИСТЕР  1828624.
4. Перош Б. (1984), "NP-полнота некоторых проблем разбиения и покрытия в графах", Дискретная прикладная математика, 8 (2): 195–208, Дои:10.1016 / 0166-218X (84) 90101-X, МИСТЕР  0743024; смотрите также Перош, Б. (1982), "Complexité de l'arboricité linéaire d'un graphe", RAIRO Recherche Opérationnelle, 16 (2): 125–129, Дои:10.1051 / ro / 1982160201251, МИСТЕР  0679633 и Перош, Б. (1985), "Complexité de l'arboricité linéaire d'un graphe. II", RAIRO Recherche Opérationnelle, 19 (3): 293–300, Дои:10.1051 / ro / 1985190302931, МИСТЕР  0815871. Сокращение Перош (1982) из мультиграфы к простым графам повторяется в Шермер, Томас К. (1996), «На прямоугольных графиках видимости. III. Внешняя видимость и сложность» (PDF), Труды 8-й Канадской конференции по вычислительной геометрии (CCCG'96), стр. 234–239.
5. Дункан, Кристиан А .; Эппштейн, Дэвид; Кобуров, Стивен Г. (2004), "Геометрическая толщина графов низкой степени", Proc. 20-й симпозиум ACM по вычислительной геометрии (SoCG 2004), стр. 340–346, arXiv:cs.CG/0312056, Дои:10.1145/997817.997868.