Ушная декомпозиция

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

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

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

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

Следующий результат принадлежит Хаслеру Уитни ^[1]:

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

Следующий результат принадлежит Герберту Робинсону^[2]:

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

В обоих случаях число ушей необходимо равно контурному рангу графа. Роббинс применил ушную декомпозицию рёберно 2-связных графов в качестве средства доказательства теоремы Роббинса, что это в точности графы, которым может быть задана сильно связная ориентация. Поскольку Уитни и Робинсон первыми исследовали ушную декомпозицию, она иногда называется синтезом Уитни – Робинсона^[3].

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

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

Если такая декомпозиция существует, она может быть выбрана относительно ребра uv графа G таким образом, что u принадлежит первому уху, v является новой вершиной в последнем ухе с более чем одним ребром и uv является ухом, состоящим из одного ребра. Этот результат впервые высказали явно Черьян и Махешвари^[4], но, как пишет Шмидт^[5], он эквивалентен результату тезисов Ph.D. диссертации 1971 года Ли Мондшейна. Структуры, тесно связанные с неразделяющими ушными декомпозициями максимальных планарными графами, называемые каноническими упорядочениями, являются также стандартным средством визуализации графов.

Определения, приведённые выше, могут быть перенесены также на ориентированные графы. Ухом тогда будет ориентированный путь, в котором все внутренние вершины имеют полустепень захода и полустепень исхода, равные 1. Ориентированный граф является сильно связным, если он содержит ориентированный путь из любой вершины в любую другую вершину. Тогда имеет место следующая теорема:

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

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

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

Ушная декомпозиции нечётна, если каждое ухо имеет нечётное число рёбер. Фактор-критический граф, это граф с нечётным числом вершин, такой, что при удалении любой вершины v из графа оставшиеся вершины имеют совершенное паросочетание. Ласло Ловас^[6] обнаружил, что:

Граф G является фактор-критическим графом тогда и только тогда, когда G имеет нечётную ушную декомпозицию.

В более общем смысле, результат Франка^[7] делает возможным найти для любого графа G ушную декомпозицию с наименьшим количеством чётных ушей.

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

Следующий результат принадлежит Дэвиду Эпштейну^[9]:

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

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

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

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

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

Ушная декомпозиция рёберно 2-связных графов и открытая декомпозиция вершинно 2-связных графов могут быть найдены с помощью жадных алгоритмов, которые находят каждое ухо поодиночке. Простой жадный алгоритм, вычисляющий за одно и то же время ушное разложение, открытое ушное разложение, st-нумерацию^[англ.] и st-ориентацию за линейное время (если они существуют), предложил Шмидт^[11]. Подход основывается на вычислении специального вида ушной декомпозиции, разложения на цепи с одним правилом генерации путей. Шмидт показал^[5], что неразделяющая ушная декомпозиция может быть построена за линейное время.

Ловас^[12], Маон, Шибер и Вышкин^[13], а также Миллер и Рамачандран^[14] привели эффективные параллельные алгоритмы для построения ушных декомпозиций различных типов. Например, чтобы найти ушную декомпозицию рёберно 2-связного графа, алгоритм Маона, Шибера и Вышкина^[13] проходит следующие шаги:

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

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

Ушная декомпозиция матроида с дополнительным ограничением, что любое ухо содержит одно и то же фиксированное число элементов матроида, может быть найдено за полиномиальное время, если имеется оракул независимости^[англ.] для матроида^[15].