В теории графов , Теорема Визинга гласит , что каждый простой неориентированный граф может быть край цветные с использованием ряда цветов, которое в большинстве один больше , чем максимальная степень А графа. Всегда необходимы как минимум Δ цветов, поэтому неориентированные графы можно разделить на два класса: графы «первого класса», для которых достаточно Δ цветов, и графы «второго класса», для которых необходимо Δ + 1 цвета. Более общая версия теоремы Визинга утверждает, что любой неориентированный мультиграф без петель можно раскрасить не более чем в ∆ + µ цветов, где µ- кратность мультиграфа. Теорема названа в честь Вадима Г. Визинга , опубликовавшего ее в 1964 году.
Примеры
Когда Δ = 1 , граф G сам должен быть паросочетанием, без двух смежных ребер, и его хроматическое число ребер равно единице. То есть все графы с Δ ( G ) = 1 относятся к первому классу.
При Δ = 2 , то граф G должен быть несвязным объединением из путей и циклов . Если все циклы четные, они могут быть окрашены в 2 края, чередуя два цвета вокруг каждого цикла. Однако если существует хотя бы один нечетный цикл, то двухреберная раскраска невозможна. То есть граф с Δ = 2 относится к первому классу тогда и только тогда, когда он двудольный .
Доказательство
Это доказательство вдохновлено Дистелем (2000) .
Пусть G = ( V , E ) простой неориентированный граф. Действуем индукцией по m - количеству ребер. Если граф пуст, теорема тривиально верна. Пусть т > 0 , и пусть собственная (Δ + 1) -Станок-раскраска существует для всех G - ху , где х ∈ 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 0 ∈ 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 ≤ k .
Определим раскраски c 1 , ..., c k как
- c i ( xy j ) = c 0 ( xy j +1 ) для всех 0 ≤ 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 ≤ i ≤ k .
Пусть β - цвет, отсутствующий в y k относительно c 0 , тогда β также отсутствует в y k относительно c i для всех 0 ≤ i ≤ k . Обратите внимание, что β не может отсутствовать в x , иначе мы могли бы легко расширить c k , поэтому ребро с цветом β инцидентно x для всех c j . Из максимальности k существует 1 ≤ 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 выше.
Классификация графиков
Некоторые авторы предоставили дополнительные условия, которые классифицируют некоторые графы как относящиеся к классу 1 или классу 2, но не предоставляют полной классификации. Например, если вершины максимальной степени Δ в графе G образуют независимое множество или, в более общем смысле, если индуцированный подграф для этого набора вершин является лесом, то G должен быть первого класса. [1]
Эрдеш и Уилсон (1977) показали, что почти все графы относятся к первому классу. То есть, в модели случайных графов Эрдеша – Реньи , в которой все графы с n вершинами равновероятны, пусть p ( n ) будет вероятностью того, что граф с n вершинами, построенный из этого распределения, имеет первый класс; тогда p ( n ) приближается к единице в пределе, когда n стремится к бесконечности. Для более точных оценок скорости, с которой p ( n ) сходится к единице, см. Frieze et al. (1988) .
Планарные графики
Визинг (1965) показал, что планарный граф относится к первому классу, если его максимальная степень не меньше восьми. Напротив, он заметил, что для любой максимальной степени в диапазоне от двух до пяти существуют плоские графы второго класса. Для степени два таким графом является любой нечетный цикл, а для степени три, четыре и пять эти графы могут быть построены из платоновых тел путем замены одного ребра на путь из двух смежных ребер.
В Визинге планарных граф гипотезы , Визинг (1965) утверждает , что все простые, плоские графы с максимальной степенью шесть или семь имеют класс один, закрывая оставшиеся возможные случаи. Независимо, Чжан (2000) и Сандерс и Чжао (2001) частично доказали гипотезу Визинга о планарных графах, показав, что все плоские графы с максимальной степенью семь относятся к первому классу. Таким образом, остается нерешенным единственный случай гипотезы максимальной шестой степени. Эта гипотеза имеет значение для гипотезы о полной раскраске .
Плоские графы второго класса, построенные путем разбиения платоновых тел, не являются правильными: у них есть вершины второй степени, а также вершины более высокой степени. Теорема о четырех цветах (доказанная Аппелем и Хакеном (1976) ) о раскраске вершин плоских графов эквивалентна утверждению, что каждый 3-регулярный планарный граф без мостов имеет первый класс ( Tait 1880 ).
Графики на неплоских поверхностях
В 1969 году Бранко Грюнбаум предположил, что любой 3-регулярный граф с полиэдральным вложением на любом двумерном ориентированном многообразии, таком как тор, должен быть первого класса. В этом контексте полиэдральное вложение - это вложение графа , в котором каждая грань вложения является топологически диском и такой, что двойственный граф вложения является простым, без петель или множественных смежностей. Если это правда, то это было бы обобщением теоремы о четырех цветах, которая, как показал Тейт, эквивалентна утверждению, что 3-регулярные графы с полиэдральным вложением на сферу относятся к первому классу. Однако Кохол (2009) показал, что гипотеза неверна, найдя снарки, которые имеют полиэдральные вложения на ориентируемых поверхностях высокого рода. Основываясь на этой конструкции, он также показал, что NP-полно определить, принадлежит ли многогранно вложенный граф первому классу. [2]
Алгоритмы
Misra & Gries (1992) описывают алгоритм с полиномиальным временем раскраски ребер любого графа в Δ + 1 цвет, где Δ - максимальная степень графа. То есть алгоритм использует оптимальное количество цветов для графов класса два и использует не более одного цвета больше, чем необходимо для всех графов. Их алгоритм следует той же стратегии, что и первоначальное доказательство своей теоремы Визингом: он начинается с неокрашенного графа, а затем неоднократно находит способ перекрашивать граф, чтобы увеличить количество окрашенных ребер на единицу.
Более конкретно, предположим, что uv - неокрашенное ребро в частично раскрашенном графе. Алгоритм Мишра и Gries можно интерпретировать как построить направленный pseudoforest P (график , в котором каждая вершина имеет не более одного исходящего край) на соседях U : для каждого соседнего р о ц , алгоритм обнаруживает цветовой C , что является не используется какой - либо из ребер , инцидентных р , находит вершину д (если оно существует) , для которых край ид имеет цвет C , и добавляет рд в качестве края к P . Есть два случая:
- Если псевдолес P, построенный таким образом, содержит путь от v до вершины w , у которой нет исходящих ребер в P , то существует цвет c , доступный как в u, так и в w . Перекрашивание ребра uw в цвет c позволяет сдвинуть оставшиеся цвета ребер на один шаг вдоль этого пути: для каждой вершины p на пути ребро вверх принимает цвет, который ранее использовался преемником p в пути. Это приводит к новой окраске, включающей краевой ультрафиолет .
- Если, с другой стороны, путь, начинающийся с v в псевдолесе P, ведет к циклу, пусть w будет соседом u, в котором путь соединяется с циклом, пусть c будет цветом ребра uw , и пусть d будет цвет, который не используется ни одним из ребер в вершине u . Затем замена цветов c и d в цепочке Кемпе либо прерывает цикл, либо границу, на которой путь соединяется с циклом, что приводит к предыдущему случаю.
С помощью некоторых простых структур данных для отслеживания цветов, которые используются и доступны в каждой вершине, построение P и этапы перекраски алгоритма могут быть реализованы за время O ( n ) , где n - количество вершин в входной граф. Поскольку эти шаги необходимо повторить m раз, при каждом повторении количество окрашенных краев увеличивается на единицу, общее время составляет O ( mn ) .
В неопубликованном техническом отчете Gabow et al. (1985) утверждал, что быстрееоценка по времени для той же задачи раскраски в Δ + 1 цвет.
История
В работах Гутина и Тофта (2000) и Сойфера (2008) Визинг упоминает, что его работа была мотивирована теоремой Шеннона (1949), показывающей, что мультиграфы можно раскрасить не более чем (3/2) Δ цветов. Хотя теорема Визинга теперь является стандартным материалом во многих учебниках по теории графов, сначала Визингу не удалось опубликовать результат, и его статья по ней появилась в малоизвестном журнале Diskret. Анализ . [3]
Смотрите также
- Теорема Брукса, связывающая раскраски вершин с максимальной степенью
Заметки
- ^ Фурнье (1973) .
- ^ Kochol (2010) .
- ↑ Полное наименование журнала - Академия Наук СССР. Сибирское отделение. Institut Matematiki. Дискретный анализ. Сборник трудов . В1980 г.он был переименован в Методы Дискретного анализа (название дано в Gutin & Toft (2000) ) и прекращен в 1991 г. [1] .
Рекомендации
- Аппель, К .; Хакен, W. (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), "Colorations des arêtes d'un graphe", Cahiers du Centre d'Etudes de Recherche Opérationnelle , 15 : 311–314, MR 0349458.
- Frieze, Алан М .; Джексон, B .; МакДиармид, 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), «Сложность трехкратной раскраски в классе кубических графов с полиэдральным вложением в ориентируемую поверхность», Дискретная прикладная математика , 158 (16): 1856–1860, DOI : 10.1016 / j. плотина.2010.06.019 , MR 2679785.
- Misra, J .; Грис, Дэвид (1992), «Конструктивное доказательство теоремы Визинга», Информационные письма , 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 : 148–151, MR 0030203..
- Сойфер, Александр (2008), Математическая раскраска , Springer-Verlag, стр. 136–137, ISBN 978-0-387-74640-1.
- Tait, PG (1880), "Замечания о раскраске карт", Proc. R. Soc. Эдинбург , 10 : 729.
- Визинг В.Г. (1964) "Об оценке хроматического класса p -графа", Дискрет. Анализ. , 3 : 25–30, MR 0180505.
- Визинг В.Г. (1965) "Критические графы с заданным хроматическим классом", Методы Дискрет. Анализ. , 5 : 9–17. (На русском.)
- Чжан, Лимин (2000), «Каждый плоский граф с максимальной степенью 7 имеет класс 1», Графики и комбинаторика , 16 (4): 467–495.
Внешние ссылки
- Доказательство теоремы Визинга в PlanetMath .