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

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

В математической дисциплине графов теории теорема Петерсена , названная в честь Юлиуса Петерсена , является одним из самых ранних результатов в теории графов и может быть сформулирована следующим образом:

Теорема Петерсена. Каждый кубический содержит граф без мостов идеальное паросочетание . ^{[ 1 ]}

Другими словами, если граф имеет ровно три ребра в каждой вершине и каждое ребро принадлежит циклу, то у него есть набор ребер, который касается каждой вершины ровно один раз.

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

Мы показываем, что для любого кубического графа без мостов $G = (V, E)$ мы имеем, что для любого множества $U \subseteq V$ количество компонент связности в графе, индуцированном V $с нечетным числом вершин , - U$ не превышает мощности $У.$ Тогда по теореме Тутте $G$ содержит совершенное паросочетание.

Пусть $G i$ — компонента с нечетным числом вершин в графе, индуцированная множеством вершин $V - U$ . Пусть $V i$ обозначает вершины $G i$ и пусть $обозначает mi$ количество ребер $G$ с одной вершиной в $и Vi$ одной вершиной в $U$ . Используя простой аргумент двойного подсчета, мы получаем, что

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

где $E i$ множество ребер $G i$ с обеими вершинами в $Vi .$ — С

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

— нечетное число и $2| Э я |$ является четным числом, из этого следует, что $m i$ должно быть нечетным числом. Более того, поскольку $G$ не имеет мостов, мы имеем, что $\geq mi 3$ .

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

|U|\geq {\frac {1}{3}}m\geq |\{{\text{components with an odd number of vertices}}\}|,

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

История

Теорема принадлежит Юлиусу Петерсену , датскому математику. Его можно рассматривать как один из первых результатов в теории графов . Теорема впервые появляется в статье 1891 года « Теория регулярных графов ». ^{[ 1 ]} По сегодняшним меркам доказательство Петерсена теоремы сложно. Серия упрощений доказательства завершилась доказательствами Фринка (1926) и Кенига (1936) .

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

Приложения

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

Расширения

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

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

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

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

Высшая степень

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

Примечания

^ Перейти обратно: ^а ^б Петерсен (1891) .
^ См., например, Буше и Фуке (1983) .
^ Хэггквист и Йоханссон (2004) .
^ Минакшисундарам и Эппштейн (2004) .
^ Ловас и Пламмер (1986) .
^ Фринк (1926) .
^ Торуп (2000) .
^ Наддеф и Пуллибланк (1981) , Теорема 4, с. 285.

Ссылки

Бидль, Тереза К .; Бозе, Просенджит ; Демейн, Эрик Д .; Любив, Анна (2001), «Эффективные алгоритмы для теоремы соответствия Петерсена», Журнал алгоритмов , 38 (1): 110–134, doi : 10.1006/jagm.2000.1132 , MR 1810434
Буше, Андре; Фуке, Жан-Люк (1983), «Три типа разложения графа на цепи», у К. Берже; Д. Брессон; П. Грузовик; Ж. Ф. Моррас; Ф. Стербул (ред.), Комбинаторная математика: материалы Международного коллоквиума по теории графов и комбинаторике (Марсель-Люмини, 1981) , Математические исследования Северной Голландии (на французском языке), том. 75, Северная Голландия, с. 131–141, doi : 10.1016/S0304-0208(08)73380-2 , ISBN 978-0-444-86512-0 , МР 0841287
Чудновская Мария ; Сеймур, Пол (2012), «Идеальные паросочетания в плоских кубических графах», Combinatorica , 32 (4): 403–424, doi : 10.1007/s00493-012-2660-9 , MR 2965284
Дикс, Кшиштоф; Станчик, Петр (2010), «Идеальное сопоставление для двусвязных кубических графов в $O (n log 2 n)$ время», в Ван Леувен, Ян ; Мусхолл, Анка ; Пелег, Давид ; Покорный, Ярослав; Румпе, Бернхард (ред.), SOFSEM 2010: 36-я конференция по текущим тенденциям в теории и практике информатики, Шпиндлерув Млын, Чешская Республика, 23–29 января 2010 г., Труды , Конспекты лекций по информатике, том 5901, Springer, стр. 321–333, номер домена : 10.1007/978-3-642-11266-9_27 , ISBN. 978-3-642-11265-2
Эспере, Луи; Кардош, Франтишек; Кинг, Эндрю Д.; Краль, Дэниел ; Норин, Сергей (2011), «Экспоненциально много совершенных паросочетаний в кубических графах», Успехи в математике , 227 (4): 1646–1664, arXiv : 1012.2878 , doi : 10.1016/j.aim.2011.03.015 , MR 2799808
Фринк, Оррин (1926), «Доказательство теоремы Петерсена», Annals of Mathematics , Second Series, 27 (4): 491–493, doi : 10.2307/1967699 , JSTOR 1967699
Хэггквист, Роланд; Йоханссон, Роберт (2004), «Заметки о реберном разложении плоских графов», Discrete Mathematics , 283 (1–3): 263–266, doi : 10.1016/j.disc.2003.11.017 , MR 2061501
Кениг, Денес (1936), Теория конечных и бесконечных графов; Комбинаторная топология комплексов маршрутов.
Ловас, Ласло ; Пламмер, доктор медицинских наук (1986), Теория соответствия , Анналы дискретной математики, том. 29, Северная Голландия, ISBN 0-444-87916-1 МР 0859549
Минакшисундарам, Гопи; Эппштейн, Дэвид (2004), «Однополосная триангуляция многообразий с произвольной топологией», Proc. 25-я Конф. Евро. доц. для компьютерной графики (Eurographics '04) , Форум компьютерной графики, том. 23, стр. 371–379, arXiv : cs.CG/0405036 , doi : 10.1111/j.1467-8659.2004.00768.x
Наддеф, Д.; Пуллибланк, WR (1981), «Сочетания в регулярных графах», Discrete Mathematics , 34 (3): 283–291, doi : 10.1016/0012-365X(81)90006-6 , MR 0613406 .
Петерсен, Юлиус (1891), «Теория регулярных графов», Acta Mathematica , 15 : 193–220, doi : 10.1007/BF02392606
Торуп, Миккель (2000), «Почти оптимальная полностью динамическая связность графов», Proc. 32-й симпозиум ACM по теории вычислений , стр. 343–350, doi : 10.1145/335305.335345 , ISBN 1-58113-184-4 , МР 2114549
Вурхув, Марк (1979), «Нижняя оценка перманентов некоторых (0,1)-матриц», Indagationes Mathematicae , 82 (1): 83–86, doi : 10.1016/1385-7258(79)90012-X , МР 0528221

[p1891-1] Перейти обратно: ^а ^б Петерсен (1891) .

[2] См., например, Буше и Фуке (1983) .

[3] Хэггквист и Йоханссон (2004) .

[FOOTNOTEMeenakshisundaramEppstein2004-4] Минакшисундарам и Эппштейн (2004) .

[FOOTNOTELovászPlummer1986-5] Ловас и Пламмер (1986) .

[6] Фринк (1926) .

[FOOTNOTEThorup2000-7] Торуп (2000) .

[8] Наддеф и Пуллибланк (1981) , Теорема 4, с. 285.

[ 1 ]

[ 2 ]

[ 3 ]

[ 4 ]

[ 5 ]

[ 6 ]

[ 7 ]

[ 8 ]