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

Перейти к навигацииПерейти к поиску
Гусеница

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

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

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

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

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

Обобщения

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

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

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

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

Для 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 — число вершин графа[10].

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

Приложения

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

Примечания

  1. ↑ 1 2 3 Harary, Schwenk, 1973, с. 359–365.
  2. ↑ 1 2 3 El-Basil, 1987, с. 153–174.
  3. ↑ Harary, Schwenk, 1973.
  4. ↑ 1 2 3 4 5 Harary, Schwenk, 1971, с. 138–140.
  5. ↑ Harary, Schwenk, 1972, с. 203–209.
  6. ↑ Raychaudhuri, 1995, с. 299–306.
  7. ↑ 1 2 Proskurowski, Telle, 1999, с. 167–176.
  8. ↑ Eckhoff, 1993, с. 117–127.
  9. ↑ Weisstein, Eric W. Lobster (англ.) на сайте Wolfram MathWorld.
  10. ↑ 1 2 Khosravani, 2011.
  11. ↑ Gutman, 1977, с. 309–315.
  12. ↑ El-Basil, 1990, с. 273–289.

Литература

  • Masoud Khosravani. Searching for optimal caterpillars in general and bounded treewidth graphs // Ph.D.. — University of Auckland, 2011.
  • Sherif El-Basil. Applications of caterpillar trees in chemistry and physics // Journal of Mathematical Chemistry. — 1987. — Т. 1, вып. 2. — С. 153–174. — doi:10.1007/BF01205666.
  • Ivan Gutman. Topological properties of benzenoid systems // Theoretica Chimica Acta. — 1977. — Т. 45, вып. 4. — С. 309–315. — doi:10.1007/BF00554539.
  • Sherif El-Basil. Advances in the Theory of Benzenoid Hydrocarbons / I. Gutman, S. J. Cyvin. — 1990. — Т. 153. — С. 273–289. — (Topics in Current Chemistry). — doi:10.1007/3-540-51505-4_28.
  • Andrzej Proskurowski, Jan Arne Telle. Classes of graphs with restricted interval models // Discrete Mathematics and Theoretical Computer Science. — 1999. — Т. 3. — С. 167–176.
  • Arundhati Raychaudhuri. The total interval number of a tree and the Hamiltonian completion number of its line graph // Information Processing Letters. — 1995. — Т. 56, вып. 6. — С. 299–306. — doi:10.1016/0020-0190(95)00163-8.
  • Jürgen Eckhoff. Extremal interval graphs // Journal of Graph Theory. — 1993. — Т. 17, вып. 1. — С. 117–127. — doi:10.1002/jgt.3190170112.
  • Frank Harary, Allen J. Schwenk. Trees with Hamiltonian square // Mathematika. — 1971. — Т. 18. — С. 138–140. — doi:10.1112/S0025579300008494.
  • Frank Harary, Allen J. Schwenk. A new crossing number for bipartite graphs // Utilitas Math.. — 1972. — Т. 1. — С. 203–209.
  • Frank Harary, Allen J. Schwenk. The number of caterpillars // Discrete Mathematics. — 1973. — Т. 6, вып. 4. — С. 359–365. — doi:10.1016/0012-365x(73)90067-8.

Ссылки