Граф-гусениця

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

Гусениця

Графи-гусениці першими почали вивчати в серії статей Харарі та . Назву запропонував ^[en]. Як барвисто писали Харарі та Швенк, «Гусениця — це дерево, яке перетворюється в шлях, якщо видалити кокон з кінцевих вершин».

Еквівалентні описи

Такі характеристики описують графи-гусениці:

• Це дерева, в яких видалення листків разом з ребрами дає шлях.
• Це дерева, в яких існує шлях, що містить всі вершини степеня два і більше.
• Це дерева, в яких будь-яка вершина степеня три і більше має не більше двох сусідів, які не є листками.
• Це дерева, які не містять в якості підграфів граф, утворений заміною кожного ребра зірки 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, … (послідовність A005418 з Онлайн енциклопедії послідовностей цілих чисел, OEIS).

Обчислювальна складність

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

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

Застосування

Гусениці використовуються в хімічній теорії графів для подання структури молекул бензоїдних вуглеводнів. У цьому поданні молекули утворюють гусениці, в яких кожне ребро відповідає кільцю з 6 атомів вуглецю, а два ребра інцидентні вершині, якщо відповідні бензольні кільця належать послідовності сполучених лінійно кілець. (англ. Sherif El-Basil) пише: «Дивно, що майже всі графи, які відіграють важливу роль у тому, що зараз називається „хімічною теорією графів“, пов'язані з графами-гусеницями». У цьому контексті графи-гусениці відомі також як бензоїдні дерева або дерева Гутмана, за роботами Івана Гутмана в цій галузі.

Див. також

• Граціозна розмітка

Примітки

1. Harary, Schwenk, 1973, с. 359–365.
2. El-Basil, 1987, с. 153–174.
3. Harary, Schwenk, 1973.
4. Harary, Schwenk, 1971, с. 138–140.
5. Harary, Schwenk, 1972, с. 203–209.
6. Raychaudhuri, 1995, с. 299–306.
7. Proskurowski, Telle, 1999, с. 167–176.
8. Eckhoff, 1993, с. 117–127.
9. Weisstein, Eric W. Lobster(англ.) на сайті Wolfram MathWorld.
10. 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.. — 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. — 1990. — Т. 153. — С. 273–289. — 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.

Посилання

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