Теорема Визинга (Mykjybg Fn[nuig)

Теорема Визинга — утверждение теории графов, согласно которому рёбра любого простого неориентированного графа могут быть раскрашены в число цветов, максимум на единицу большее максимальной степени вершин $\Delta$ графа. Поскольку $\Delta +1$ цветов достаточно всегда, все неориентированные графы можно разбить на два класса — графы «первого класса», для которых $\Delta$ цветов достаточно, и «второго класса», для которых необходимо $\Delta +1$ цветов.

Результат установлен Вадимом Визингом в 1964 году.

Примеры

Если $\Delta =1$, в графе $G$ нет смежных рёбер, и рёбра можно раскрасить в один цвет. Таким образом, все графы с $\Delta (G)=1$ принадлежит первому классу.

Если $\Delta =2$, граф $G$ должен быть дизъюнктным объединением путей и циклов. Если все циклы чётны, их рёбра можно раскрасить в два цвета, меняя поочерёдно цвета, проходя вдоль каждого цикла. Однако, если существует хотя бы один нечётный цикл, его рёбра нельзя выкрасить в 2 цвета. Таким образом, граф с $\Delta =2$ принадлежит первому классу тогда и только тогда, когда он является двудольным.

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

Классификация графов

Некоторые авторы дали дополнительные условия для принадлежности некоторых графов первому или второму классу, но полной классификации нет. Например, если вершины максимальной степени $\Delta$ в графе $G$ образуют независимое множество, или, более общее условие, если порождённый подграф для этого множества вершин является лесом, то $G$ будет принадлежать первому классу.

Эрдёш и Уилсон показали, что почти все графы принадлежат первому классу. Так, в модели случайных графов Эрдёша — Реньи, в которой все графы с $n$ вершинами равновероятны, пусть $p(n)$ обозначает вероятность того, что граф с $n$ вершинами принадлежит первому классу. Тогда $p(n)$ стремится к единице при стремлении $n$ к бесконечности. Позднее разработаны более тонкие оценки скорости стремления $p(n)$ к единице.

Плоские графы

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

Гипотеза Визинга о планарных графах утверждает, что все простые планарные графы с максимальной степенью шесть и семь принадлежат первому классу, что закрывает оставшиеся возможности. В 2001 году установлено, что все планарные графы с максимальной степенью семь принадлежат первому классу. Таким образом, остаётся под вопросом только случай с максимальной степенью шесть. Эта гипотеза даёт предпосылки для гипотезы о тотальной раскраске.

Планарные графы второго класса, построенные из правильных многогранников путём разбиения рёбер, не являются регулярными — у них есть как вершины второго порядка, так и вершины больших порядков. Теорема о четырёх красках о раскраске вершин планарного графа эквивалентна утверждению, что любой 3-регулярный граф без мостов принадлежит первому классу (это утверждение верно в виду доказанности теоремы о четырёх красках).

Графы на поверхностях, отличных от плоскости

В 1969 году Бранко Грюнбаум высказал гипотезу, что любой 3-регулярный граф, у которого существует вложение в виде многогранника в любое двумерное ориентированное многообразие, такое как тор, должен принадлежать первому классу. В этом контексте вложение в виде многогранника означает вложение графа, при котором любая полученная грань графа топологически эквивалентна диску, и при котором двойственный граф является простым, без петель или многократной смежности. Если бы это было верно, это было бы обобщением теоремы о четырёх красках, которая, как показал Тейт, эквивалентна утверждению, что любой 3-регулярный граф, для которого существует вложение в виде многогранника в сферу, принадлежит первому классу. Однако в 2009 году показано, что гипотеза не верна, найдя снарки, которые имеет вложение в виде многогранников в ориентированные поверхности, имеющие высокий род. Основываясь на этом построении, он также показал, что определение, принадлежит ли граф с вложением в виде многогранника первому классу, является NP-полной задачей.

Алгоритмы

В 1992 году описан алгоритм полиномиального времени раскраски любого графа с помощью $\Delta +1$ цветов, где $\Delta$ — максимальная степень графа. Таким образом, алгоритм использует оптимальное число цветов для графов второго класса, и использует максимум один лишний цвет для всех графов. Алгоритм использует ту же стратегию, что и изначальное доказательство теоремы Визинга — алгоритм начинает с графа без красок и последовательно ищет пути раскраски, так, чтобы вовлечь в раскраску ещё одно ребро.

В описании алгоритма используются термины «веер», «вращение веера» и «$cd$-путь», введённые авторами алгоритма, а также следующее соглашение: цвет $d$ свободен в вершине $w$, если нет рёбер, выкрашенных в цвет $d$, инцидентных вершине $w$. Алгоритм выполняет следующие шаги:

• Для каждого неокрашенного ребра $uv$ в частично раскрашенном графе строится последовательность $\left\langle v,...,l\right\rangle$ — максимальный веер.
  • Для каждой пары цветов $c,d$, где $c$ — цвет, свободный в вершине $u$, а $d$ — цвет, свободный в $l$ обращаются цвета $cd$-пути.
  • Выбирается вершина $w$ так, что $\left\langle v,...,w\right\rangle$ является подцепочкой $\left\langle v,...,l\right\rangle$ и $d$ не используется в $w$.
  • Веер $\left\langle v,...,w\right\rangle$ «вращается», $uw$ раскрашивается в цвет $d$.

Веер — это последовательность вершин $\left\langle v_{0},...,v_{r}\right\rangle$ со следующими свойствами:

• все вершины являются соседями вершины $u$ и $v_{0}=v$
• ребро $u\,v_{k+1}$ выкрашено в цвет $d_{k}$, который не использовался в вершинах $\left\langle v_{0},\ldots ,v_{k}\right\rangle$

Веер можно вращать, то есть заменить цвета рёбер $uv_{k}$ на цвета рёбер $uv_{k+1}$, и эта перестановка цветов не нарушает раскраски графа.

$cd$-путь — это максимальная последовательность рёбер, начинающаяся в $u$, и каждое ребро выкрашено в $c$ или $d$. Обращение цветов этой цепочки означает замену $c$ на $d$ и $d$ на $c$.

Все используемые в алгоритме операции не разрушают раскраску графа, а после обращения цветов $cd$-пути описанная в алгоритме подцепочка существует.

Используя простую структуру данных для хранения цветов, использованных в вершине, весь шаг алгоритма можно выполнить за время $O(n)$, где $n$ — число вершин графа. Поскольку каждый шаг нужно повторить для всех $m$ дуг, общее время будет $O(mn)$.

В неопубликованной работе 1985 года утверждалось, что можно найти раскраску за время $O(m{\sqrt {n}}\log n)$.

История

Считается, что работа Визинга была навеяна теоремой Шеннона, которая показывает, что мультиграфы можно раскрасить с использованием не более ${\tfrac {3}{2}}\Delta$ цветов. Также существует мнение, что у Визинга были проблемы с публикацией результата (впервые опубликован в журнале «Дискретный анализ», выпускавшимся до 1991 года Институтом математики Сибирского отделения АН СССР, который западными авторами называется «малоизвестным»).

См. также

• Теорема Брукса, связывающая раскраску вершин с максимальной степенью.

Литература

• K. Appel, W. Haken. Every planar map is four colorable // Bulletin of the American Mathematical Society. — 1976. — Т. 82, вып. 5. — С. 711–712. — doi:10.1090/S0002-9904-1976-14122-5.
• Paul Erdős, Robin J. Wilson. Note on the chromatic index of almost all graphs // Journal of Combinatorial Theory. — 1977. — Т. 23, вып. 2–3. — С. 255–257. — doi:10.1016/0095-8956(77)90039-9.
• Jean-Claude Fournier. Colorations des arêtes d’un graphe // Cahiers du Centre d’Études de Recherche Opérationnelle. — 1973. — Т. 15. — С. 311–314.
• Alan M. Frieze, B. Jackson, C. J. H. McDiarmid, B. Reed. Edge-colouring random graphs // Journal of Combinatorial Theory. — 1988. — Т. 45, вып. 2. — С. 135–149. — doi:10.1016/0095-8956(88)90065-2.
• Harold N. Gabow, Takao Nishizeki, Oded Kariv, Daniel Leven, Osamu Terada. Algorithms for edge-coloring graphs. — Tohoku University, 1985. — (Tech. Report TRECIS-8501).
• Gregory Gutin, Bjarne Toft. Interview with Vadim G. Vizing // European Mathematical Society Newsletter. — 2000. — Т. 38, вып. December. — P. 22–23.
• Martin Kochol. Proceedings of the American Mathematical Society. — 2009. — Т. 137. — С. 1613–1619.
• Martin Kochol. Complexity of 3-edge-coloring in the class of cubic graphs with a polyhedral embedding in an orientable surface // Discrete Applied Mathematics. — 2010. — Т. 158, вып. 16. — С. 1856–1860. — doi:10.1016/j.dam.2010.06.019.
• A constructive proof of Vizing's Theorem // Information Processing Letters. — 1992. — Т. 41, вып. 3. — С. 131–133. — doi:10.1016/0020-0190(92)90041-S.
• Daniel P. Sanders, Yue Zhao. Planar graphs of maximum degree seven are class I // Journal of Combinatorial Theory. — 2001. — Т. 83, вып. 2. — С. 201–212. — doi:10.1006/jctb.2001.2047.
• Claude Shannon. A theorem on coloring the lines of a network // J. Math. Physics. — 1949. — Т. 28. — С. 148–151.
• Alexander Soifer. The Mathematical Coloring Book. — 2008. — С. 136–137. — ISBN 978-0-387-74640-1.
• P. G. Tait. Remarks on the colourings of maps // Proc. R. Soc. Edinburgh. — 1880. — Т. 10. — С. 729.
• В. Г. Визинг. Об оценке хроматического класса р-графа // сб. Дискретный анализ. — Новосибирск: Институт математики СО АН СССР, 1964. — Вып. 3. — С. 25–30.
• В. Г. Визинг. Критические графы с данным хроматическим классом // сб . Дискретный анализ. — Новосибирск: Институт математики СО АН СССР, 1965. — Вып. 5. — С. 9–17.

Ссылки

• Proof of Vizing’s theorem at PlanetMath.