Теорема Визинга

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

Открытие

Теорема, открытая советским математиком Вадимом Г. Визингом, была опубликована в 1964 году, когда Визинг работал в Новосибирске , и стала известна как теорема Визинга. Индийский математик Р.П. Гупта независимо открыл теорему, работая над докторской диссертацией (1965-1967).

Примеры

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

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

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

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

Пусть G = ( V , E ) — простой неориентированный граф. Мы действуем индукцией по m , количеству ребер. Если граф пуст, теорема тривиально верна. Пусть m > 0 и предположим, что правильная (Δ+1) -раскраска ребер существует для всех G − xy , где xy ∈ E .

Мы говорим, что цвет α ∈ {1,...,Δ+1 } отсутствует в x ∈ V относительно правильной (Δ+1) -раскраски ребер c, если c ( xy ) ≠ α для всех y ∈ N( х ) . Также пусть α/β -путь из x обозначает единственный максимальный путь, начинающийся в x с ребра цвета α и чередующего цвета ребер (второе ребро имеет цвет β , третье ребро имеет цвет α и т. д.), его длину может быть 0 . Обратите внимание, что если c — правильная (Δ+1) -раскраска ребер G , то каждая вершина имеет недостающий цвет по отношению к c .

Предположим, что не правильной (∆+1) -раскраски ребер G. существует Это эквивалентно следующему утверждению:

(1) Пусть xy ∈ E и c — произвольная собственная (Δ+1) -раскраска ребер G − xy , причем α отсутствует в x и β отсутствует в y относительно c . Тогда α/β -путь из y заканчивается в x .

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

Пусть теперь xy ₀ ∈ E и c ₀ — собственная (Δ+1) -раскраска ребер G − xy ₀ и α отсутствует в x относительно c ₀ . Мы определяем y ₀ ,..., y _k как максимальную последовательность соседей x такую, что c ₀ ( xy _i ) отсутствует в y _{i −1} относительно c ₀ для всех 0 < i ≤ k .

Определим раскраски c ₁ ,..., c _k как

c _я ( xy _j ) = c ₀ ( xy _{j +1} ) для всех 0 ≤ j < i ,

c _i ( xy _i ) не определено,

c _я ( е ) = c ₀ ( е ) в противном случае.

Тогда c _i является собственной (Δ+1) -раскраской ребер G − xy _i в силу определения y ₀ ,..., y _k . Также обратите внимание, что недостающие цвета в x одинаковы по отношению к c _i для всех 0 ≤ i ≤ k .

Пусть β — цвет, отсутствующий в y _k по отношению к c ₀ , тогда β также отсутствует в y _k по отношению к c _i для всех 0 ⩽ i ⩽ k . что β не может отсутствовать в x , иначе мы могли бы легко расширить , _{Обратите внимание ,} поэтому ребро цвета β инцидентно x для всех cj _ck . Из максимальности k существует 1 ⩽ i < k такое, что c ₀ ( xy _i ) = β . Из определения c ₁ ,..., c _k справедливо:

c ₀ ( xy _я ) знак равно c _{я -1} ( xy _я ) знак равно c _k ( xy _{я -1} ) знак равно β

Пусть P — α/β из yk _ck относительно путь _- . Из (1) P должно заканчиваться на x . Но α отсутствует в x , поэтому оно должно заканчиваться ребром цвета β . Следовательно, последнее ребро P — это y _{i −1} x . Теперь пусть P' — α/β -путь от y _{i −1} относительно c _{i −1} . Поскольку P' определяется однозначно и внутренние ребра не изменяются в c0 _P ,..., ck _P , путь P' использует те же ребра, что и , в обратном порядке и yk _{посещает} . Ребро, ведущее к y _k, очевидно, имеет цвет α . Но β отсутствует в , _yk поэтому P' заканчивается в _. yk Что противоречит пункту (1) выше.

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

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

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

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

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

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

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

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

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

Алгоритмы

Основная статья: Алгоритм окраски ребер Мисры и Гриса

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

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

• псевдолес P Если построенный таким образом содержит путь от v до вершины w , не имеющий исходящих ребер в P , то существует цвет c , доступный как в u, так и в w . Перекрашивание ребра uw в цвет c позволяет сдвинуть оставшиеся цвета ребер на один шаг по этому пути: для каждой вершины p в пути ребро вверх принимает цвет, который ранее использовался преемником p в пути. Это приводит к новой окраске, которая включает в себя Edge UV .
• Если, с другой стороны, путь, начинающийся из v в псевдолесе P , ведет к циклу, пусть w будет соседом u , в котором путь присоединяется к циклу, пусть c будет цветом ребра uw и пусть d будет a цвет, который не используется ни одним из ребер в вершине u . Тогда замена цветов c и d в цепочке Кемпе либо разрывает цикл, либо ребро, на котором путь присоединяется к циклу, что приводит к предыдущему случаю.

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

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

История

И в Gutin & Toft (2000) , и в Soifer (2008) Визинг упоминает, что его работа была мотивирована теоремой Шеннона (1949), показывающей, что мультиграфы можно раскрасить не более чем (3/2)Δ цветами. Хотя теорема Визинга сейчас является стандартным материалом во многих учебниках по теории графов, у Визинга изначально возникли проблемы с публикацией результата, и его статья по ней появилась в малоизвестном журнале Discret. Анализ .

См. также

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

Ссылки

• Аппель, К .; Хакен, В. (1976), «Каждая плоская карта раскрашивается в четыре цвета», Бюллетень Американского математического общества , 82 (5): 711–712, doi : 10.1090/S0002-9904-1976-14122-5 , MR   0424602 .
• Дистель, Рейнхард (2000), Теория графов (PDF) , Берлин, Нью-Йорк: Springer-Verlag, стр. 103–104 .
• Эрдеш, Пол ; Уилсон, Робин Дж. (1977), «Примечание о хроматическом индексе почти всех графов» (PDF) , Журнал комбинаторной теории , серия B, 23 (2–3): 255–257, doi : 10.1016/0095-8956 (77)90039-9 .
• Фурнье, Жан-Клод (1973), «Раскраски ребер графа», Cahiers du Centre d'Etudes de Recherche Opérationnelle , 15 : 311–314, MR   0349458 .
• Фриз, Алан М .; Джексон, Б.; МакДиармид, CJH; Рид, Б. (1988), «Случайные графы с раскраской ребер», Журнал комбинаторной теории , серия B, 45 (2): 135–149, doi : 10.1016/0095-8956(88)90065-2 , MR   0961145 .
• Габоу, Гарольд Н .; Нисидзеки, Такао ; Карив, Одед; Левен, Дэниел; Терада, Осаму (1985), Алгоритмы раскраски ребер графов , Tech. Отчет TRECIS-8501, Университет Тохоку .
• Гутин, Григорий; Тофт, Бьярне (декабрь 2000 г.), «Интервью с Вадимом Г. Визингом» (PDF) , Информационный бюллетень Европейского математического общества , 38 : 22–23 .
• Кохол, Мартин (2009), «Многогранные вложения снарков в ориентируемые поверхности», Труды Американского математического общества , том. 137, стр. 1613–1619 .
• Кохоль, Мартин (2010), «Сложность трехгранной раскраски в классе кубических графов с многогранным вложением в ориентируемую поверхность», Discrete Applied Mathematics , 158 (16): 1856–1860, doi : 10.1016/j. плотина.2010.06.019 , МР   2679785 .
• Мисра, Дж.; Грис, Дэвид (1992), «Конструктивное доказательство теоремы Визинга», Information Processing Letters , 41 (3): 131–133, doi : 10.1016/0020-0190(92)90041-S .
• Сандерс, Дэниел П .; Чжао, Юэ (2001), «Плоские графы максимальной седьмой степени относятся к классу I», Журнал комбинаторной теории, серия B , 83 (2): 201–212, doi : 10.1006/jctb.2001.2047 .
• Шеннон, Клод Э. (1949), «Теорема о раскраске линий сети», J. Math. Физика , 28 (1–4): 148–151, doi : 10.1002/sapm1949281148 , MR   0030203 .
• Сойфер, Александр (2008), Математическая книжка-раскраска , Springer-Verlag, стр. 136–137, ISBN  978-0-387-74640-1 .
• Тейт, П.Г. (1880), «Замечания о раскрасках карт», Proc. Р. Сок. Эдинбург , 10 :729, номер номера : 10.1017/S0370164600044643 .
• Визинг, В. Г. (1964), "Об оценке хроматического класса p -графа", Дискрет. Анализ. , 3 : 25–30, МР   0180505 .
• Визинг, В.Г. (1965), "Критические графы с заданным хроматическим классом", Методы дискретности. Анализ. , 5 : 9–17 . (На русском языке.)
• Чжан, Лимин (2000), «Каждый плоский граф с максимальной степенью 7 относится к классу 1», Graphs and Combinatorics , 16 (4): 467–495, doi : 10.1007/s003730070009 , S2CID   10945647 .

Внешние ссылки

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