Показать меню

Порождённый путь

09.12.2020
39

В теории графов порождённым путём в неориентированном графе G называется путь, являющийся порождённым подграфом G. Таким образом, это последовательность вершин в G такая, что любые две смежные вершины в последовательности соединены ребром в G, и любые две несмежные вершины последовательности не соединены ребром G. Порождённый путь иногда называют змеёй и задача поиска самого длинного порождённого пути в графах гиперкубов известна как задача о змее в коробке.

Также порождённым циклом называется цикл, являющийся порождённым подграфом G. Порождённые циклы называются также циклами без хорд или (если длина цикла не меньше четырёх) дырами. Антидыра — это дыра в дополнении графа G, то есть антидыра — это дополнение дыры.

Длину наибольшего порождённого пути в графе иногда называют числом обхода графа. Для разреженных графов существование ограниченного числа обхода эквивалентно существованию ограниченной глубины дерева. Порождённым числом обхода графа G называется наименьшее число подмножеств вершин, на которые можно разложить вершины графа, чтобы каждое подмножество образовывало порождённый путь, и это понятие тесно связано с числом покрытия путями — минимальное число несвязных путей, являющихся порождёнными подграфами G, покрывающих все вершины G. Обхват графа — это длина его кратчайшего цикла, но этот цикл должен быть порождённым циклом, так как любая хорда могла бы образовать более короткий цикл. По тем же причинам нечётным обхватом графа называется длина его кратчайшего нечётного порождённого цикла.

Пример

На рисунке показан куб, граф с восемью вершинами, двенадцатью рёбрами и порождённым путём длины четыре. Прямой анализ показывает, что не существует более длинного порождённого пути в кубе, хотя существует порождённый цикл длины шесть. Задача поиска наибольшего порождённого пути или цикла в гиперкубе, впервые поставленная Каутцем, известна как задача о змее в коробке и изучалась интенсивно ввиду её использования в теории кодирования и конструировании.

Описание семейств графов

Многие важные семейства графов можно описать в терминах порождённых путей или циклов графов в семействе.

  • Очевидно, что связные графы, не имеющие порождённых путей длины два — это полные графы, а связные графы без порождённых циклов — это деревья.
  • Граф без треугольников — это граф без порождённых циклов длины три.
  • Кографы — это в точности графы без порождённых путей длины три.
  • Хордальные графы — это графы без порождённых циклов длины четыре и более.
  • Графы без дыр чётной длины — это графы, не имеющие циклов, содержащих чётное число вершин.
  • Тривиально совершенные графы — это графы, в которых нет ни порождённых путей длины три, ни порождённых циклов длины четыре.
  • По строгой теореме о совершенных графах совершенные графы — это графы без нечётных дыр и нечётных антидыр.
  • Дистанционно-наследуемые графы — это графы, в которых любой порождённый путь является кратчайшим, и в этих графах любые два порождённых пути между двумя вершинами имеют одинаковую длину.
  • Блоковые графы — это графы, в которых существует максимум один порождённый путь между любыми двумя вершинами, а связные блоковые графы – это графы, в которых существует в точности один порождённый путь между любыми двумя вершинами.

Алгоритмы и сложность

Задача определения, имеет ли граф G порождённый путь длины не меньшей k, является NP-полной. Гарей и Джонсон высказали этот результат в неопубликованном сообщении Михалису Яннакакису. Однако эту задачу можно решить за полиномиальное время для определённых семейств графов, таких как графы без астероидальных троек или графы без длинных дыр.

Также является NP-полной задачей определение, можно ли разложить вершины графа на два порождённых пути или два порождённых цикла. Как следствие, определение числа порождённых путей графа является NP-трудной задачей.

Сложность задач аппроксимации наибольшего порождённого пути или цикла можно связать с задачей поиска наибольших независимых множеств в графах.

Дыры (и антидыры в графах без циклов длины 5 без хорд) в графе с n вершинами и m рёбрами могут быть найдены за время (n+m2).

Атомарные циклы

Атомарные циклы – это обобщение циклов без хорд. Если задан цикл, n-хорда определяется как путь длины n, содержащий две точки цикла, где n меньше длины кратчайшего пути в цикле, соединяющем эти точки. Если цикл не имеет n-хорд, он называется атомарным циклом, поскольку его нельзя разбить на меньшие циклы. В худшем случае атомарные циклы в графе могут быть перечислены за время O(m2), где m – число рёбер в графе.

Еще по этой теме:
Суньер I (граф Пальярса)
14:23, 09 декабрь
Суньер I (граф Пальярса)
Суньер I (кат. Sunyer I) (умер в 1010 или 1011) — граф Пальярса (948/950—1010/1011; до 995/1007 — граф-соправитель), граф-соправитель графства Рибагорса (между 1006 и 1008—1010/1011). Младший сын
Многогранник
13:08, 09 декабрь
Многогранник
Многогранник или полиэдр — обычно замкнутая поверхность, составленная из многоугольников, но иногда так же называют тело, ограниченное этой поверхностью. Определение Многогранник, точнее
Алгоритм Форда — Фалкерсона
23:37, 08 декабрь
Алгоритм Форда — Фалкерсона
Алгоритм Форда — Фалкерсона решает задачу нахождения максимального потока в транспортной сети. Идея алгоритма заключается в следующем. Изначально величине потока присваивается значение 0:
Рёберный граф
00:29, 08 декабрь
Рёберный граф
В теории графов рёберным графом L(G) неориентированного графа G называется граф L(G), представляющий соседство рёбер графа G. Понятие рёберного графа для данного графа настолько естественно, что
Магический граф
00:55, 07 декабрь
Магический граф
Магический граф — это граф, допускающий такую разметку его рёбер положительными целыми числами, что сумма меток всех рёбер, инцидентных любой вершине, постоянна (то есть не зависит от выбора
Коэффициент сетчатости
05:44, 05 декабрь
Коэффициент сетчатости
Коэффициент сетчатости — инвариант планарных графов, измеряющий число ограниченных граней графа по отношению к возможному числу граней других планарных графов с тем же числом вершин. Коэффициент
Комментарии:
Добавить комментарий
Ваше Имя:
Ваш E-Mail:
  • bowtiesmilelaughingblushsmileyrelaxedsmirk
    heart_eyeskissing_heartkissing_closed_eyesflushedrelievedsatisfiedgrin
    winkstuck_out_tongue_winking_eyestuck_out_tongue_closed_eyesgrinningkissingstuck_out_tonguesleeping
    worriedfrowninganguishedopen_mouthgrimacingconfusedhushed
    expressionlessunamusedsweat_smilesweatdisappointed_relievedwearypensive
    disappointedconfoundedfearfulcold_sweatperseverecrysob
    joyastonishedscreamtired_faceangryragetriumph
    sleepyyummasksunglassesdizzy_faceimpsmiling_imp
    neutral_faceno_mouthinnocent