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

Пример ушной декомпозиции графа, содержащей 3 уха.

В теории графов ухо неориентированного графа 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].

Примечания

1. Whitney, 1932.
2. Robbins, 1939.
3. Gross, Yellen, 2006.
4. Cheriyan, Maheshwari, 1988.
5. Schmidt, 2013b.
6. Lovász, 1972.
7. Frank, 1993.
8. Khuller, 1989.
9. Eppstein, 1992.
10. Szegedy, Szegedy, 2006.
11. Schmidt, 2013a.
12. Lovász, 1985.
13. Maon, Schieber, Vishkin, 1986.
14. Miller, Ramachandran, 1986.
15. Coullard, Hellerstein, 1996.

Литература

• J. Cheriyan, S. N. Maheshwari. Finding nonseparating induced cycles and independent spanning trees in 3-connected graphs // Journal of Algorithms. — 1988. — Т. 9, вып. 4. — С. 507–537. — doi:10.1016/0196-6774(88)90015-6.
• Collette R. Coullard, Lisa Hellerstein. Independence and port oracles for matroids, with an application to computational learning theory // Combinatorica. — 1996. — Т. 16, вып. 2. — С. 189–208. — doi:10.1007/BF01844845.
• D. Eppstein. Parallel recognition of series-parallel graphs // Information & Computation. — 1992. — Т. 98, вып. 1. — С. 41–55. — doi:10.1016/0890-5401(92)90041-D.
• András Frank. Conservative weightings and ear-decompositions of graphs // Combinatorica. — 1993. — Т. 13, вып. 1. — С. 65–81. — doi:10.1007/BF01202790.
• Jonathan L. Gross, Jay Yellen. Graph theory and its applications. — 2nd. — Chapman &Hall/CRC, Boca Raton, FL, 2006. — С. 498–499. — (Discrete Mathematics and its Applications (Boca Raton)). — ISBN 978-1-58488-505-4.
• Samir Khuller. Ear decompositions // SIGACT News. — 1989. — Т. 20, вып. 1. — С. 128.
• László Lovász. A note on factor-critical graphs // Studia Sci. Math. Hung.. — 1972. — Т. 7. — С. 279–280.
• László Lovász. 26th Annual Symposium on Foundations of Computer Science. — 1985. — С. 464–467. — doi:10.1109/SFCS.1985.16.
• Y. Maon, B. Schieber, U. Vishkin. Parallel ear decomposition search (EDS) and ST-numbering in graphs // Theoretical Computer Science. — 1986. — Т. 47, вып. 3. — doi:10.1016/0304-3975(86)90153-2.
• G. Miller, V. Ramachandran. Efficient parallel ear decomposition with applications. — Unpublished manuscript, 1986.
• H. E. Robbins. A theorem on graphs, with an application to a problem of traffic control // American Mathematical Monthly. — 1939. — Т. 46. — С. 281–283. — doi:10.2307/2303897..
• Jens M. Schmidt. A Simple Test on 2-Vertex- and 2-Edge-Connectivity // Information Processing Letters. — 2013a. — Т. 113, вып. 7. — С. 241–244. — doi:10.1016/j.ipl.2013.01.016.
• Jens M. Schmidt. The Mondshein sequence. — 2013b.
• Alexander Schrijver. Combinatorial Optimization. Polyhedra and efficiency. Vol A. — Springer-Verlag, 2003. — ISBN 978-3-540-44389-6.
• Balázs Szegedy, Christian Szegedy. Symplectic spaces and ear-decomposition of matroids // Combinatorica. — 2006. — Т. 26, вып. 3. — С. 353–377. — doi:10.1007/s00493-006-0020-3.
• H. Whitney. Non-separable and planar graphs // Transactions of the American Mathematical Society. — 1932. — Т. 34. — С. 339–362. — doi:10.1090/S0002-9947-1932-1501641-2. — JSTOR 1989545.