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

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

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

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

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

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

ДоказательствоПравить

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

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

${\sum <!--\; \sum \; -->}_{v\in <!--\; \in \; -->V_i}{\mathrm{deg}}_G<!--\; \; -->(v)=2|E_i|+m_i,$$\sum \nolimits _{v\in V_{i}}\deg _{G}(v)=2|E_{i}|+m_{i},$ 

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

${\sum <!--\; \sum \; -->}_{v\in <!--\; \in \; -->V_i}{\mathrm{deg}}_G<!--\; \; -->(v)=3|V_i|$$\sum \nolimits _{v\in V_{i}}\deg _{G}(v)=3|V_{i}|$ 

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

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

$|U|\ge <!--\; \ge \; -->\frac{1}{3}m\ge <!--\; \ge \; -->|\{\text{компоненты с нечётным числом вершин}\}|,$$|U|\geq {\frac {1}{3}}m\geq |\{{\text{компоненты с нечётным числом вершин}}\}|,$ 

Таким образом условие теоремы Татта выполняется.

ИсторияПравить

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

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

ПрименениеПравить

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

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

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

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

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

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

Повышение степениПравить

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