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

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

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

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

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

Це дерева, в яких видалення листків разом з ребрами дає шлях Шаблон:Sfn Шаблон:Sfn.
Це дерева, в яких існує шлях, що містить всі вершини степеня два і більше.
Це дерева, в яких будь-яка вершина степеня три і більше має не більше двох сусідів, які не є листками.
Це дерева, які не містять в якості підграфів граф, утворений заміною кожного ребра зірки K_1,3 шляхом з двох реберШаблон:Sfn.
Це зв'язні графи, які можна намалювати, розташувавши вершини на двох паралельних прямих з ребрами, що не перетинаються, а кінцеві вершини кожного ребра розташувавши на різних прямихШаблон:Sfn Шаблон:Sfn Шаблон:Sfn.
Це дерева, квадрат яких є гамільтоновим графом. Під квадратом тут мається на увазі існування циклічної послідовності всіх вершин, при якій кожна пара сусідніх вершин у послідовності знаходяться на відстані один або два. Дерева, що не є гусеницями, такої послідовності не мають. Цикл такого вигляду можна отримати, якщо намалювати гусеницю з вершинами на двох паралельних прямих. Потім нумеруємо вершини на одній прямій в одному напрямку, а на іншій прямій — у зворотному напрямкуШаблон:Sfn.
Це дерева, реберні графи яких містять гамільтонів шлях. Такий шлях може бути отриманий шляхом впорядкування ребер на малюнку гусениці з двома прямими. Більш загально, число ребер, які потрібно додати до реберного графу для довільного дерева, щоб він містив гамільтонів шлях (розмір його гамільтонового доповнення), дорівнює мінімальному числу гусениць, що не перетинаються по ребрах, на які дерево може бути розбитеШаблон:Sfn.
Це зв'язні графи з одиничною шляховою шириною Шаблон:Sfn.
Це зв'язні інтервальні графи без трикутників Шаблон:Sfn.

Узагальнення

K-дерево — це хордальний граф, що містить рівно Шаблон:Nobr максимальних клік, кожна з яких містить Шаблон:Nobr вершину. В k-дереві, яке саме по собі не є Шаблон:Nobr, кожна максимальна кліка або поділяє граф на дві або більше компонент, або містить (k-)листкову вершину, яка належить тільки одній максимальній кліці. k-шлях — це k-дерево з максимум двома листками, а k-гусениця — це k-дерево, яке можна розбити на k-шляхи і кілька k-листків, кожен з яких суміжний з сепаратором k-кліки k-шляху. В цій термінології, 1-гусениця — це те ж саме, що й граф-гусениця, а k-гусениці є реберно-максимальними графами зі шляховою шириною kШаблон:Sfn.

Краб — це дерево, в якому всі вершини знаходяться на відстані, що не перевершує 2 від центрального шляху^[1]

Перерахування

Гусениці є рідкісним випадком задач перерахування графів, коли відома точна формула — якщо n ≥ 3, число гусениць з n вершинами дорівнюєШаблон:Sfn

2^{n - 4} + 2^{⌊ (n - 4) / 2 ⌋} .

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

1, 1, 1, 2, 3, 6, 10, 20, 36, 72, 136, 272, 528, 1056, 2080, 4160, … (Шаблон:OEIS).

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

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

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

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

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