Гусеница (теория графов)

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

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

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

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

• Это деревья, в которых удаление листьев вместе с рёбрами даёт путь.
• Это деревья, в которых существует путь, содержащий все вершины степени два и более.
• Это деревья, в которых любая вершина степени три и более имеет не более двух соседей, не являющихся листьями.
• Это деревья, которые не содержат в качестве подграфов граф, образованный заменой каждого ребра звезды K1,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 вершинами равно.

2 n − 4 + 2 ⌊ ( n − 4 ) / 2 ⌋ . {displaystyle 2^{n-4}+2^{lfloor (n-4)/2 floor }.}

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

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

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

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

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

Приложения

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