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

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

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

Обобщения K-дерево — это хордальный граф, содержащий в точности максимальных клик, каждая из которых содержит вершин. В k-дереве, которое само по себе не является , каждая максимальная клика либо разделяет граф на две или более компоненты, либо содержит (k-)листовую вершину, которая принадлежит только одной максимальной клике. k-путь — это k-дерево с максимум двумя листами, а k-гусеница — это k-дерево, которое можно разбить на k-пути и несколько k-листьев, каждый из которых смежен сепаратору k-клики 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, … ().

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

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

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

Примечания

Литература

Ссылки

Категория:Деревья (графы) Категория:Математическая химия