Гусеница или гусеничное дерево — это дерево , в котором все вершины находятся на расстоянии не более 1 от центрального пути.

Графы-гусеницы первыми начали изучать в серии статей Харари и Швенк. Название предложил Артур Хоббс . Как красочно писали Харари и Швенк , «Гусеница — это дерево, которое превращается в путь, если удалить кокон из конечных вершин» .

Эквивалентные описания

Следующие характеристики описывают графы-гусеницы:

• Это деревья, в которых удаление листьев вместе с рёбрами даёт путь .
• Это деревья, в которых существует путь, содержащий все вершины степени два и более.
• Это деревья, в которых любая вершина степени три и более имеет не более двух соседей, не являющихся листьями.
• Это деревья, которые не содержат в качестве подграфов граф, образованный заменой каждого ребра звезды K _1,3 путём из двух рёбер .
• Это связные графы, которые можно нарисовать , расположив вершины на двух параллельных прямых с непересекающимися рёбрами, а конечные вершины каждого ребра расположив на разных прямых .
• Это деревья, квадрат которых является гамильтоновым графом . Под квадратом здесь понимается существование циклической последовательности всех вершин, при которой каждая пара соседних вершин в последовательности находятся на расстоянии один или два. Деревья, не являющиеся гусеницами, такой последовательностью не обладают. Цикл такого вида можно получить, если нарисовать гусеницу с вершинами на двух параллельных прямых. Затем нумеруем вершины на одной прямой в одном направлении, а на другой прямой — в обратном направлении .
• Это деревья, рёберные графы которых содержат гамильтонов путь . Такой путь может быть получен путём упорядочения рёбер в рисунке гусеницы с двумя прямыми. Более обще, число рёбер, которые нужно добавить к рёберному графу для произвольного дерева, чтобы он содержал гамильтонов путь (размер его гамильтонова дополнения ), равно минимальному числу не пересекающихся по рёбрам гусениц, на которые дерево может быть разбито .
• Это связные графы с единичной путевой шириной .
• Это связные интервальные графы без треугольников .

Обобщения

K -дерево — это хордальный граф , содержащий в точности n − k максимальных клик , каждая из которых содержит k + 1 вершин. В k -дереве, которое само по себе не является ( k + 1)-кликой , каждая максимальная клика либо разделяет граф на две или более компоненты, либо содержит ( k -)листовую вершину, которая принадлежит только одной максимальной клике. k -путь — это k -дерево с максимум двумя листами, а k -гусеница — это k -дерево, которое можно разбить на k -пути и несколько k -листьев, каждый из которых смежен сепаратору k -клики k -пути. В этой терминологии, 1-гусеница — это то же самое, что и граф-гусеница, а k -гусеницы являются рёберно-максимальными графами с путевой шириной k .

Краб — это дерево , в котором все вершины находятся на расстоянии, не превосходящем 2 от центрального пути

Перечисление

Гусеницы являются редким случаем задач перечисления графов , когда известна точная формула — если n ≥ 3, число гусениц с n вершинами равно .

${\displaystyle 2^{n-4}+2^{\lfloor (n-4)/2\rfloor }.}$

Для n = 1, 2, 3, …число гусениц с n вершинами равно

1, 1, 1, 2, 3, 6, 10, 20, 36, 72, 136, 272, 528, 1056, 2080, 4160, … (последовательность в OEIS ).

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

Поиск стягивающей гусеницы является NP-полной задачей . Соответствующая оптимизационная задача — задача о минимальной стягивающей гусенице (ЗМСГ), в которой заданы цены на рёбрах и целью является поиск гусеницы, минимизирующей цены. Здесь цена гусеницы определяется как сумма цен её рёбер, а каждое ребро имеет две цены, в зависимости от того, является ли оно листом или внутренним ребром. Не существует f(n)- аппроксимационного алгоритма для ЗМСГ, если не выполняется P = NP . Здесь f(n) — любая функция от n, вычисляемая за полиномиальное время, а n — число вершин графа .

Существует параметризованный алгоритм, который находит оптимальное решение ЗМСГ в графе с ограниченной древесной шириной . Таким образом, как задача о стягивающей гусенице, так и задача о минимальной стягивающей гусенице имеют алгоритмы линейного времени, если граф внешнепланарен , является параллельно-последовательным графом , или графом Халина .

Приложения

Гусеницы используются в химической теории графов для представления структуры молекул бензоидных углеводородов . В этом представлении молекулы образуют гусеницы, в которых каждое ребро соответствует кольцу из 6 атомов углерода, а два ребра инцидентны вершине, если соответствующие бензольные кольца принадлежат последовательности соединённых линейно колец. Ель-Базиль пишет: «Удивительно, что почти все графы, которые играют важную роль в том, что сейчас называется «химической теорией графов», связаны с графами-гусеницами». В этом контексте графы-гусеницы известны также как бензоидные деревья или деревья Гутмана , по работам Ивана Гутмана в этой области .

Примечания

Литература

Ссылки

• Weisstein, Eric W. (англ.) на сайте Wolfram MathWorld .