Разложение уха

Пример разложения по уху графа, содержащего 3 уха.

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

Разложения на ухо могут использоваться для характеристики нескольких важных классов графов и как часть эффективных алгоритмов графов . Их также можно обобщить с графов на матроиды .

Описание классов графов [ править ]

Несколько важных классов графов можно охарактеризовать как графы, имеющие определенные типы разложений ушей.

Связность графиков [ править ]

Граф называется k -вершинно-связным, если удаление любых ( k  - 1) вершин оставляет связный подграф, и k- реберно-связным, если удаление любых ( k  - 1) ребер оставляет связный подграф.

Следующий результат принадлежит Хасслеру Уитни  ( 1932 ):

Граф с 2-вершинно-связным тогда и только тогда, когда он имеет разложение открытого уха.${\ Displaystyle G = (V, E)}$${\ displaystyle | E | \ geq 2}$

Следующий результат принадлежит Герберту Роббинсу  ( 1939 ):

Граф является 2-реберно связным тогда и только тогда, когда он имеет разложение на ухо.

В обоих случаях количество ушей обязательно равно рангу схемы данного графа. Роббинс ввел разложение двух ребер связных графов как инструмент для доказательства теоремы Роббинса о том , что это именно те графы, которым можно придать сильно связную ориентацию. Из-за новаторской работы Уитни и Роббинса по разложению ушей, разложение уха иногда также называют синтезом Уитни-Роббинса ( Gross & Yellen 2006 ).

Разложение уха без разделения является открытым разложением уха такое , что для каждой вершины V только с одним исключением, v есть сосед , чье первое появление в разложении в более позднем ухе , чем первое появление V . Этот тип разложения уха можно использовать для обобщения результата Уитни:

Граф с 3-вершинно-связным тогда и только тогда, когда G имеет неразделяющее разложение уха.${\ Displaystyle G = (V, E)}$${\ displaystyle | V | \ geq 2}$

Если такое разложение существует, то она может быть выбрана по отношению к конкретному краевому уф из G таким образом , что у находится в первом ухе, v является новой вершиной в последнем ухе с более чем одним ребром, и увами являются однолезвийное ухо. Этот результат был впервые явно сформулирован Cheriyan & Maheshwari (1988) , но, как описывает Шмидт (2013b) , он эквивалентен результату, полученному в 1971 г. диссертация Ли Мондшейна. Структуры, тесно связанные с неразрывными разложениями максимальных плоских графов, называемые каноническими упорядочениями, также являются стандартным инструментом при рисовании графов .

Сильная связность ориентированных графов [ править ]

Приведенные выше определения также могут применяться к ориентированным графам . Тогда ухо будет направленным путем, в котором все внутренние вершины имеют степень и исходящую степень, равную 1. Ориентированный граф является сильно связным, если он содержит направленный путь из каждой вершины в каждую другую вершину. Тогда справедлива следующая теорема ( Банг-Йенсен и Гутин, 2007 , теорема 7.2.2):

Ориентированный граф сильно связен тогда и только тогда, когда он имеет разложение на ухо.

Факторно-критические графики [ править ]

Разложение уха является нечетным, если в каждом из его ушей используется нечетное количество краев. Фактор-граф критического представляет собой график с нечетным числом вершин, таким образом, что для каждой вершины V , если v удаляются из графа , то остальные вершины имеют полное совпадение . Ласло Ловас  ( 1972 ) обнаружил, что:

Граф G фактор-критичен тогда и только тогда, когда G имеет разложение на нечетное ухо.

В более общем плане результат Фрэнка (1993) позволяет найти в любом графе G разложение уха с наименьшим числом четных ушей.

Последовательно-параллельные графы [ править ]

Дерева разложения уха является собственным разложением уха , в котором первое ухо одно ребро , и для каждого последующего уха , есть одно ухо , таким образом, что оба конца лежат на ( Khuller +1989 ). Вложенное разложение уха разложения уха дерева таким образом , что в пределах каждого уха , множество пар оконечных других ушей , которые лежат в виде набора вложенных интервалов. Последовательно -параллельный граф - это граф с двумя обозначенными терминалами s и t${\ displaystyle P_ {i}}$${\ displaystyle P_ {j}}$${\ displaystyle i> j}$${\ displaystyle P_ {i}}$${\ displaystyle P_ {j}}$${\ displaystyle P_ {j}}$${\ displaystyle P_ {i}}$${\ displaystyle P_ {j}}$ который может быть сформирован рекурсивно путем объединения меньших последовательно-параллельных графов одним из двух способов: последовательная композиция (идентификация одного терминала из одного меньшего графа с одним терминалом из другого меньшего графа и сохранение двух других терминалов в качестве терминалов объединенного графа ) и параллельная композиция (идентификация обеих пар терминалов из двух меньших графиков).

Следующий результат принадлежит Дэвиду Эппштейну  ( 1992 ):

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

Более того, любое открытое разложение последовательно-параллельного графа с двумя вершинами должно быть вложенным. Результат может быть расширен до последовательно-параллельных графов, которые не связаны по двум вершинам, с использованием разложений с открытым ухом, которые начинаются с пути между двумя терминалами.

Матроиды [ править ]

Понятие разложения уха можно распространить с графов на матроиды . Разложение на ухо матроида определяется как последовательность схем матроида с двумя свойствами:

• каждая схема в последовательности имеет непустое пересечение с предыдущими схемами, и
• каждая схема в последовательности остается схемой, даже если все предыдущие схемы в последовательности свернуты.

При нанесении на графическую матроиду графа G , это определение декомпозиции ухи совпадает с определением правильного разложения уха G : несобственные разложения исключены требованием , чтобы каждый контур включает по меньшей мере один край , который также принадлежит к предыдущим цепям . Используя это определение, матроид может быть определен как фактор критичный, когда он имеет разложение на ухо, в котором каждая цепь в последовательности имеет нечетное количество новых элементов ( Szegedy & Szegedy 2006 ).

Алгоритмы [ править ]

На классических компьютерах разложения ушей двухсвязных графов и разложения открытых ушей 2-вершинно-связных графов могут быть найдены жадными алгоритмами, которые находят каждое ухо по одному. Простой жадный подход, который одновременно вычисляет разложение уха, разложение открытого уха, st-нумерацию и -ориентацию за линейное время (если они существуют), приведен в Schmidt (2013a) . Подход основан на вычислении специального разложения уха, называемого цепным разложением, по одному правилу генерации пути. Шмидт (2013b) показывает, что неразрывные разложения уха также могут быть построены за линейное время.

Ловас (1985) , Маон, Шибер и Вишкин (1986) и Миллер и Рамачандран (1986) предоставили эффективные параллельные алгоритмы для построения разложений уха различных типов. Например, чтобы найти разложение двух ребер связного графа, алгоритм Маона, Шибера и Вишкина (1986) выполняется в соответствии со следующими шагами:

1. Найдите остовное дерево данного графа и выберите корень дерева.
2. Определить для каждого ребра уф , который не является частью дерева, расстояние между корнем и наименьшего общего предка из U и V .
3. Для каждого ребра uv, которое является частью дерева, найдите соответствующее "главное ребро", не являющееся деревом ребро wx, такое, что цикл, образованный добавлением wx к дереву, проходит через uv, и такое, что среди таких ребер w и x имеют наименьшего общего предка, который находится как можно ближе к корню (со связями, нарушенными идентификаторами ребер).
4. Сформируйте ухо для каждого ребра, не являющегося деревом, состоящего из него и ребер дерева, для которого он является главным, и упорядочите уши по расстоянию их главных ребер от корня (с тем же правилом разрыва связей).

Эти алгоритмы могут использоваться в качестве подпрограмм для решения других задач, включая тестирование связности, распознавание последовательно-параллельных графов и построение st -нумерации графов (важная подпрограмма при проверке планарности ).

Разложение на ухо данного матроида с дополнительным ограничением, что каждое ухо содержит один и тот же фиксированный элемент матроида, может быть найдено за полиномиальное время при наличии доступа к оракулу независимости для матроида ( Coullard & Hellerstein 1996 ).

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