Гусеница дерево

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

Гусеницы были впервые изучены в серии работ Харари и Швенка. Название было предложено Артуром Хоббсом . ^{[ 1 ]}^{[ 2 ]} Как красочно пишут Харари и Швенк (1973) : «Гусеница — это дерево, которое превращается в путь, когда удаляется его кокон из конечных точек». ^{[ 1 ]}

Эквивалентные характеристики

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

Это деревья, для которых удаление листьев и инцидентных ребер создает граф путей . ^{[ 2 ]}^{[ 3 ]}
Это деревья, в которых существует путь, содержащий каждую вершину второй или более степени.
Это деревья, в которых каждая вершина степени не ниже третьей имеет не более двух соседей, не являющихся листьями.
Это деревья, которые не содержат в качестве подграфа граф, образованный заменой каждого ребра звездчатого графа K _1,3 на путь длины два. ^{[ 3 ]}
Это связные графы, вершины которых можно нарисовать на двух параллельных линиях, а ребра представляют собой непересекающиеся отрезки линий, имеющие одну конечную точку на каждой линии. ^{[ 3 ]}^{[ 4 ]}
Это деревья, квадрат которых является гамильтоновым графом . То есть у гусеницы существует циклическая последовательность всех вершин, в которой каждая соседняя пара вершин последовательности находится на расстоянии одна или две друг от друга, а деревья, не являющиеся гусеницами, такой последовательности не имеют. Цикл этого типа можно получить, нарисовав гусеницу на двух параллельных линиях и соединив последовательность вершин на одной линии с обратной последовательностью на другой линии. ^{[ 3 ]}
Это деревья, линейные графы которых содержат гамильтонов путь ; такой путь можно получить, упорядочив ребра на двухлинейном рисунке дерева. В более общем смысле, количество ребер, которые необходимо добавить в линейный граф произвольного дерева, чтобы оно содержало гамильтонов путь (размер его гамильтонова завершения ), равно минимальному количеству гусениц, не пересекающихся по ребрам, которые ребра дерева могут разложиться на. ^{[ 5 ]}
Это связные графы с шириной пути один. ^{[ 6 ]}
Это связные без треугольников интервальные графы . ^{[ 7 ]}
Это n-вершинные графы, матрицы смежности которых можно записать так, что матрицы верхней треугольной части образуют путь длины n-1, начинающийся в правом верхнем углу и идущий вниз или влево. ^{[ 8 ]}

Обобщения

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

Граф омара — это дерево , все вершины которого находятся на расстоянии 2 от центрального пути . ^{[ 9 ]}

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

Гусеницы представляют собой одну из редких задач перечисления графов , для которой можно дать точную формулу: когда n ≥ 3, количество гусениц с n непомеченными вершинами равно ^{[ 1 ]}

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-полным . Связанная с этим задача оптимизации - это задача гусеницы с минимальным охватом (MSCP), где граф имеет двойную стоимость по своим краям, и цель состоит в том, чтобы найти дерево-гусеницу, которая охватывает входной граф и имеет наименьшую общую стоимость. Здесь стоимость гусеницы определяется как сумма стоимостей ее ребер, где каждое ребро берет на себя одну из двух стоимостей в зависимости от его роли как листового ребра или внутреннего. не существует алгоритма f(n)-аппроксимации Для MSCP , если только P = NP . Здесь f(n) — любая вычислимая за полиномиальное время функция от n — количества вершин графа. ^{[ 10 ]}

Существует параметризованный алгоритм, который находит оптимальное решение для MSCP в графах с ограниченной шириной дерева . Таким образом, и задача Spanning Caterpillar, и MSCP имеют алгоритмы с линейным временем, если граф является внешнепланарным, последовательно-параллельным или графом Халина . ^{[ 10 ]}

Приложения

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

Ссылки

^ Jump up to: ^а ^б ^с Харари, Фрэнк ; Швенк, Аллен Дж. (1973), «Число гусениц» (PDF) , Discrete Mathematics , 6 (4): 359–365, doi : 10.1016/0012-365x(73)90067-8 , hdl : 2027.42/33977 .
^ Jump up to: ^а ^б ^с Эль-Базиль, Шериф (1987), «Применение деревьев-гусениц в химии и физике», Журнал математической химии , 1 (2): 153–174, doi : 10.1007/BF01205666 , S2CID 121322252 .
^ Jump up to: ^а ^б ^с ^д Харари, Фрэнк ; Швенк, Аллен Дж. (1971), «Деревья с квадратом Гамильтона», Mathematika , 18 : 138–140, doi : 10.1112/S0025579300008494 , hdl : 2027.42/153141 .
^ Харари, Фрэнк ; Швенк, Аллен Дж. (1972), «Новое число пересечений для двудольных графов», Utilitas Math. , 1 : 203–209 .
^ Райчаудхури, Арундати (1995), «Общее число интервалов дерева и гамильтонианное число завершения его линейного графа», Information Processing Letters , 56 (6): 299–306, doi : 10.1016/0020-0190(95)00163 -8 .
^ Jump up to: ^а ^б Проскуровский, Анджей; Телле, Ян Арне (1999), «Классы графов с моделями с ограниченными интервалами» (PDF) , Дискретная математика и теоретическая информатика , 3 : 167–176 .
^ Экхофф, Юрген (1993), «Экстремальные интервальные графики», Journal of Graph Theory , 17 (1): 117–127, doi : 10.1002/jgt.3190170112 .
^ Э. Гусейнов, Шаблоны матриц смежности и еще одно доказательство того, что гусеницы изящны [1]
^ Вайсштейн, Эрик В. «График омаров» . Математический мир .
^ Jump up to: ^а ^б Хосравани, Масуд (2011). Поиск оптимальных гусениц в общих и ограниченных древовидных графах (к.т.н.). Университет Окленда.
^ Гутман, Иван (1977), «Топологические свойства бензоидных систем», Theoretica Chimica Acta , 45 (4): 309–315, doi : 10.1007/BF00554539 .
^ Эль-Базиль, Шериф (1990), «Деревья-гусеницы (Гутмана) в химической теории графов», Гутман, И.; Сайвин, С.Дж. (ред.), Достижения в теории бензоидных углеводородов , Темы современной химии, том. 153, стр. 273–289, номер документа : 10.1007/3-540-51505-4_28 , S2CID 91687862 .

Внешние ссылки

Вайсштейн, Эрик В. «Гусеница» . Математический мир .

[hs73-1] Jump up to: ^а ^б ^с Харари, Фрэнк ; Швенк, Аллен Дж. (1973), «Число гусениц» (PDF) , Discrete Mathematics , 6 (4): 359–365, doi : 10.1016/0012-365x(73)90067-8 , hdl : 2027.42/33977 .

[eb87-2] Jump up to: ^а ^б ^с Эль-Базиль, Шериф (1987), «Применение деревьев-гусениц в химии и физике», Журнал математической химии , 1 (2): 153–174, doi : 10.1007/BF01205666 , S2CID 121322252 .

[hs71-3] Jump up to: ^а ^б ^с ^д Харари, Фрэнк ; Швенк, Аллен Дж. (1971), «Деревья с квадратом Гамильтона», Mathematika , 18 : 138–140, doi : 10.1112/S0025579300008494 , hdl : 2027.42/153141 .

[4] Харари, Фрэнк ; Швенк, Аллен Дж. (1972), «Новое число пересечений для двудольных графов», Utilitas Math. , 1 : 203–209 .

[5] Райчаудхури, Арундати (1995), «Общее число интервалов дерева и гамильтонианное число завершения его линейного графа», Information Processing Letters , 56 (6): 299–306, doi : 10.1016/0020-0190(95)00163 -8 .

[pt99-6] Jump up to: ^а ^б Проскуровский, Анджей; Телле, Ян Арне (1999), «Классы графов с моделями с ограниченными интервалами» (PDF) , Дискретная математика и теоретическая информатика , 3 : 167–176 .

[7] Экхофф, Юрген (1993), «Экстремальные интервальные графики», Journal of Graph Theory , 17 (1): 117–127, doi : 10.1002/jgt.3190170112 .

[8] Э. Гусейнов, Шаблоны матриц смежности и еще одно доказательство того, что гусеницы изящны [1]

[9] Вайсштейн, Эрик В. «График омаров» . Математический мир .

[mk11-10] Jump up to: ^а ^б Хосравани, Масуд (2011). Поиск оптимальных гусениц в общих и ограниченных древовидных графах (к.т.н.). Университет Окленда.

[11] Гутман, Иван (1977), «Топологические свойства бензоидных систем», Theoretica Chimica Acta , 45 (4): 309–315, doi : 10.1007/BF00554539 .

[12] Эль-Базиль, Шериф (1990), «Деревья-гусеницы (Гутмана) в химической теории графов», Гутман, И.; Сайвин, С.Дж. (ред.), Достижения в теории бензоидных углеводородов , Темы современной химии, том. 153, стр. 273–289, номер документа : 10.1007/3-540-51505-4_28 , S2CID 91687862 .

[ 1 ]

[ 2 ]

[ 3 ]

[ 4 ]

[ 5 ]

[ 6 ]

[ 7 ]

[ 8 ]

[ 9 ]

[ 10 ]

[ 11 ]

[ 12 ]