Разложение ушей

Разделение графа на последовательность путей

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

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

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

Характеристика классов графов

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

Графовая связность

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

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

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

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

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

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

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

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

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

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

Приведенные выше определения также можно применить к ориентированным графам . Тогда ухо будет направленным путем, в котором все внутренние вершины имеют степень входа и выхода , равную 1. Ориентированный граф является сильно связным , если он содержит направленный путь от каждой вершины к каждой другой вершине. Тогда мы имеем следующую теорему (Bang-Jensen & Gutin 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):

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

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

Матроиды

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

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

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

Алгоритмы

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

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

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

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

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

Рекомендации

• Банг-Йенсен, Йорген; Гутин, Грегори (2007), «7.2 Ушные разложения», Орграфы: теория, алгоритмы и приложения , Springer-Verlag, стр. 349–352
• Чериян, Дж.; Махешвари, С.Н. (1988), «Нахождение неразделяющих индуцированных циклов и независимых остовных деревьев в 3-связных графах», Journal of Algorithms , 9 (4): 507–537, doi : 10.1016/0196-6774(88)90015-6, МР  0970192.
• Куллард, Коллетт Р .; Хеллерштейн, Лиза (1996), «Независимость и порт-оракулы для матроидов с применением к теории вычислительного обучения», Combinatorica , 16 (2): 189–208, doi : 10.1007/BF01844845, MR  1401892, S2CID  1437169.
• Эппштейн, Д. (1992), «Параллельное распознавание последовательно-параллельных графов» (PDF) , Information and Computation , 98 (1): 41–55, doi : 10.1016/0890-5401(92)90041-D, MR  1161075.
• Франк, Андраш (1993), «Консервативное взвешивание и ушное разложение графов», Combinatorica , 13 (1): 65–81, doi : 10.1007/BF01202790, MR  1221177, S2CID  10857300.
• Гросс, Джонатан Л.; Йеллен, Джей (2006), «Характеристика сильно ориентируемых графов», Теория графов и ее приложения, Дискретная математика и ее приложения (Бока-Ратон) (2-е изд.), Chapman & Hall/CRC, Бока-Ратон, Флорида, стр. 498– 499, ISBN 978-1-58488-505-4, МР  2181153.
• Хуллер, Самир (1989), «Разложение уха» (PDF) , SIGACT News , 20 (1): 128.
• Ловас, Ласло (1972), «Заметки о факторно-критических графах», Studia Sci. Математика. Висела. , 7 : 279–280, МР  0335371.
• Ловас, Ласло (1985), «Параллельные вычисления и ветвления», 26-й ежегодный симпозиум по основам информатики , стр. 464–467, номер документа : 10.1109/SFCS.1985.16, S2CID  14879896.
• Маон, Ю.; Шибер, Б.; Вишкин, У. (1986), «Поиск с разложением параллельного уха (EDS) и нумерация ST в графиках», Theoretical Computer Science , 47 (3): 277–298, doi : 10.1016/0304-3975(86)90153-2 , МР  0882357.
• Миллер, Г .; Рамачандран, В. (1986), Эффективное параллельное разложение ушей с применением , Неопубликованная рукопись.
• Роббинс, HE (1939), «Теорема о графах с применением к проблеме управления дорожным движением» (PDF) , American Mathematical Monthly , 46 (5): 281–283, doi : 10.2307/2303897, JSTOR  2303897.
• Шмидт, Йенс М. (2013a), «Простой тест на связность 2 вершин и 2 ребер», Information Processing Letters , 113 (7): 241–244, arXiv : 1209.0700 , doi : 10.1016/j.ipl .2013.01.016, S2CID  7040381.
• Шмидт, Йенс М. (2013b), Последовательность Мондшейна , arXiv : 1311.0750 , Бибкод : 2013arXiv1311.0750S.
• Шрийвер, Александр (2003), Комбинаторная оптимизация. Многогранники и эффективность. Том А , Springer-Verlag, ISBN 978-3-540-44389-6.
• Сегеди, Балаж ; Сегеди, Кристиан (2006), «Симплектические пространства и ушное разложение матроидов», Combinatorica , 26 (3): 353–377, doi : 10.1007/s00493-006-0020-3, MR  2246153, S2CID  11578490.
• Уитни, Х. (1932), «Неразделимые и плоские графы», Труды Американского математического общества , 34 (2): 339–362, doi : 10.1090/S0002-9947-1932-1501641-2 , JSTOR  1989545.