В математической дисциплине теории графов , теорема Петерсена , названная в честь Julius Петерсно , является одним из самых ранних результатов в теории графов и может быть сформулирована следующим образом :
Теорема Петерсена. Каждый кубический , bridgeless граф содержит полное совпадение . [1]
Другими словами, если граф имеет ровно три ребра в каждой вершине и каждое ребро принадлежит циклу, то у него есть набор ребер, которые касаются каждой вершины ровно один раз.
Доказательство
Покажем , что для каждого кубика, bridgeless графа G = ( V , E ) мы имеем , что для каждого множества U ⊆ V число компонент связности в графе , индуцированной с помощью V - U с нечетным числом вершин не превосходит мощности U . Тогда по теореме Тютте G содержит совершенное паросочетание.
Пусть G я быть компонентом с нечетным числом вершин в графе , индуцированное множество вершин V - U . Пусть V я обозначу вершину G я и пусть м я обозначу число ребер G с одной вершиной в V я и одна вершины в U . Используя простой аргумент двойного счета, мы имеем, что
где E i - множество ребер графа G i с обеими вершинами из V i . С
нечетное число и 2 | E i | является четным числом, следовательно, m i должно быть нечетным числом. Более того, поскольку G не имеет мостов, имеем m i ≥ 3 .
Пусть т быть число ребер в G с одной вершиной в U и одной вершины в графе , индуцированной V - U . Каждая компонента с нечетным числом вершин дает не менее 3 ребер в m , и они уникальны, поэтому количество таких компонентов не превышает m / 3 . В худшем случае каждое ребро с одной вершиной в U вносит вклад в m , и поэтому m ≤ 3 | U | . Мы получили
что показывает выполнение условия теоремы Тутте .
История
Теорема принадлежит Юлиусу Петерсену , датскому математику. Это можно считать одним из первых результатов теории графов . Теорема впервые появляется в статье 1891 года « Теория регулятивных графов ». [1] По сегодняшним меркам доказательство теоремы Петерсеном сложно. Серия упрощений доказательства завершилась доказательствами Фринка (1926) и Кенига (1936) .
В современных учебниках теорема Петерсена рассматривается как приложение теоремы Тутте .
Приложения
- В кубическом графе с идеальным совпадением ребра, которые не находятся в идеальном совпадении, образуют 2-фактор . По ориентирующему 2-фактору, края совершенного соответствия могут быть расширены до путей длины три, скажем, беря наружу ориентированные ребра. Это показывает, что каждый кубический граф без мостов распадается на рёберно-непересекающиеся пути длины три. [2]
- Теорема Петерсена также может быть применена, чтобы показать, что любой максимальный планарный граф может быть разложен на набор рёберно непересекающихся путей длины три. В этом случае двойственный граф является кубическим и без мостов, поэтому по теореме Петерсена он имеет сопоставление, которое соответствует в исходном графе паре смежных граней треугольника. Каждая пара треугольников дает путь длиной три, который включает ребро, соединяющее треугольники вместе с двумя из четырех оставшихся ребер треугольника. [3]
- Применяя теорему Петерсена к двойственному графу треугольной сетки и соединяя пары треугольников, которые не совпадают, можно разложить сетку на циклические полосы треугольников . С некоторыми дальнейшими преобразованиями он может быть превращен в единую полосу и, следовательно, дает метод преобразования треугольной сетки так, что ее дуальный граф становится гамильтоновым . [4]
Расширения
Число совершенных сопоставлений в кубических графах без мостов
Было высказано предположение , по Lovász и Пламмеру , что число совершенных паросочетаний содержится в кубической , bridgeless графы является экспоненциальным числом вершин графа п . [5] Гипотеза была впервые доказана для двудольных кубических графов без мостов Вурхувом (1979) , позже для плоских кубических графов без мостов Чудновским и Сеймуром (2012) . Общий случай был урегулирован Esperet et al. (2011) , где было показано, что каждый кубический граф без мостов содержит не менее идеальное соответствие.
Алгоритмические версии
Biedl et al. (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) .
- ^ См., Например, Bouchet & Fouquet (1983) .
- ^ Хэггквист и Йоханссон (2004) .
- ^ Meenakshisundaram & Эпштайна (2004) .
- ^ Lovász & Пламмер (1986) .
- ^ Фринк (1926) .
- ^ Thorup (2000) .
- ^ Naddef & Pulleyblank (1981) , теорема 4, стр. 285.
Рекомендации
- Бидль, Тереза К .; Бозе, Просенджит ; Демейн, Эрик Д .; Lubiw, Анна (2001), "Эффективные алгоритмы теоремы Петерсена соответствия", журнал алгоритмов , 38 (1): 110-134, DOI : 10,1006 / jagm.2000.1132 , МР 1810434
- Буше, Андре; Фуке, Жан-Люк (1983), «Три типа декомпозиции un graphe en chaînes», у К. Берже, П. Камиона, Д. Брессона; Стербоул Ф. (ред.), Комбинаторная математика: Труды Международного коллоквиума по теории графов и комбинаторике (Марсель-Люмини, 1981) , Математические исследования Северной Голландии (на французском языке), 75 , Северная Голландия, стр. 131– 141, DOI : 10.1016 / S0304-0208 (08) 73380-2 , МР 0841287
- Чудновский, Мария ; Seymour, Paul (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, DOI : 10.1007 / 978-3-642-11266-9_27
- Эспере, Луи; Кардош, Франтишек; Кинг, Эндрю Д .; Кралу, Даниэль ; Норин, Сергей (2011), «Экспоненциально много точных сопоставлений в кубических графах», Успехи в математике , 227 (4): 1646–1664, arXiv : 1012.2878 , doi : 10.1016 / j.aim.2011.03.015 , MR 2799808
- Frink, Orrin (1926), "Доказательство теоремы Петерсена", Annals математики , второй серии, 27 (4): 491-493, DOI : 10,2307 / 1967699
- Хэггквист, Роланд; Йоханссон, Роберт (2004), "Замечание о реберных разбиений плоских графов", Дискретная математика , 283 (1-3): 263-266, DOI : 10.1016 / j.disc.2003.11.017 , MR 2061501
- König, Dénes (1936), Theorie der endlichen und unendlichen Graphen; kombinatorische Topologie der Streckenkomplexe.
- Ловас, Ласло ; Пламмер, доктор медицины (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
- Наддеф, Д .; Pulleyblank, WR (1981), "Паросочетание в регулярных графах", дискретная математика , 34 (3): 283-291, DOI : 10.1016 / 0012-365X (81) 90006-6 , МР 0613406.
- Петерсен, Джулиус (1891), "Die Théorie дер regulären графов", Acta Mathematica , 15 : 193-220, DOI : 10.1007 / BF02392606
- Thorup, Mikkel (2000), "Почти оптимальная полностью динамическая связность графа", Proc. Тридцать второй 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 , MR 0528221