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

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

Открытие

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

Примеры

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

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

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

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

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

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

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

(1) Пусть

xy \in E

c

— произвольная правильная

(Δ+1)

-раскраска ребер графа

G - xy

α

отсутствует в

x

, а

β

отсутствует в

y

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

c

. Тогда

α/β

-путь из

y

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

x

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

Теперь пусть $xy 0 \in E$ и $c 0$ является собственной $(Δ+1)$ -раскраской ребер $G - xy 0$ и $α$ отсутствует в $x$ относительно $c 0$ . Определим $y 0,..., y k$ как максимальную последовательность соседей $x$ такую, что $c 0 (xy i)$ отсутствует в $y i -1$ относительно $c 0$ для всех $0 < i \leq k$ .

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

c i (xy j)= c 0 (xy j +1)

для всех

0 \leq j < i

c i (xy i)

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

c i (e)= c 0 (e)

в противном случае.

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

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

c 0 (xy i) = c i -1 (xy i) = c k (xy i -1) = β

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

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

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

Erdős & Wilson (1977) показали, что почти все графы относятся к классу один. То есть, в модели случайных графов Erdős–Rényi , в которой все $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-полной задачей является определение того, принадлежит ли полиэдрально вложенный граф классу один. ^[6]

Алгоритмы

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

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

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

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

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

История

В работах Gutin & Toft (2000) и Soifer (2008) Визинг упоминает, что его работа была мотивирована теоремой Шеннона (1949), показывающей, что мультиграфы могут быть раскрашены максимум в $(3/2)Δ$ цветов. Хотя теорема Визинга теперь является стандартным материалом во многих учебниках по теории графов, у Визинга изначально были проблемы с публикацией результата, и его статья об этом появилась в малоизвестном журнале Diskret. Analiz . ^[7]

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

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

Примечания

^ Берж, Клод; Фурнье, Жан Клод (1991). «Краткое доказательство обобщения теоремы Визинга». Журнал теории графов . 15 (3). Онлайн-библиотека Wiley: 333–336. doi :10.1002/jgt.3190150309.
^ Визинг (1965)
^ Штибиц, Михаэль; Шайде, Диего; Тофт, Бьярне; Фаврхольдт, Лене М. (2012). Раскраска ребер графа: теорема Визинга и гипотеза Голдберга. Ряды Уайли в дискретной математике и оптимизации. John Wiley & Sons, Inc., Хобокен, Нью-Джерси. стр. xii. ISBN 978-1-118-09137-1. МР 2975974.
^ Тофт, Б.; Уилсон, Р. (11 марта 2021 г.). «Краткая история раскраски рёбер – с личными воспоминаниями». Discrete Mathematics Letters . 6 : 38–46. doi : 10.47443/dml.2021.s105 .
^ Фурнье (1973).
^ Кохоль (2010).
↑ Полное название журнала — Академия наук СССР. Сибирское Отделение. Институт Математики. Дискретный анализ. Сборник Трудова . В 1980 году он был переименован в «Методы дискретного анализа» (название дано ему в Gutin & Toft (2000)) и прекращено в 1991 году [1].

Ссылки

Аппель, К.; Хакен , В. (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.
Фриз, Алан М.; Джексон, Б.; МакДиармид, К. Дж. Х.; Рид, Б. (1988), «Случайные графы с раскраской рёбер», Журнал комбинаторной теории , Серия B, 45 (2): 135–149, doi :10.1016/0095-8956(88)90065-2, MR 0961145.
Габов, Гарольд Н.; Нишизеки , Такао ; Карив, Одед; Левен, Дэниел; Терада, Осаму (1985), Алгоритмы для раскраски ребер графов , Технический отчет TRECIS-8501, Университет Тохоку.
Гутин, Грегори; Тофт, Бьярне (декабрь 2000 г.), «Интервью с Вадимом Г. Визингом» (PDF) , Информационный бюллетень Европейского математического общества , 38 : 22–23.
Кохоль, Мартин (2009), «Многогранные вложения снарков в ориентируемые поверхности», Труды Американского математического общества , т. 137, стр. 1613–1619.
Кохоль, Мартин (2010), «Сложность 3-рёберной раскраски в классе кубических графов с многогранным вложением в ориентируемую поверхность», Дискретная прикладная математика , 158 (16): 1856–1860, doi : 10.1016/j.dam.2010.06.019 , MR 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. Physics , 28 (1–4): 148–151, doi :10.1002/sapm1949281148, MR 0030203.
Сойфер, Александр (2008), Математическая раскраска , Springer-Verlag, стр. 136–137, ISBN 978-0-387-74640-1.
Тейт, ПГ (1880), "Замечания о раскраске карт", Proc. R. Soc. Эдинбург , 10 : 729, doi :10.1017/S0370164600044643.
Визинг, В.Г. (1964), "Об оценке хроматического класса p -графа", Дискретный анализ , 3 : 25–30, MR 0180505.
Визинг, В.Г. (1965), «Критические графы с заданным хроматическим классом», Методы дискретного анализа , 5 : 9–17. (На русском языке.)
Чжан, Лиминь (2000), «Каждый планарный граф с максимальной степенью 7 имеет класс 1», Графы и комбинаторика , 16 (4): 467–495, doi :10.1007/s003730070009, S2CID 10945647.

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

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