Теорема Визингса - Vizings theorem

В теория графов, Теорема Визинга заявляет, что каждый простой неориентированный граф может быть край окрашен используя количество цветов, которое не более чем на один больше максимального степень $Δ$ графика. По крайней мере $Δ$ цвета всегда необходимы, поэтому неориентированные графы можно разделить на два класса: графы «первого класса», для которых $Δ$ цветов достаточно, и графы "второго класса", для которых $Δ + 1$ цвета необходимы. Более обобщенная версия теоремы Визинга утверждает, что каждый неориентированный мультиграф без петель можно раскрасить не более $Δ + µ$ цвета, где $µ$ это множественность мультиграфа. Теорема названа в честь Вадим Геннадьевич Визинг который опубликовал его в 1964 году.

Примеры

Когда $Δ = 1$ , график $грамм$ сам должен быть совпадением, без двух смежных краев, а его хроматическое число края равно единице. То есть все графики с $Δ (грамм) = 1$ относятся к первому классу.

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

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

Это доказательство вдохновлено Дистель (2000).

Позволять $грамм = (V, E)$ - простой неориентированный граф. Продолжим индукцию по $м$ , количество ребер. Если граф пуст, теорема тривиально верна. Позволять $м > 0$ и предположим правильный $(Δ + 1)$ -кратная раскраска существует для всех $грамм - ху$ куда $ху \in E$ .

Мы говорим этот цвет $α \in {1, ..., Δ + 1$ } отсутствует в $Икс \in V$ в отношении собственно $(Δ + 1)$ -кратная окраска $c$ если $c (ху) \neq α$ для всех $у \in N (Икс)$ . Кроме того, пусть $α / β$ -путь от $Икс$ обозначим единственный максимальный путь, начинающийся в $Икс$ с $α$ -цветная кромка и чередование цветов кромок (вторая кромка имеет цвет $β$ , третье ребро имеет цвет $α$ и так далее), его длина может быть $0$ . Обратите внимание, что если $c$ это правильный $(Δ + 1)$ -кратная окраска $грамм$ то в каждой вершине отсутствует цвет по отношению к $c$ .

Предположим, что нет собственно $(Δ + 1)$ -кратная окраска $грамм$ существуют. Это эквивалентно этому утверждению:

(1) Пусть

ху \in E

и

c

быть произвольным

(Δ + 1)

-кратная окраска

грамм - ху

и

α

быть пропавшим без вести

Икс

и

β

быть пропавшим без вести

у

относительно

c

. Тогда

α / β

-путь от

у

заканчивается в

Икс

.

Это эквивалентно, потому что, если (1) не выполняется, мы можем поменять цвета местами $α$ и $β$ на $α / β$ -path и установите цвет $ху$ быть $α$ , создавая надлежащий $(Δ + 1)$ -кратная окраска $грамм$ из $c$ . Наоборот, если правильно $(Δ + 1)$ -рёбер-раскраска существует, тогда мы можем удалить ребро, ограничить раскраску, и (1) тоже не будет выполняться.

Теперь позвольте $ху 0 \in E$ и $c 0$ быть правильным $(Δ + 1)$ -кратная окраска $грамм - ху 0$ и $α$ отсутствовать в $Икс$ относительно $c 0$ . Мы определяем $у 0,..., у k$ быть максимальной последовательностью соседей $Икс$ такой, что $c 0 (ху я)$ отсутствует в $у я -1$ относительно $c 0$ для всех $0 < я \leq k$ .

Определим раскраску $c 1,..., c k$ в качестве

c я (ху j)= c 0 (ху j +1)

для всех

0 \leq j < я

,

c я (ху я)

не определено,

c я (е)= c 0 (е)

иначе.

потом $c я$ это правильный $(Δ + 1)$ -кратная окраска $грамм - ху я$ из-за определения $у 0,..., у k$ . Также обратите внимание, что отсутствующие цвета в $Икс$ такие же в отношении $c я$ для всех $0 \leq я \leq k$ .

Позволять $β$ быть цветом, отсутствующим в $у k$ относительно $c 0$ , тогда $β$ также отсутствует в $у k$ относительно $c я$ для всех $0 \leq я \leq k$ . Обратите внимание, что $β$ не может отсутствовать в $Икс$ , иначе мы могли бы легко расширить $c k$ , поэтому край с цветом $β$ имеет отношение к $Икс$ для всех $c j$ . Из максимума $k$ , Существует $1 \leq я < k$ такой, что $c 0 (ху я) = β$ . Из определения $c 1,..., c k$ это имеет место:

c 0 (ху я) = c я -1 (ху я) = c k (ху я -1) = β

Позволять $п$ быть $α / β$ -путь от $у k$ относительно $c k$ . С 1), $п$ должен заканчиваться $Икс$ . Но $α$ отсутствует в $Икс$ , поэтому он должен заканчиваться краем цвета $β$ . Следовательно, последний край $п$ является $у я -1 Икс$ . Теперь позвольте $П'$ быть $α / β$ -путь от $у я -1$ относительно $c я -1$ . С $П'$ однозначно определено и внутренние ребра $п$ не изменяются в $c 0,..., c k$ , тропинка $П'$ использует те же края, что и $п$ в обратном порядке и посещения $у k$ . Край, ведущий к $у k$ явно имеет цвет $α$ . Но $β$ отсутствует в $у k$ , так $П'$ заканчивается в $у k$ . Это противоречит пункту 1 выше.

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

Некоторые авторы предоставили дополнительные условия, которые классифицируют некоторые графы как относящиеся к классу 1 или классу 2, но не обеспечивают полной классификации. Например, если вершины максимальной степени $Δ$ в графике $грамм$ для мужчин независимый набор, или в более общем смысле, если индуцированный подграф для этого множества вершин лес, то $грамм$ должен быть первого класса.^[1]

Эрдеш и Уилсон (1977) показало, что почти все графики первого класса. То есть в Модель Эрдеша – Реньи случайных графов, в которых все $п$ -вершинные графы равновероятны, пусть $п (п)$ быть вероятностью того, что $п$ - граф вершин, построенный из этого распределения, имеет первый класс; тогда $п (п)$ приближается к единице в пределе, когда $п$ уходит в бесконечность. Для более точных оценок скорости, с которой $п (п)$ сходится к одному, см. Frieze et al. (1988).

Планарные графики

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

В Гипотеза Визинга о плоском графе, Визинг (1965) утверждает, что все простые плоские графы с максимальной степенью шесть или семь относятся к первому классу, закрывая остальные возможные случаи.Сандерс и Чжао (2001) частично доказал гипотезу Визинга о планарных графах, показав, что все плоские графы с максимальной степенью семь относятся к классу 1. Таким образом, единственный случай гипотезы, который остается нерешенным, - это случай максимальной степени шесть. Эта гипотеза имеет значение для Гипотеза полной окраски.

Плоские графы второго класса, построенные путем разбиения платоновых тел, не являются правильными: у них есть вершины второй степени, а также вершины более высокой степени. теорема четырех цветов (доказано Аппель и Хакен (1976) ) о раскраске вершин плоских графов, эквивалентно утверждению, что каждый 3-регулярный планарный граф без мостов имеет класс один (Tait 1880 ).

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

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

Алгоритмы

Мисра и Грис (1992) описать алгоритм полиномиального времени для окраски ребер любого графа с $Δ + 1$ цвета, где $Δ$ - максимальная степень графа. То есть алгоритм использует оптимальное количество цветов для графов класса два и использует не более одного цвета, чем необходимо для всех графов. Их алгоритм следует той же стратегии, что и первоначальное доказательство своей теоремы Визингом: он начинается с неокрашенного графа, а затем неоднократно находит способ перекрашивать граф, чтобы увеличить количество цветных ребер на единицу.

Более конкретно, предположим, что $УФ$ является неокрашенным ребром частично раскрашенного графа. Алгоритм Мисры и Гриса можно интерпретировать как построение направленного псевдолес $п$ (граф, в котором каждая вершина имеет не более одного исходящего ребра) на соседях $ты$ : для каждого соседа $п$ из $ты$ , алгоритм находит цвет $c$ который не используется ни одним из ребер, инцидентных $п$ , находит вершину $q$ (если он существует) для какого ребра $uq$ имеет цвет $c$ , и добавляет $pq$ как край к $п$ . Есть два случая:

Если псевдолесье $п$ построенный таким образом, содержит путь из $v$ к вершине $ш$ который не имеет исходящих ребер в $п$ , то есть цвет $c$ который доступен как на $ты$ и $ш$ . Перекрашивание края $уф$ с цветом $c$ позволяет сдвинуть оставшиеся цвета ребер на один шаг по этому пути: для каждой вершины $п$ в пути, край $вверх$ принимает цвет, который ранее использовался преемником $п$ в пути. Это приводит к новой окраске, включающей кромку $УФ$ .
Если же, с другой стороны, путь, начинающийся с $v$ в псевдолесе $п$ приводит к циклу, пусть $ш$ быть соседом $ты$ на котором путь входит в цикл, пусть $c$ быть цвета края $уф$ , и разреши $d$ быть цветом, который не используется ни одним из ребер в вершине $ты$ . Затем меняем цвета $c$ и $d$ на Кемпе цепь либо прерывает цикл, либо границу, на которой путь соединяется с циклом, что приводит к предыдущему случаю.

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

В неопубликованном техническом отчете Gabow et al. (1985) потребовал более быстрого ${ Displaystyle О (м { sqrt {п}} журнал п)}$ оценка времени для той же задачи раскраски с $Δ + 1$ цвета.

История

В обоих Гутин и Тофт (2000) и Сойфер (2008), Визинг упоминает, что его работа была мотивирована теоремой Шеннон (1949) показывая, что мультиграфы можно раскрасить не более чем $(3/2) Δ$ цвета. Хотя теорема Визинга теперь является стандартным материалом во многих учебниках по теории графов, сначала Визингу не удалось опубликовать результат, и его статья по ней появилась в малоизвестном журнале. Дискрет. Анализ.^[3]

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

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

Примечания

^ Фурнье (1973).
^ Кочол (2010).
^ Полное название этого журнала было Академия Наук СССР. Сибирское отделение. Institut Matematiki. Дискретный анализ. Сборник Трудов. Был переименован Методы Дискретного анализа в 1980 г. (название дано в Гутин и Тофт (2000) ) и снята с производства в 1991 г. [1].

внешняя ссылка

Доказательство теоремы Визинга в PlanetMath.

[1] Фурнье (1973).

[2] Кочол (2010).

[3] Полное название этого журнала было Академия Наук СССР. Сибирское отделение. Institut Matematiki. Дискретный анализ. Сборник Трудов. Был переименован Методы Дискретного анализа в 1980 г. (название дано в Гутин и Тофт (2000) ) и снята с производства в 1991 г. [1].

[1]

[2]

[3]