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

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

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

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

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

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

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

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

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

$\sum _{v\in V_i}{\mathrm{deg}}_G(v)=2|E_i|+m_i,$

где $E_i$ — это множество рёбер $G_i$ с обеими вершинами в $V_i$. Поскольку

$\sum _{v\in V_i}{\mathrm{deg}}_G(v)=3|V_i|$

является нечётным числом и $2|E_i|$ — чётное, то $m_i$ должно быть нечётным. Более того $m_i\ge 3$, так как $G$ — двусвязный граф.

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

$|U|\ge \frac{1}{3}m\ge |odd(G\mathrm{\setminus }U)|$

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

История

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

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

Применение

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

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

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

Ловас и Шаблон:Iw предположили, что количество совершенных паросочетаний, содержащихся в кубическом двусвязном графе, экспоненциально зависит от числа вершин графа $n$Шаблон:Sfn. Гипотеза была впервые доказана для двудольных кубических двусвязных графов Шаблон:Harvtxt, а затем для планарных кубических двусвязных доказательство представили Шаблон:Harvtxt. Общий случай был решен в Шаблон:Harvtxt, где было показано, что каждый кубический двусвязный граф содержит как минимум $2^{n/3656}$ совершенных паросочетаний.

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

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

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

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

Ссылки

• Шаблон:Citation
• Шаблон:Citation
• Шаблон:Citation
• Шаблон:Citation
• Шаблон:Citation
• Шаблон:Citation
• Шаблон:Citation
• Шаблон:Citation
• Шаблон:Книга
• Шаблон:Citation
• Шаблон:Citation.
• Шаблон:Citation
• Шаблон:Citation
• Шаблон:Citation