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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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