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

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск
Пример ушной декомпозиции графа, содержащей 3 уха.

В теории графов ухо неориентированного графа 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-связными с помощью открытой ушной декомпозиции, которая стартует с пути между двумя концами.

Матроиды[править | править код]

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

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

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

Алгоритмы[править | править код]

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

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

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

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

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

Примечания[править | править код]

Литература[править | править код]