Ушная декомпозиция (Rougx ;ytkbhk[nenx)
В теории графов ухо неориентированного графа G — это путь P, у которого две конечные точки могут совпадать, но в противном случае не разрешается повторение вершин или рёбер, так что любая внутренняя точка пути P имеет в пути степень два. Ушная декомпозиция неориентированного графа G — это разбиение множества его рёбер на последовательность ушей, так что конечные точки каждого уха принадлежат ранее выделенным ушам в последовательности, при этом внутренние вершины каждого уха не принадлежат предыдущим ушам. Кроме того, в большинстве случаев первое ухо в последовательности должно быть циклом. Открытая или правильная ушная декомпозиция — это ушная декомпозиция, в которой две конечные точки каждого уха, кроме первого, отличаются.
Ушную декомпозицию можно использовать для описания некоторых важных классов графов, и как часть эффективных алгоритмов на графах. Ушную декомпозицию можно обобщить для матроидов.
Описание классов графов
[править | править код]Некоторые важные классы графов могут быть описаны определённым типом ушных декомпозиций.
Связность графа
[править | править код]Граф вершинно k-связнен, если удаление лишь (k − 1) вершин оставляет подграф связным, и рёберно k-связен, если удаление любых (k − 1) рёбер оставляет связный подграф.
Следующий результат принадлежит Хаслеру Уитни [1]:
- Граф с вершинно 2-связен тогда и только тогда, когда для него существует открытая ушная декомпозиция.
Следующий результат принадлежит Герберту Робинсону[2]:
- Граф рёберно 2-связен тогда и только тогда, когда для него существует ушная декомпозиция.
В обоих случаях число ушей необходимо равно контурному рангу графа. Роббинс применил ушную декомпозицию рёберно 2-связных графов в качестве средства доказательства теоремы Роббинса, что это в точности графы, которым может быть задана сильно связная ориентация. Поскольку Уитни и Робинсон первыми исследовали ушную декомпозицию, она иногда называется синтезом Уитни – Робинсона[3].
Неразделяющая ушная декомпозиция — это открытая ушная декомпозиция, такая, что для каждой вершины v, за исключением одной, v имеет соседнюю вершину, которая появляется в декомпозиции позже вершины v. Этот тип декомпозиции можно использовать для обобщения результата Уитни:
- Граф с является вершинно 3-связным тогда и только тогда, когда G имеет неразделяющую ушную декомпозицию.
Если такая декомпозиция существует, она может быть выбрана относительно ребра uv графа G таким образом, что u принадлежит первому уху, v является новой вершиной в последнем ухе с более чем одним ребром и uv является ухом, состоящим из одного ребра. Этот результат впервые высказали явно Черьян и Махешвари[4], но, как пишет Шмидт[5], он эквивалентен результату тезисов Ph.D. диссертации 1971 года Ли Мондшейна. Структуры, тесно связанные с неразделяющими ушными декомпозициями максимальных планарными графами, называемые каноническими упорядочениями, являются также стандартным средством визуализации графов.
Сильная связность ориентированных графов
[править | править код]Определения, приведённые выше, могут быть перенесены также на ориентированные графы. Ухом тогда будет ориентированный путь, в котором все внутренние вершины имеют полустепень захода и полустепень исхода, равные 1. Ориентированный граф является сильно связным, если он содержит ориентированный путь из любой вершины в любую другую вершину. Тогда имеет место следующая теорема:
- Ориентированный граф является сильно связным тогда и только тогда, когда он имеет ушную декомпозицию.
Аналогично, ориентированный граф является двусвязным, если для любых двух вершин существует простой цикл, содержащий обе вершины. Тогда
- Ориентированный граф является двусвязным тогда и только тогда, когда у него есть открытая ушная декомпозиция.
Фактор-критические графы
[править | править код]Ушная декомпозиции нечётна, если каждое ухо имеет нечётное число рёбер. Фактор-критический граф, это граф с нечётным числом вершин, такой, что при удалении любой вершины v из графа оставшиеся вершины имеют совершенное паросочетание. Ласло Ловас[6] обнаружил, что:
- Граф G является фактор-критическим графом тогда и только тогда, когда G имеет нечётную ушную декомпозицию.
В более общем смысле, результат Франка[7] делает возможным найти для любого графа G ушную декомпозицию с наименьшим количеством чётных ушей.
Параллельно-последовательные графы
[править | править код]Древесная ушная декомпозиция — это правильная ушная декомпозиция, в которой первое ухо является отдельным ребром и для каждого последующего уха существует единственное ухо , , в котором обе конечные точки лежат на [8]. Вложенная ушная декомпозиция — это древесная ушная декомпозиция, такая, что внутри каждого уха множество пар конечных точек других ушей , лежащих внутри , образует множество вложенных интервалов. Параллельно-последовательный граф — это граф с двумя выделенными различными концами s и t, который может быть образован рекурсивно путём комбинирования меньших параллельно-последовательных графов одним из двух способов — последовательное соединение (отождествляем один конец одного из графов с одним концом другого графа, а другие два конца обоих графов становятся концами объединения) и параллельное соединение (отождествляем обе пары терминалов обоих меньших графов).
Следующий результат принадлежит Дэвиду Эпштейну[9]:
- Вершинно 2-связный граф является параллельно-последовательным графом тогда и только тогда, когда он имеет вложенную ушную декомпозицию.
Более того, любая открытая ушная декомпозиция вершинно 2-связного параллельно-последовательного графа должна быть вложенной. Результат можно обобщить на параллельно-последовательные графы, не являющиеся вершинно 2-связными с помощью открытой ушной декомпозиции, которая стартует с пути между двумя концами.
Матроиды
[править | править код]Концепция ушной декомпозиции может быть обобщена с графов на матроиды. Ушная декомпозиция матроида определяется как последовательность циклов матроида, имеющая два свойства:
- каждый цикл в последовательности имеет непустое пересечение с предыдущими циклами.
- каждый цикл в последовательности остаётся циклом, даже если все предыдущие циклы в последовательности стянуть.
Если применить к графовому матроиду[англ.] графа G, это определение ушной декомпозиции совпадает с определением правильной декомпозиции G — неправильные декомпозиции исключаются требованием, что каждый цикл включает по меньшей мере одно ребро, принадлежащее предыдущим циклам. Если использовать это определение, матроид может быть определён фактор–критичным, если он имеет ушную декомпозицию, в которой каждый цикл в последовательности имеет нечётное число новых элементов[10].
Алгоритмы
[править | править код]Ушная декомпозиция рёберно 2-связных графов и открытая декомпозиция вершинно 2-связных графов могут быть найдены с помощью жадных алгоритмов, которые находят каждое ухо поодиночке. Простой жадный алгоритм, вычисляющий за одно и то же время ушное разложение, открытое ушное разложение, st-нумерацию[англ.] и st-ориентацию за линейное время (если они существуют), предложил Шмидт[11]. Подход основывается на вычислении специального вида ушной декомпозиции, разложения на цепи с одним правилом генерации путей. Шмидт показал[5], что неразделяющая ушная декомпозиция может быть построена за линейное время.
Ловас[12], Маон, Шибер и Вышкин[13], а также Миллер и Рамачандран[14] привели эффективные параллельные алгоритмы для построения ушных декомпозиций различных типов. Например, чтобы найти ушную декомпозицию рёберно 2-связного графа, алгоритм Маона, Шибера и Вышкина[13] проходит следующие шаги:
- Находится остовное дерево заданного графа и выбирается корень дерева.
- Для каждого ребра uv, не являющегося частью дерева, определяем расстояние между корнем и наименьшим общим предком u и v.
- Для каждого ребра uv, являющегося частью дерева, находим соответствующее «главное ребро», ребро wx не из дерева, такое, что цикл, образованный добавлением wx к дереву, проходит через uv и такое, что среди всех рёбер w и x имеет самого низкого предка, как можно более близкого к корню.
- Образуем ухо для каждого ребра не из дерева, состоящее из этого ребра и рёбер дерева, для которых это ребро является главным. Упорядочиваем уши по расстояниям главного ребра от корня.
Этот алгоритм можно использовать в качестве процедуры для других задач, включая проверку связности, распознавание последовательно-параллельных графов и построение st-нумерации графов (важная процедура для проверки планарности).
Ушная декомпозиция матроида с дополнительным ограничением, что любое ухо содержит одно и то же фиксированное число элементов матроида, может быть найдено за полиномиальное время, если имеется оракул независимости[англ.] для матроида[15].
Примечания
[править | править код]- ↑ Whitney, 1932.
- ↑ Robbins, 1939.
- ↑ Gross, Yellen, 2006.
- ↑ Cheriyan, Maheshwari, 1988.
- ↑ 1 2 Schmidt, 2013b.
- ↑ Lovász, 1972.
- ↑ Frank, 1993.
- ↑ Khuller, 1989.
- ↑ Eppstein, 1992.
- ↑ Szegedy, Szegedy, 2006.
- ↑ Schmidt, 2013a.
- ↑ Lovász, 1985.
- ↑ 1 2 Maon, Schieber, Vishkin, 1986.
- ↑ Miller, Ramachandran, 1986.
- ↑ 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. — .
Для улучшения этой статьи желательно:
|