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

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

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

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

Связность графа

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Матроиды

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

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

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

Алгоритмы

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

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

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

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

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

Примечания

Литература