Теорема Петерсена

Совершенное паросочетание (красные ребра) в графе Петерсена. Поскольку граф Петерсена кубический и двусвязный, то для него выполнены условия теоремы Петерсена.

Кубический (но не двусвязный) граф без совершенного паросочетания показывает, что условие двусвязности в теореме Петерсена не может быть опущено.

Теорема Петерсена — одна из самых ранних теорем теории графов, названная в честь Юлиуса Петерсена. Определение теоремы может быть сформулировано следующим образом:

Теорема Петерсена. Любой кубический двусвязный граф содержит в себе совершенное паросочетание.

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

Доказательство

Нужно показать, что для каждого кубического двусвязного графа $G=(V,E)$ справедливо, что для каждого набора $U\subseteq V$ количество нечётных компонент связности в подграфе $G\backslash U$ не превышает мощности $U$. Тогда по теореме Татта $G$ содержит совершенное паросочетание.

Пусть $G_{i}$ — компонента с нечётным числом вершин в подграфе $G\backslash U$. Пусть $V_{i}$ обозначает вершины $G_{i}$, а $m_{i}$ обозначает количество ребер $G$ с одной вершиной в $V_{i}$ и одной вершиной в $U$. Удвоив это значение, можно получить следующее:

$\sum \nolimits _{v\in V_{i}}\deg _{G}(v)=2|E_{i}|+m_{i},$

где $E_{i}$ — это множество рёбер $G_{i}$ с обеими вершинами в $V_{i}$. Поскольку

$\sum \nolimits _{v\in V_{i}}\deg _{G}(v)=3|V_{i}|$

является нечётным числом и $2|E_{i}|$ — чётное, то $m_{i}$ должно быть нечётным. Более того $m_{i}\geq 3$, так как $G$ — двусвязный граф.

Пусть $m$ — количество рёбер графа $G$, соединяющих вершины $U$ с вершинами графа $G\backslash U$. Каждая компонента с нечётным числом вершин добавляет в $m$ минимум 3 уникальных ребра, поэтому количество таких компонент не превышает $m/3$. В худшем случае каждое ребро с одной из вершин в $U$ будет учитываться при подсчёте $m$, а поэтому $m\leq 3|U|$. Получается, что

$|U|\geq {\frac {1}{3}}m\geq |odd(G\backslash U)|$

Условие теоремы Татта выполняется. Следовательно, в $G$ существует совершенное паросочетание

История

Теорема была названа в честь датского математика Юлиуса Петерсена. Считается одной из первых теорем теории графов. Впервые теорема появилась в статье 1891 года «Die Theorie der regulären graphs». Доказательство теоремы, представленное Петерсеном, считается сложным по сегодняшним стандартам. Серия упрощений доказательства представлена в доказательствах Фринка (Frink (1926)) и Кёнига (König (1936)).

В современных учебниках теорема Петерсена рассматривается как приложение теоремы Татта.

Применение

• В кубическом графе с совершенным паросочетанием рёбра, не входящие в это паросочетание, формируют 2-фактор. Ориентируя 2-фактор, рёбра совершенного паросочетания можно расширить до путей длины три, скажем, взяв рёбра, ориентированные наружу. Это показывает, что каждый кубический двусвязный граф раскладывается на непересекающиеся по рёбрам пути длины три.
• Теорема Петерсена может быть также применена для того, чтобы показать, что каждый максимальный планарный граф может быть разложен на множество непересекающихся по рёбрам путей длины три. В этом случае двойственный граф будет кубическим и двусвязным, поэтому согласно теореме Петерсена он имеет паросочетание, которое соответствует в исходном графе паре соседних треугольных граней. Каждая пара треугольников даёт путь длины три, включающий ребро, соединяющее треугольники вместе с двумя из четырёх оставшихся рёбер треугольника.
• Применяя теорему Петерсена к двойственному графу треугольной сетки и соединяя пары несовпадающих треугольников, можно разложить сетку на циклические полосы треугольников. С помощью некоторых дальнейших преобразований его можно превратить в единую полосу - получается метод преобразования треугольной сетки таким образом, что её двойственный граф становится гамильтоновым.

Расширения теоремы

Количество совершенных паросочетаний в кубических двусвязных графах

Ловас и Пламмер предположили, что количество совершенных паросочетаний, содержащихся в кубическом двусвязном графе, экспоненциально зависит от числа вершин графа $n$. Гипотеза была впервые доказана для двудольных кубических двусвязных графов Voorhoeve (1979), а затем для планарных кубических двусвязных доказательство представили Чудновски & Сеймур (2012). Общий случай был решен в Esperet et al. (2011), где было показано, что каждый кубический двусвязный граф содержит как минимум $2^{n/3656}$ совершенных паросочетаний.

Алгоритмические версии

Biedl et al. (2001) обсудили эффективные версии теоремы Петерсена. Основываясь на доказательстве Фринка, они получили алгоритм сложности $O(n\log ^{4}(n))$ для вычисления совершенного паросочетания в кубическом двусвязном графе с $n$ вершинами. Если граф, кроме того, планарный, в той же статье даётся алгоритм сложности $O(n)$. Их ограничение по времени $O(n\log ^{4}(n))$ может быть улучшено на основе последующих улучшений времени для поддержания множества мостов в динамическом графе. Дальнейшие улучшения, сокращающие время до $O(n\log ^{2}(n))$ или (с дополнительными случайными структурами данных) $O(n\log(n)\log ^{3}(\log(n)))$, были предложены Diks & Stanczyk (2010).

Повышение степени

Если $G$ — регулярный граф степени $d$, рёберная связность которого не меньше $d-1$, и $G$ имеет чётное число вершин, то он имеет совершенное паросочетание. Говоря более строго, каждое ребро графа $G$ принадлежит хотя бы одному совершенному паросочетанию. Условие на количество вершин можно опустить из этого утверждения, когда степень нечётна, потому что в этом случае (по лемме о рукопожатиях) количество вершин всегда чётно.