Разложение уха - Ear decomposition

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

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

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

Описание классов графов

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

Связь с графиком

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Матроиды

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

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

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

Алгоритмы

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

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

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

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

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

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

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