Гусеница дерево - Caterpillar tree
В теории графов , А гусеница или гусеница дерево представляет собой дерево , в котором все вершины находятся в пределах расстояния 1 центрального пути.
Впервые гусеницы были изучены в серии работ Харари и Швенка. Название было предложено А. Хоббсом . Как красочно пишут Харари и Швенк (1973) : «Гусеница - это дерево, которое превращается в путь, когда его конечный кокон удаляется».
Эквивалентные характеристики
Все следующие характеристики описывают гусеницы:
- Это деревья, для которых удаление листьев и инцидентных ребер дает граф путей .
- Это деревья, в которых существует путь, содержащий каждую вершину степени два или более.
- Это деревья, в которых каждая вершина степени не менее трех имеет не более двух соседей, не являющихся листами.
- Это деревья, которые не содержат в качестве подграфа граф, образованный заменой каждого ребра в звездном графе K 1,3 на путь длины два.
- Это связанные графы, которые можно нарисовать вершинами на двух параллельных линиях с ребрами, представленными в виде непересекающихся отрезков, имеющих по одной конечной точке на каждой линии.
- Это деревья, квадрат которых является гамильтоновым графом . То есть в гусенице существует циклическая последовательность всех вершин, в которой каждая смежная пара вершин в последовательности находится на расстоянии одного или двух друг от друга, а деревья, не являющиеся гусеницами, не имеют такой последовательности. Цикл этого типа можно получить, нарисовав гусеницу на двух параллельных линиях и сцепив последовательность вершин на одной линии с обратной последовательностью на другой линии.
- Это деревья, линейные графики которых содержат гамильтонов путь ; такой путь может быть получен путем упорядочения ребер на двухстрочном чертеже дерева. В более общем смысле количество ребер, которые необходимо добавить к линейному графу произвольного дерева, чтобы он содержал гамильтонов путь (размер его гамильтонова завершения ), равно минимальному количеству непересекающихся по ребрам гусениц, которые могут быть на ребрах дерева. разложить на.
- Это связанные графы ширины пути .
- Это связные интервальные графы без треугольников .
- Это n-вершинные графы, матрицы смежности которых могут быть записаны таким образом, что матрицы верхней треугольной части образуют путь длиной n-1, начинающийся в верхнем правом углу и идущий вниз или влево.
Обобщения
К -tree является хордой графа с точно п - к максимальным кликам , каждым из которых содержит к + 1 вершинам; в k -дереве, которое не является ( k + 1) -кликой , каждая максимальная клика либо разделяет граф на две или более компоненты, либо содержит одну листовую вершину, вершину, которая принадлежит только одной максимальной клике. К -path является к -tree с не более двух листьев, а также к -caterpillar является к -tree , которая может быть разделена на K -path и некоторых K -leaves, каждый из которых примыкает к Сепаратор K -clique из k -путь. В этой терминологии 1-гусеница - это то же самое, что и дерево-гусеница, а k -гусеницы - это графы с максимальными ребрами с шириной пути k .
Омары граф является деревом , в котором все вершины находятся в пределах расстояния 2 центрального пути .
Перечисление
Гусеницы представляют собой одну из редких задач перечисления графов, для которой можно дать точную формулу: при n ≥ 3 количество гусениц с n непомеченными вершинами равно
Для n = 1, 2, 3, ... количество n- вершинных гусениц равно
- 1, 1, 1, 2, 3, 6, 10, 20, 36, 72, 136, 272, 528, 1056, 2080, 4160, ... (последовательность A005418 в OEIS ).
Вычислительная сложность
Нахождение остовной гусеницы в графе является NP-полным . Связанная с этим проблема оптимизации - это задача минимальной остовной гусеницы (MSCP), когда граф имеет двойную стоимость по краям, и цель состоит в том, чтобы найти дерево гусеницы, которое охватывает входной граф и имеет наименьшую общую стоимость. Здесь стоимость гусеницы определяется как сумма затрат на ее ребра, где каждое ребро принимает одну из двух затрат в зависимости от его роли как кромки листа или внутренней. Не существует f (n) - приближенного алгоритма для MSCP, если P = NP . Здесь f (n) - любая вычислимая за полиномиальное время функция от n, числа вершин графа.
Существует параметризованный алгоритм, который находит оптимальное решение для MSCP в графах с ограниченной древовидной шириной . Таким образом, и проблема Spanning Caterpillar, и MSCP имеют алгоритмы линейного времени, если граф является внешнепланарным, последовательно-параллельным или графом Халина .
Приложения
Деревья-гусеницы использовались в химической теории графов для представления структуры молекул бензоидных углеводородов . В этом представлении одна образует гусеницу, в которой каждое ребро соответствует 6-углеродному кольцу в молекулярной структуре, а два ребра падают в вершину всякий раз, когда соответствующие кольца принадлежат последовательности колец, соединенных встык. структура. Эль-Базиль (1987) пишет: «Удивительно, что почти все графы, сыгравшие важную роль в том, что сейчас называется« химической теорией графов », могут быть связаны с деревьями-гусеницами». В этом контексте гусеничные деревья также известны как бензеноидные деревья и деревья Гутмана после работы Ивана Гутмана в этой области.