Из Википедии, бесплатной энциклопедии
Перейти к навигации Перейти к поиску
Эта статья о теории графов. Для кустарника см Plumeria alba .
Гусеница

В теории графов , А гусеница или гусеница дерево представляет собой дерево , в котором все вершины находятся в пределах расстояния 1 центрального пути.

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

Эквивалентные характеристики [ править ]

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

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

Обобщения [ править ]

К -tree является хордой графа с точно п - к максимальным кликам , каждым из которых содержит к + 1 вершинам; в k -дереве, которое не является ( k + 1) -кликой , каждая максимальная клика либо разделяет граф на две или более компоненты, либо содержит одну листовую вершину, вершину, которая принадлежит только одной максимальной клике. К -path является к -tree с не более двух листьев, а также к -caterpillar является к -tree , который может быть разделен на K -path и некоторых к-листы, каждый из которых примыкает к разделителю k -клика k-пути . В этой терминологии 1-гусеница - это то же самое, что и дерево-гусеница, а k -гусеницы - это графы с максимальными ребрами с шириной пути k . [6]

Омары граф является деревом , в котором все вершины находятся в пределах расстояния 2 центрального пути . [8]

Перечисление [ править ]

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

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

Приложения [ править ]

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

Ссылки [ править ]

  1. ^ a b c Харари, Фрэнк ; Schwenk, Аллен Дж (1973), "Число гусениц" (PDF) , дискретная математика , 6 (4): 359-365, DOI : 10.1016 / 0012-365x (73) 90067-8.
  2. ^ Б с Эль-Basil, Шериф (1987), "Применение гусеничных дерев в химии и физике", Журнал математической химии , 1 (2): 153-174, DOI : 10.1007 / BF01205666.
  3. ^ a b c d Харари, Фрэнк ; Швенк, Аллен Дж. (1971), «Деревья с гамильтоновым квадратом», Mathematika , 18 : 138–140, DOI : 10.1112 / S0025579300008494 , hdl : 2027.42 / 153141.
  4. ^ Харари, Фрэнк ; Швенк, Аллен Дж. (1972), "Новое число пересечения для двудольных графов", Utilitas Math. , 1 : 203–209.
  5. ^ Raychaudhuri, Arundhati (1995), «Общее число интервалов дерева и гамильтоново число завершения его линейного графа», Письма об обработке информации , 56 (6): 299–306, DOI : 10.1016 / 0020-0190 (95) 00163-8.
  6. ^ a b Проскуровский, Анджей; Телле, Ян Арне (1999), «Классы графов с моделями с ограниченным интервалом» (PDF) , Дискретная математика и теоретическая информатика , 3 : 167–176, заархивировано из оригинала (PDF) 06.06.2011 , извлечено в 2010 г. -05-07 .
  7. ^ Экхофф, Юрген (1993), «Экстремальные интервальные графики», Журнал теории графов , 17 (1): 117–127, DOI : 10.1002 / jgt.3190170112.
  8. ^ Вайсштейн, Эрик В. "График омара" . MathWorld .
  9. ^ a b Хосравани, Масуд (2011). Поиск оптимальных гусениц в общих и ограниченных древовидных графах (Ph.D.). Оклендский университет.
  10. ^ Гутман, Иван (1977), "Топологические свойства бензеноидных систем", Theoretica Chimica Acta , 45 (4): 309-315, DOI : 10.1007 / BF00554539.
  11. ^ Эль-Базиль, Шериф (1990), «Гусеницы (Гутман) деревья в химической теории графов», в Gutman, I .; Cyvin, SJ (ред . ), Достижения в области теории бензеноидных Углеводороды , Темы Current Chemistry, 153 ., С. 273-289, DOI : 10.1007 / 3-540-51505-4_28.

Внешние ссылки [ править ]

  • Вайсштейн, Эрик В. «Гусеница» . MathWorld .