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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Факторно-критические графы

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

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

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

Серийно-параллельные графики

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

Следующий результат принадлежит Дэвиду Эппштейну ( 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, doi : 10.1109/SFCS.1985.16 , ISBN  0-8186-0644-4 , 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 , Bibcode : 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), «Неразделимые и плоские графы», Transactions of the American Mathematical Society , 34 (2): 339–362, doi : 10.1090/S0002-9947-1932-1501641-2 , JSTOR   1989545 .