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

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

Гусениця

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

Еквівалентні описиРедагувати

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

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

УзагальненняРедагувати

K-дерево — це хордальний граф[ru], що містить рівно nk максимальних клік, кожна з яких містить k + 1 вершину. В k-дереві, яке саме по собі не є (k + 1)-клікою, кожна максимальна кліка або поділяє граф на дві або більше компонент, або містить (k-)листкову вершину, яка належить тільки одній максимальній кліці. k-шлях — це k-дерево з максимум двома листками, а k-гусениця — це k-дерево, яке можна розбити на k-шляхи і кілька k-листків, кожен з яких суміжний з сепаратором[ru] 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)-апроксимаційного алгоритму[ru] для ЗМСГ, якщо не виконується P = NP. Тут f(n) — будь-яка функція від n, що обчислюється за поліноміальний час, а n — число вершин графа[10].

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

ЗастосуванняРедагувати

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

ПриміткиРедагувати

  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.

ПосиланняРедагувати