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

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