Теорема Петерсенса - Petersens theorem

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

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

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

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

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

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

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

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

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

куда $E я$ это множество ребер $грамм я$ с обеими вершинами в $V я$ . С

{ Displaystyle сумма nolimits _ {v in V_ {i}} deg _ {G} (v) = 3 | V_ {i} |}

нечетное число и $2| E я |$ четное число, отсюда следует, что $м я$ должно быть нечетным числом. Более того, поскольку $грамм$ без моста у нас есть это $м я \geq 3$ .

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

{ displaystyle | U | geq { frac {1} {3}} m geq | {{ text {компоненты с нечетным числом вершин}} } |,}

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

История

Теорема связана с Юлиус Петерсен, датский математик. Это можно считать одним из первых результатов в теория графов. Теорема впервые появляется в статье 1891 года "Графы Die Theorie der Regären".^[1] По сегодняшним меркам доказательство теоремы Петерсеном сложно. Ряд упрощений доказательства завершился доказательством Фринк (1926) и Кениг (1936).

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

Приложения

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

Расширения

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

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

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

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

Уровнем выше

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

Примечания

^ ^а ^б Петерсен (1891).
^ См. Например Буше и Фуке (1983).
^ Хэггквист и Йоханссон (2004).
^ Минакшисундарам и Эппштейн (2004).
^ Ловас, Ласло; Пламмер, М. (1986), Теория соответствия, Анналы дискретной математики, 29, Северная Голландия, ISBN 0-444-87916-1, МИСТЕР 0859549.
^ Фринк (1926).
^ Thorup (2000).
^ Наддеф и Pulleyblank (1981), Теорема 4, с. 285.

Рекомендации

Бидль, Тереза К.; Бозе, Просенджит; Демейн, Эрик Д.; Любив, Анна (2001), «Эффективные алгоритмы теоремы Петерсена о согласовании», Журнал алгоритмов, 38 (1): 110–134, Дои:10.1006 / jagm.2000.1132, МИСТЕР 1810434
Буше, Андре; Фуке, Жан-Люк (1983), «Три типа декомпозиции un graphe en chaînes», у К. Берже, П. Камиона, Д. Брессона; Стербоул, Ф. (ред.), Комбинаторная математика: материалы международного коллоквиума по теории графов и комбинаторике (Marseille-Luminy, 1981), Математические исследования Северной Голландии (на французском языке), 75, Северная Голландия, стр. 131–141, Дои:10.1016 / S0304-0208 (08) 73380-2, МИСТЕР 0841287
Чудновский, Мария; Сеймур, Пол (2012), «Совершенные паросочетания в плоских кубических графах», Комбинаторика, 32 (4): 403–424, Дои:10.1007 / s00493-012-2660-9, МИСТЕР 2965284
Дикс, Кшиштоф; Станчик, Петр (2010), "Идеальное соответствие для двусвязных кубических графов в $O (п бревно 2 п)$ время в ван Леувен, Ян; Мушолл, Анка; Пелег, Давид; Покорный, Ярослав; Румпе, Бернхард (ред.), SOFSEM 2010: 36-я конференция «Современные тенденции в теории и практике информатики», Шпиндлерув Млин, Чешская Республика, 23–29 января 2010 г., Труды, Конспект лекций по информатике, 5901, Springer, стр. 321–333, Дои:10.1007/978-3-642-11266-9_27
Эспере, Луи; Кардош, Франтишек; Кинг, Эндрю Д .; Кралу, Даниэль; Норин, Сергей (2011), "Экспоненциально много совершенных паросочетаний в кубических графах", Успехи в математике, 227 (4): 1646–1664, arXiv:1012.2878, Дои:10.1016 / j.aim.2011.03.015, МИСТЕР 2799808
Фринк, Оррин (1926), «Доказательство теоремы Петерсена», Анналы математики, Вторая серия, 27 (4): 491–493, Дои:10.2307/1967699
Хэггквист, Роланд; Йоханссон, Роберт (2004), "Заметка о реберном разбиении плоских графов", Дискретная математика, 283 (1–3): 263–266, Дои:10.1016 / j.disc.2003.11.017, МИСТЕР 2061501
Кениг, Денес (1936), Theorie der endlichen und nonndlichen 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, Дои:10.1111 / j.1467-8659.2004.00768.x
Наддеф, Д .; Pulleyblank, W. R. (1981), «Сопоставления в регулярных графах», Дискретная математика, 34 (3): 283–291, Дои:10.1016 / 0012-365X (81) 90006-6, МИСТЕР 0613406.
Петерсен, Юлиус (1891), «Теория регулятивных графов», Acta Mathematica, 15: 193–220, Дои:10.1007 / BF02392606
Торуп, Миккель (2000), «Почти оптимальная полностью динамическая связность графов», Proc. 32-й симпозиум ACM по теории вычислений, стр. 343–350, Дои:10.1145/335305.335345, ISBN 1-58113-184-4, МИСТЕР 2114549
Вурхув, Марк (1979), "Нижняя оценка перманентов некоторых (0,1) -матриц", Indagationes Mathematicae, 82 (1): 83–86, Дои:10.1016 / 1385-7258 (79) 90012-Х, МИСТЕР 0528221

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

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

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

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

[5] Ловас, Ласло; Пламмер, М. (1986), Теория соответствия, Анналы дискретной математики, 29, Северная Голландия, ISBN 0-444-87916-1, МИСТЕР 0859549.

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

[FOOTNOTEThorup2000-7] Thorup (2000).

[8] Наддеф и Pulleyblank (1981), Теорема 4, с. 285.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]