Меню Главная Случайная статья Настройки Теорема Петерсена Материал из https://ru.wikipedia.org Теорема Петерсена — одна из самых ранних теорем теории графов, названная в честь Юлиуса Петерсена. Утверждение теоремы может быть сформулировано следующим образом: Теорема Петерсена. Любой кубический двусвязный граф содержит в себе совершенное паросочетание[1]. Другими словами, если из каждой вершины графа выходит ровно три ребра (граф является 3-регулярным) и каждое ребро принадлежит циклу, то в графе есть множество рёбер, касающихся каждой вершины графа ровно один раз. Содержание 1 Доказательство 2 История 3 Применение 4 Расширения теоремы 4.1 Количество совершенных паросочетаний в кубических двусвязных графах 4.2 Алгоритмические версии 4.3 Повышение степени 5 Источники 6 Ссылки Доказательство Нужно показать, что для каждого кубического двусвязного графа ${\displaystyle G=(V,E)}$ справедливо, что для каждого набора ${\displaystyle U\subseteq V}$ количество нечётных компонент связности в подграфе ${\displaystyle G\backslash U}$ не превышает мощности ${\displaystyle U}$. Тогда по теореме Татта ${\displaystyle G}$ содержит совершенное паросочетание. Пусть ${\displaystyle G_{i}}$ — компонента с нечётным числом вершин в подграфе ${\displaystyle G\backslash U}$. Пусть ${\displaystyle V_{i}}$ обозначает вершины ${\displaystyle G_{i}}$, а ${\displaystyle m_{i}}$ обозначает количество ребер ${\displaystyle G}$ с одной вершиной в ${\displaystyle V_{i}}$ и одной вершиной в ${\displaystyle U}$. Подсчётом двумя способами получаем следующее: ${\displaystyle \sum \nolimits _{v\in V_{i}}\deg _{G}(v)=2|E_{i}|+m_{i},}$ где ${\displaystyle E_{i}}$ — это множество рёбер ${\displaystyle G_{i}}$ с обеими вершинами в ${\displaystyle V_{i}}$. Поскольку ${\displaystyle \sum \nolimits _{v\in V_{i}}\deg _{G}(v)=3|V_{i}|}$ нечётно, а ${\displaystyle 2|E_{i}|}$ — чётно, получаем, что ${\displaystyle m_{i}}$ должно быть нечётным. Более того, ${\displaystyle m_{i}\geq 3}$, так как ${\displaystyle G}$ — двусвязный граф. Пусть ${\displaystyle m}$ — количество рёбер графа ${\displaystyle G}$, соединяющих вершины ${\displaystyle U}$ с вершинами графа ${\displaystyle G\backslash U}$. Каждая компонента с нечётным числом вершин добавляет в ${\displaystyle m}$ минимум 3 уникальных ребра, поэтому количество таких компонент не превышает ${\displaystyle m/3}$. В худшем случае каждое ребро с одной из вершин в ${\displaystyle U}$ будет учитываться при подсчёте ${\displaystyle m}$, а поэтому ${\displaystyle m\leq 3|U|}$. Получается, что ${\displaystyle |U|\geq {\frac {1}{3}}m\geq |odd(G\backslash U)|}$ Условие теоремы Татта выполняется. Следовательно, в ${\displaystyle G}$ существует совершенное паросочетание История Теорема была названа в честь датского математика Юлиуса Петерсена. Считается одной из первых теорем теории графов. Впервые теорема появилась в статье 1891 года «Die Theorie der regulren graphs»[1]. Доказательство теоремы, представленное Петерсеном, считается сложным по сегодняшним стандартам. Серия упрощений доказательства представлена в доказательствах Фринка (Frink (1926)) и Кёнига (Knig (1936)). В современных учебниках теорема Петерсена рассматривается как приложение теоремы Татта. Применение В кубическом графе с совершенным паросочетанием рёбра, не входящие в это паросочетание, формируют 2-фактор. Ориентируя 2-фактор, рёбра совершенного паросочетания можно расширить до путей длины три, скажем, взяв рёбра, ориентированные наружу. Это показывает, что каждый кубический двусвязный граф раскладывается на непересекающиеся по рёбрам пути длины три[2]. Теорема Петерсена может быть также применена для того, чтобы показать, что каждый максимальный планарный граф может быть разложен на множество непересекающихся по рёбрам путей длины три. В этом случае двойственный граф будет кубическим и двусвязным, поэтому согласно теореме Петерсена он имеет паросочетание, которое соответствует в исходном графе паре соседних треугольных граней. Каждая пара треугольников даёт путь длины три, включающий ребро, соединяющее треугольники вместе с двумя из четырёх оставшихся рёбер треугольника[3]. Применяя теорему Петерсена к двойственному графу треугольной сетки и соединяя пары несовпадающих треугольников, можно разложить сетку на циклические полосы треугольников[англ.]. С помощью некоторых дальнейших преобразований его можно превратить в единую полосу — получается метод преобразования треугольной сетки таким образом, что её двойственный граф становится гамильтоновым[4]. Расширения теоремы Количество совершенных паросочетаний в кубических двусвязных графах Ловас и Пламмер[англ.] предположили, что количество совершенных паросочетаний, содержащихся в кубическом двусвязном графе, экспоненциально зависит от числа вершин графа ${\displaystyle n}$[5]. Гипотеза была впервые доказана для двудольных кубических двусвязных графов Voorhoeve (1979), а затем для планарных кубических двусвязных доказательство представили Чудновская & Сеймур (2012). Общий случай был решен в Esperet et al. (2011), где было показано, что каждый кубический двусвязный граф содержит как минимум ${\displaystyle 2^{n/3656}}$ совершенных паросочетаний. Алгоритмические версии Biedl et al. (2001) обсудили эффективные версии теоремы Петерсена. Основываясь на доказательстве Фринка[6], они получили алгоритм сложности ${\displaystyle O(n\log ^{4}(n))}$ для вычисления совершенного паросочетания в кубическом двусвязном графе с ${\displaystyle n}$ вершинами. Если граф, кроме того, планарный, в той же статье даётся алгоритм сложности ${\displaystyle O(n)}$. Их ограничение по времени ${\displaystyle O(n\log ^{4}(n))}$ может быть улучшено на основе последующих улучшений времени для поддержания множества мостов в динамическом графе[7]. Дальнейшие улучшения, сокращающие время до ${\displaystyle O(n\log ^{2}(n))}$ или (с дополнительными случайными структурами данных) ${\displaystyle O(n\log(n)\log ^{3}(\log(n)))}$, были предложены Diks & Stanczyk (2010). Повышение степени Если ${\displaystyle G}$ — регулярный граф степени ${\displaystyle d}$, рёберная связность которого не меньше ${\displaystyle d-1}$, и ${\displaystyle G}$ имеет чётное число вершин, то он имеет совершенное паросочетание. Верно даже более сильное условие: каждое ребро графа ${\displaystyle G}$ принадлежит хотя бы одному совершенному паросочетанию. Когда степень ${\displaystyle d}$ нечётна, условие на количество вершин можно опустить, так как в этом случае по лемме о рукопожатиях количество вершин всегда чётно[8]. Источники 1 2 Petersen (1891). See for example Bouchet & Fouquet (1983). Hggkvist & Johansson (2004). Meenakshisundaram, Eppstein, 2004. Lovsz, Plummer, 1986. Frink (1926). Thorup, 2000. Naddef & Pulleyblank (1981), Theorem 4, p. 285. Ссылки Biedl, Therese C.; Bose, Prosenjit; Demaine, Erik D.; Lubiw, Anna (2001), Efficient algorithms for Petersen's matching theorem, Journal of Algorithms, 38 (1): 110–134, doi:10.1006/jagm.2000.1132, MR 1810434