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

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

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

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

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

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

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

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

Пусть G _i будет компонентом с нечетным числом вершин в графе, индуцированном множеством вершин V  −  U. Пусть V _i обозначает вершины G _i , а m _i обозначает число ребер G с одной вершиной в V _i и одной вершиной в U. С помощью простого аргумента двойного подсчета мы имеем, что

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

где E _i — множество ребер G _i с обеими вершинами в V _i . Так как

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

нечетное число, а 2| E _i | четное число, то следует, что m _i должно быть нечетным числом. Более того, поскольку G не имеет мостов, то m _i  ≥ 3 .

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

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

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

История

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

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

Приложения

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

Расширения

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

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

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

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

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

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

Смотрите также

• Теорема о 2 факторах – родственная теорема Петерсена

Примечания

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

Ссылки

• Biedl, Therese C. ; Bose, Prosenjit ; Demaine, Erik D. ; Lubiw, Anna (2001), "Эффективные алгоритмы для теоремы Петерсена о соответствиях", Journal of Algorithms , 38 (1): 110–134, doi :10.1006/jagm.2000.1132, MR  1810434
• Буше, Андре; Фуке, Жан-Люк (1983), «Три типа декомпозиций графа в цепочках», в К. Берже; Д. Брессон; П. Кэмион; Ж. Ф. Моррас; Ф. Стербул (ред.), Комбинаторная математика: материалы Международного коллоквиума по теории графов и комбинаторике (Марсель-Люмини, 1981) , Математические исследования Северной Голландии (на французском языке), том. 75, Северная Голландия, стр. 131–141, номер документа : 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
• Diks, Krzysztof; Stanczyk, Piotr (2010), "Perfect matching for biconnected cubic graphs in O( n log ² n ) time", в van Leeuwen, Jan ; Muscholl, Anca ; Peleg, David ; Pokorný, Jaroslav; Rumpe, Bernhard (ред.), SOFSEM 2010: 36-я конференция по текущим тенденциям в теории и практике компьютерных наук, Шпиндлерув-Млин, Чешская Республика, 23–29 января 2010 г., Труды , Lecture Notes in Computer Science, т. 5901, Springer, стр. 321–333, doi :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 , вторая серия, 27 (4): 491–493, doi :10.2307/1967699, JSTOR  1967699
• Хеггквист, Роланд; Йоханссон, Роберт (2004), «Заметка о рёберных декомпозициях планарных графов», Дискретная математика , 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), "Однополосная триангуляция многообразий с произвольной топологией", Труды 25-й конференции Европейской ассоциации компьютерной графики (Eurographics '04) , Форум компьютерной графики, т. 23, стр. 371–379, arXiv : cs.CG/0405036 , doi :10.1111/j.1467-8659.2004.00768.x
• Наддеф, Д.; Пуллибланк, В. Р. (1981), «Соответствия в регулярных графах», Дискретная математика , 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), «Почти оптимальная полностью динамическая связность графа», Труды 32-го симпозиума ACM по теории вычислений , стр. 343–350, doi :10.1145/335305.335345, ISBN 1-58113-184-4, МР  2114549
• Voorhoeve, Marc (1979), «Нижняя граница для перманентов некоторых (0,1)-матриц», Indagationes Mathematicae , 82 (1): 83–86, doi : 10.1016/1385-7258(79)90012-X , MR  0528221