Информатика · объяснение и практика
Минимум цветов требует двух доказательств: раскраски и отказа меньшего числа
Найти точное хроматическое число малого простого графа ограниченным полным поиском и предъявить проверяемую раскраску.

В теме Графы и маршруты · Учебная карта
Главная мысль
Любая корректная раскраска даёт верхнюю границу хроматического числа. Чтобы утверждать минимальность, нужно дополнительно исключить все меньшие числа цветов. В малом графе это можно сделать полным поиском с проверкой соседства и явным пределом вычислений.
Метод и постановка
Каждой вершине присваивается один цвет, а концы любого ребра должны иметь разные цвета. Цветовые номера являются только метками: глобальная перестановка номеров не меняет раскраску. Поэтому поиск может вводить новые цвета последовательно, не перебирая все переименования одного и того же решения. Это сокращает работу без потери существенно разных назначений.
Проверьте возможность раскраски сначала в один цвет, затем в два и далее. На очередной вершине запрещены цвета уже окрашенных соседей. Если допустимого цвета нет, вернитесь к предыдущему выбору. Порядок выбора вершин влияет на скорость поиска, но не на точность при полном завершении. Начало с более связных вершин часто раньше обнаруживает конфликт, однако само по себе не является доказательством оптимальности.
Проверка и границы вывода
Когда раскраска впервые найдена для k цветов, верхняя граница подтверждается непосредственной проверкой всех рёбер. Нижняя граница следует из завершённых отрицательных поисков для меньших значений. Если лимит вычислений достигнут до завершения, этот вывод нельзя подменять словом «точно». Ограниченный интерфейс возвращает ошибку ресурса вместо неподтверждённого минимального числа.
Жадный проход по вершинам решает другую задачу: быстро строит некоторую допустимую раскраску, которая может использовать лишние цвета. Не сравнивайте его результат с точным ответом без различения гарантий. Для независимых контрольных семейств используйте полный граф, где всем вершинам нужны разные цвета, и нечётный цикл, который не двухцветен, но допускает три цвета. Пустой по рёбрам непустой граф требует одного цвета. Эти проверки исследуют разные причины нижней границы и помогают отличить ошибку перебора от простой перестановки цветовых меток.
Пример
В треугольнике каждая пара вершин соединена. Два цвета невозможны: третья вершина соседствует с обеими уже разными. Три различных цвета дают корректную раскраску.
Здесь есть и нижняя, и верхняя граница три. Для цикла из пяти вершин нижняя граница два не достигается из-за нечётности, но три цвета также достаточны.
От чтения к действию
А теперь — вы
Частые вопросы
Жадная раскраска всегда минимальна?
Нет. Здесь минимальность получается отказами полного ограниченного поиска для всех меньших чисел цветов.
Что при достижении лимита поиска?
Возвращается ошибка ограничения вычислений. Промежуточная верхняя граница не выдаётся за точное хроматическое число.
Углублённый разбор
Линейный граф превращает рёберную раскраску в вершинную
Задачу раскраски рёбер можно передать решателю вершинной раскраски. Для этого каждое исходное ребро становится вершиной линейного графа, а общий конец превращается в конфликт цветов.
Перед началом: Правильная вершинная раскраска; Смежные рёбра.
Конфликт переносится без изменения допустимых назначений
Для простого неориентированного графа G построим L(G). Его вершины — рёбра G;две различные вершины L смежны, если соответствующие рёбра G имеют общий конец. Правильная рёберная раскраска G требует разных цветов именно у таких пар. Поэтому она взаимно однозначно соответствует правильной вершинной раскраске L(G) с теми же цветовыми метками.
Следовательно, хроматический индексχ′(G) равенχ(L(G)). Это точное преобразование задачи оптимизации, а не приблизительная оценка. Ноχ(G) самого исходного графа обычно отличается: в нём цвета назначаются другим объектам и ограничения относятся к другим парам. Путать эти два числа особенно легко на двудольных примерах.
Звезда исходной вершины становится кликой
Если исходная вершина имеет степень d, все её d инцидентных рёбер попарно конфликтуют. В линейном графе они образуют клику размера d. Поэтомуχ′(G)≥Δ(G), гдеΔ — максимальная степень. Это простой нижний сертификат, который можно предъявить вместе с конкретной верхней раскраской.
У линейного графа|E(G)|вершин, а число его рёбер для простого G равно Σ_v binom(d(v),2): каждая конфликтующая пара имеет единственный общий конец. Поэтому преобразование может заметно увеличить плотность. Быстрый исходный граф не гарантирует маленькую задачу для произвольного решателя раскраски.
Сохраняйте идентичность рёбер при обратном переносе
Результат решателя нужно вернуть исходным рёбрам, а не их концам. Удобно дать каждому ребру устойчивый идентификатор. В неориентированном простом графе можно использовать упорядоченную пару концов;при кратных рёбрах понадобится отдельный номер, и условия определения следует уточнить.
Петли в этой главе исключены: обычная правильная рёберная раскраска с петлёй имеет иной договор либо становится невозможной. Проверка готового ответа перечисляет пары рёбер у каждой исходной вершины и сравнивает их цвета. Она независимо подтверждает перенос, не доверяя только матрице L(G).
Квадрат с дополнительным ребром
Условие. Пусть G имеет рёбра AB,BC,CD,DA,AE. Найдитеχ′(G) через линейный граф и сравните сχ(G).
- У A три инцидентных ребра AB,DA,AE. В L(G) они образуют треугольник, поэтому нужны минимум 3 цвета.
- Назначим цвета AB=1,BC=2,CD=1,DA=2,AE=3. У каждого исходного конца цвета инцидентных рёбер различны.
- Получена верхняя граница 3, совпавшая с нижней. Поэтомуχ′(G)=χ(L(G))=3.
- Сам G двудолен с долями{A,C}и{B,D,E}, поэтомуχ(G)=2. Линейный граф имеет 5 вершин и 6 рёбер, а не повторяет исходную структуру.
Ответ. χ′(G)=3,χ(L(G))=3, ноχ(G)=2.
Проверка. Независимая проверка всех пар рёбер с общим концом находит 6 конфликтов и не находит совпавших цветов в назначении. Перебор двух цветов для пяти рёбер не даёт допустимого ответа.
Где легко ошибиться. Вершины L(G) обозначают рёбра G. Ответ раскраски нужно переносить на эти рёбра;присваивание тех же цветов исходным вершинам решает другую задачу.
Проверьте понимание
Вопросы к этой главе
Всякая клика L возникает из одной звезды?
Нет: треугольник исходного графа тоже даёт три попарно смежных ребра. Для простой нижней границыΔдостаточно звёзд, но полная структура клик может быть богаче.
Преобразование сохраняет число цветов точно?
Да, для указанной модели существует взаимно однозначное соответствие допустимых назначений с фиксированными цветовыми метками. Поэтому сохраняется и минимальное число.
Сверить определения и условия
Объяснение и задачи написаны для erudeet. Эти источники используются для проверки понятий и границ модели.
- NetworkX: line_graph
Официальная документация: прочитано соответствие рёбер исходного графа вершинам линейного и смежность по общему концу. Собственный квадрат с листом и цветовые сертификаты подготовлены отдельно.
Вырожденность гарантирует жадную раскраску
Удаление вершины минимальной текущей степени строит порядок с ограниченным числом будущих соседей. Раскраска в обратном порядке использует не больше d+1 цветов, где d — вырожденность, но эта граница не обязана совпадать с точнымχ.
Перед началом: Индуцированный подграф; Жадная раскраска.
Максимум минимальных степеней характеризует весь граф
Вырожденность d есть наибольшее значение минимальной степени среди непустых подграфов. Достаточно индуцированных подграфов: удаление дополнительных рёбер не увеличивает минимальную степень. Эквивалентно, каждый непустой индуцированный подграф содержит вершину степени не больше d, а некоторый содержит только степени не меньше d.
Последовательно удаляем вершину минимальной текущей степени, сохраняя её номер и степень при удалении. Максимум этих записанных степеней равен d. Он даёт верхний сертификат существующим порядком, а оставшийся подграф в момент достижения максимума даёт нижний сертификат: все его вершины тогда имеют степень хотя бы d.
Обратный порядок ограничивает число запрещённых цветов
Начинаем раскраску с последней удалённой вершины. Когда возвращается вершина v, уже окрашены только те соседи, которые оставались в момент её удаления;их не больше d. Поэтому среди d+1 цветов хотя бы один свободен. Выбор наименьшего свободного цвета даёт воспроизводимую правильную раскраску.
Если раскрашивать в прямом порядке удаления, у вершины могут оказаться многие уже окрашенные ранее удалённые соседи, и этот аргумент не сработает. Сохранённые степени относятся к оставшейся части, а не ко всем исходным соседям. Направление чтения порядка является частью доказательства, а не косметическим выбором реализации.
Подграф высокой минимальной степени не является кликой
Из d не следуетχ≥d+1. Например, полный двудольный K₃,₃ имеет вырожденность 3, но раскрашивается двумя цветами. Критерий контролирует доступное число ранее окрашенных соседей, а не наличие попарно смежного множества. Для точногоχнужен самостоятельный нижний сертификат.
Практический отчёт должен различать доказанную границу d+1, реальное число цветов выбранного жадного прохода и точный минимум, если он известен. Иногда проход использует меньше гарантированного максимума. Это улучшает предъявленную верхнюю границу, но само по себе ещё не доказывает её оптимальность.
Колесо с более слабой общей гарантией
Условие. Возьмите цикл A–B–C–D–A и центральную H, соединённую со всеми четырьмя. Найдите вырожденность, обратную жадную раскраску и сравните гарантию с точнымχ.
- Порядок удаления A,B,C,D,H имеет текущие степени 3,2,2,1,0. В каждом шаге выбрана вершина минимальной степени.
- Максимум 3 даёт d≤3, а весь исходный граф имеет минимальную степень 3, поэтому d=3. Общая гарантия равна 4 цветам.
- В обратном порядке можно назначить H=1,D=2,C=3,B=2,A=3. Проверка всех рёбер подтверждает правильность трёх цветов.
- Треугольник H,A,B даёт нижнюю границу 3. Поэтому точноеχ=3, хотя универсальная гарантия d+1 равна 4.
Ответ. d=3;гарантия 4 цвета;предъявленная и оптимальная раскраска использует 3.
Проверка. Прямой перебор всех непустых подмножеств пяти вершин подтверждает максимум минимальной степени 3. Отдельная треугольная нижняя граница и проверенные цвета сертифицируютχ=3.
Где легко ошибиться. Вырожденность d даёт верхнюю границу d+1, а не автоматическое равенствоχ=d+1. Читайте порядок удаления назад при применении доказанной жадной гарантии.
Проверьте понимание
Вопросы к этой главе
Нужно всегда выбирать уникальную вершину минимума?
Нет. При равенстве можно выбрать любую, сохраняя корректность. Фиксированное правило меток делает конкретный порядок и цвета воспроизводимыми.
Почему достаточно индуцированных подграфов?
Добавление всех рёбер между уже выбранными вершинами лишь повышает степени. Поэтому максимум минимальной степени не станет меньше при переходе к индуцированному варианту.
Сверить определения и условия
Объяснение и задачи написаны для erudeet. Эти источники используются для проверки понятий и границ модели.
- NetworkX: core_number
Прочитаны определение k-core, максимальный core number и исключение петель/мультиграфов. Обратная жадная раскраска, колесо и различие верхней границы с точнымχ доказаны отдельно.
Дробная раскраска и двойственные веса вершин
Дробная раскраска распределяет вес между независимыми множествами, покрывая каждую вершину суммарно хотя бы единицей. Она допускает меньшую стоимость, чем целочисленное число цветов. Оптимальность подтверждается двумя наборами весов: покрытием сверху и ограничением на каждое независимое множество снизу.
Перед началом: Независимое множество; Линейные неравенства.
Цветовые классы становятся переменными линейной программы
Пусть I пробегает все независимые множества конечного простого графа. Назначим им веса x_I≥0 с условием Σ_{I∋v}x_I≥1 для каждой вершины v. Минимизируем Σ_I x_I; оптимум называется χ_f. Обычная k-раскраска даёт допустимое решение, поставив вес 1 её цветовым классам, поэтому χ_f≤χ. Но дробные веса не обязаны соответствовать разбиению вершин на непересекающиеся классы.
Рациональное решение можно трактовать как многократную раскраску. Умножив веса на общий знаменатель b, получим a независимых цветовых классов с повторениями, покрывающих каждую вершину не меньше b раз. Лишние включения можно удалить. Тогда каждой вершине назначены b цветов из a, а соседние вершины не имеют общего цвета; стоимость равна a/b. Это содержательная интерпретация дробей, а не вероятность одного случайно выбранного правильного цвета.
Двойственные веса дают проверяемую нижнюю границу
Назначим вершинам y_v≥0 так, чтобы для любого независимого I выполнялось Σ_{v∈I}y_v≤1. Для любого допустимого покрытия Σ_v y_v≤Σ_I x_IΣ_{v∈I}y_v≤Σ_I x_I. Первое неравенство следует из покрытия каждой вершины. Следовательно сумма y является нижней границей, и совпадение с предъявленной стоимостью x доказывает точный оптимум без доверия решателю LP.
Недостаточно проверить двойственное условие только для нескольких удобных независимых множеств. Нужен весь класс либо доказанная верхняя граница на их вес. Например, равномерные веса 1/α допустимы, если размер любого независимого множества не больше α. Для графа с особой вершиной можно назначить ей другой вес и отдельно разобрать множества, содержащие её.
Присоединённая универсальная вершина добавляет отдельную стоимость
Если хаб h смежен со всеми вершинами обода, независимое множество, содержащее h, состоит только из него. Поэтому покрытие хаба требует отдельного суммарного веса не меньше 1 и не помогает покрывать обод. Это позволяет точно разложить задачу на хаб и исходный граф. Такая структурная проверка полезна при различении χ_f, кликового числа и обычной χ: эти три величины могут оказаться попарно разными.
Дробная раскраска колеса с семивершинным ободом
Условие. Граф содержит цикл 0–1–2–3–4–5–6–0 и хаб h, соединённый со всеми семью вершинами. Найдите χ_f, предъявив прямые и двойственные веса.
- Для каждого i modulo7 возьмём независимую тройку Iᵢ={i,i+2,i+4}. Каждая вершина обода входит ровно в3 такие тройки. Вес 1/3 каждой тройки покрывает обод единицей и имеет общую стоимость 7/3.
- Хаб покрываем множеством {h} веса 1. Общая стоимость допустимого дробного покрытия равна 1+7/3=10/3.
- Для нижней границы положим y_h=1, а для каждой вершины обода y=1/3. Любое независимое множество либо равно {h}, либо лежит в ободе и имеет не больше 3 вершин: четыре несмежные вершины потребовали бы не меньше 8 позиций цикла.
- Значит каждый независимый набор имеет вес не больше 1, и сумма двойственных весов равна 10/3. Верхняя и нижняя границы совпали. Обычному нечётному ободу нужны 3 цвета, хабу отдельный четвёртый.
Ответ. χ_f=10/3, тогда как χ=4 и максимальная клика имеет размер 3.
Проверка. Полный перебор 128 подмножеств обода подтверждает α=3 и все двойственные ограничения. Проверка семи троек подтверждает независимость и трёхкратное покрытие каждой вершины; отдельный перебор раскрасок исключает 3 цвета для всего колеса.
Где легко ошибиться. Не округляйте дробные веса по отдельности и не считайте их долями цвета каждой вершины без условий независимости. Нижний сертификат обязан ограничивать все независимые множества.
Проверьте понимание
Вопросы к этой главе
Почему хаб нельзя покрыть одной из троек?
Хаб смежен с каждым её участником, поэтому добавление h разрушит независимость. Любой цветовой класс с h не содержит вершины обода, и его стоимость нельзя разделить с ободом.
Означает χ_f=10/3 существование обычной раскраски тремя цветами?
Нет. Дробная программа является ослаблением целочисленной задачи. Здесь трёхцветный обод использует все три цвета, а универсальный хаб требует ещё один; минимум обычных цветов равен 4.
Сверить определения и условия
Объяснение и задачи написаны для erudeet. Эти источники используются для проверки понятий и границ модели.
- Chun-Hung Liu: Fractional coloring, 2024-03-04
Прочитаны stable-set-vertex incidence, LP в Theorem4 и взвешенная нижняя граница Proposition6/Theorem7. Собственный worked — колесо с7 вершинами обода и отдельным хабом, с явными прямыми и двойственными весами; не приведённый в источнике один нечётный цикл. ChicagoPDF geoff08 дал 502 и не использован.
Совершенный порядок исключения в хордальном графе
Жадная раскраска становится точной, если более поздние соседи каждой вершины образуют клику. Такой совершенный порядок исключения существует у хордальных графов. Он даёт сразу две проверяемые вещи: правильную раскраску и кликовую нижнюю границу того же размера.
Перед началом: Клика и раскраска; Индуцированный цикл.
Определение порядка фиксирует направление
Порядок v₁,…,vₙ называется совершенным порядком исключения, если для каждого i все соседи vᵢ с большими индексами попарно смежны. Иными словами, при последовательном удалении слева направо очередная вершина симплициальна в оставшемся графе. В некоторых источниках порядок записывают наоборот; всегда проверяйте, какая сторона соседей должна быть кликой.
Граф хордальный, если не содержит индуцированного цикла длины не меньше 4. Если порядок исключения существует, такой цикл невозможен: его самая ранняя вершина имела бы двух более поздних соседей по циклу без ребра между ними. Обратная теорема также верна: каждый хордальный граф допускает совершенный порядок. При распознавании можно построить кандидат поиском максимальной мощности, но затем нужно согласовать его ориентацию и проверить кликовое условие.
Раскрашивание идёт в обратном порядке удаления
Обрабатываем vₙ,…,v₁, назначая каждой вершине наименьший цвет, не занятый уже окрашенными соседями. Для vᵢ эти соседи являются как раз более поздними в порядке исключения и образуют клику. Если их k, они имеют k различных цветов, а вместе с vᵢ дают клику размера k+1. Поэтому очередной цвет не превосходит ω(G), размера максимальной клики.
Любая правильная раскраска требует не меньше ω(G) цветов. Значит жадный результат на совершенном порядке достигает точного χ=ω. Это более сильный вывод, чем общая гарантия через вырожденность: там известно только число поздних соседей, но не их попарная смежность и не совпадающая кликовая нижняя граница. Для конкретного ответа достаточно показать порядок, раскраску и одну клику нужного размера.
Плохой произвольный порядок ещё не опровергает хордальность
Даже хордальный граф имеет порядки, не удовлетворяющие определению. Нахождение двух несмежных поздних соседей опровергает этот кандидат, но само по себе не существование другого порядка. Для отрицательного сертификата можно предъявить индуцированный цикл длины≥4. Например, у квадрата без диагоналей ни одна вершина не симплициальна, поэтому начать порядок невозможно. Это отличается от неудачного произвольного запуска жадной раскраски.
Три перекрывающиеся клики
Условие. Рёбра графа являются объединением треугольников ABC,BCD,CDE; других рёбер нет. Проверьте порядок A,B,C,D,E и найдите оптимальную раскраску.
- У A более поздние соседи B,C смежны. У B поздние C,D смежны. У C поздние D,E также смежны; у D остаётся только E. Значит порядок совершенный.
- Красим обратно: E получает 1, D получает 2, C получает 3, поскольку смежна с E,D.
- У B окрашенные соседи C,D имеют цвета 3,2, поэтому доступен 1. У A соседи B,C имеют цвета 1,3, поэтому назначаем 2.
- Итак, A=2,B=1,C=3,D=2,E=1. Каждое исходное ребро соединяет разные цвета. Треугольник ABC требует 3 цвета, значит результат оптимален.
Ответ. Совершенный порядок A,B,C,D,E даёт χ=ω=3 и цвета (2,1,3,2,1).
Проверка. Независимый перебор всех подмножеств находит максимальную клику размера 3; перебор двухцветных назначений не находит раскраски. Полная проверка пар поздних соседей подтверждает сертификат порядка.
Где легко ошибиться. Не раскрашивайте в направлении удаления и не используйте неудачу одного произвольного порядка как доказательство нехордальности. Проверяйте и ориентацию порядка, и кликовость поздних соседей.
Проверьте понимание
Вопросы к этой главе
Нужно ли перечислять все клики для доказательства оптимальности раскраски?
Нет. Правильная раскраска тремя цветами даёт верхнюю границу 3, а один треугольник — нижнюю 3. Полный перебор клик здесь служит дополнительной независимой проверкой, а не обязательной частью короткого сертификата.
Почему неиндуцированный цикл из четырёх вершин разрешён?
Если у него есть хорда, соответствующие две поздние соседние вершины могут быть смежны. Запрещены именно циклы без хорд; хордальный граф не обязан быть деревом или вообще не иметь длинных циклов.
Сверить определения и условия
Объяснение и задачи написаны для erudeet. Эти источники используются для проверки понятий и границ модели.
- Pfenning, Platzer: Register Allocation, §4–6
Прочитаны chordal graphs, simplicial elimination и оптимальность greedy coloring. В источнике соглашение о порядке противоположно нашему: там кликой являются более ранние соседи, здесь более поздние, поэтому раскраска идёт в обратном порядке. Собственный граф трёх перекрывающихся треугольников проверен отдельно. BuffaloPDF вернул 404.
Треугольников нет, а цветов нужно четыре: конструкция Мычельского
Отсутствие треугольников не гарантирует раскраску тремя цветами. Конструкция Мычельского добавляет теневые вершины и одну общую вершину так, что число цветов увеличивается на единицу, а треугольники из ничего не возникают. Нижняя граница получается преобразованием предполагаемой раскраски.
Перед началом: Правильная вершинная раскраска; Нечётный цикл и хроматическое число.
Тени копируют соседство, но не образуют свой слой рёбер
Пусть простой граф G имеет вершины vi. Сохраним все его рёбра и добавим для каждого vi теневую вершину ui. Для каждого старого ребра vivj добавляются ui-vj и uj-vi. Ещё одна вершина w соединяется со всеми ui. Между двумя тенями рёбер нет; ребро ui-vi также не добавляется автоматически.
Если G правильно раскрашен k цветами, каждой тени можно дать цвет её оригинала, а w — новый цвет. Старые рёбра остаются правильными. Новое ребро ui-vj также правильно, поскольку его концы получают цвета соседних vi,vj. Так получается верхняя граница k+1. Одной этой конструкции раскраски ещё недостаточно для доказательства точного увеличения.
Удаление одного цвета доказывает невозможность k цветов
Предположим, что весь новый граф раскрашен всего k цветами, где k=χ(G). Назовём цвет w выделенным. Ни одна тень не имеет этого цвета. Теперь в старом графе заменим цвет каждой vi выделенного цвета на цвет соответствующей ui. Остальные старые вершины оставим как были.
Две смежные старые вершины не могли обе иметь выделенный цвет. Если перекрашивается только vi, сосед vj не конфликтует с её новым цветом: тень ui смежна с vj в новом графе. Получилась правильная раскраска G без выделенного цвета, то есть k−1 цветами. Это противоречит определению k и даёт нижнюю границу k+1.
Почему треугольник не появляется
Треугольник, содержащий w, потребовал бы ребра между двумя тенями, а таких рёбер нет. Треугольник без w может содержать не больше одной тени. Если в нём есть ui и старые vj,vk, то в G существовали бы все три ребра vi-vj,vi-vk,vj-vk. Значит, он происходил бы из старого треугольника.
Начав с нечётного цикла без треугольников, получаем новый граф без треугольников с большим хроматическим числом. Повторение операции строит всё более требовательные к раскраске графы. Это полезный контрпример попытке оценивать число цветов только по крупнейшей клике: локальная проверка трёх попарно смежных вершин не обнаруживает глобального препятствия.
Одиннадцать вершин, двадцать рёбер, четыре цвета
Условие. Возьмите цикл v0-v1-v2-v3-v4-v0. Постройте его граф Мычельского и определите число вершин, рёбер, наличие треугольников и точное хроматическое число.
- Пять исходных вершин, пять теней и w дают 11 вершин. Пять исходных рёбер порождают десять перекрёстных, ещё пять соединяют w с тенями: всего 20.
- Цикл C5 требует три цвета: чередование двух цветов возвращается к исходной вершине с конфликтом. Цвета (0,1,0,1,2) дают явную трёхцветную раскраску.
- Назначим ui цвет vi, а w цвет 3. Все 20 рёбер соединяют разные цвета, поэтому новый граф допускает четыре цвета.
- Если бы хватило трёх, перекрашивание старых вершин цвета w цветами их теней дало бы двухцветную раскраску C5. Это невозможно, поэтому четыре цвета необходимы.
- В исходном C5 треугольников нет. Разбор положения w и теневых вершин исключает их появление в построенном графе.
Ответ. Получен треугольников свободный граф на 11 вершинах с 20 рёбрами и χ=4.
Проверка. Независимый перебор троек вершин не находит треугольника. Поиск правильных раскрасок с возвратами отвергает три цвета и находит допустимую четырёхцветную раскраску.
Где легко ошибиться. Не соединяйте тени между собой по образцу исходного графа. Это другая конструкция, для которой приведённое доказательство отсутствия треугольников уже не работает.
Проверьте понимание
Вопросы к этой главе
Почему общая вершина соединена только с тенями?
Так она запрещает свой цвет всему теневому слою. Именно это позволяет убрать один цвет из предполагаемой раскраски исходного графа и получить противоречие.
Означает ли отсутствие треугольников двудольность?
Нет. Уже исходный цикл C5 не содержит треугольников, но имеет нечётный цикл и не является двудольным. Новая конструкция усиливает это расхождение: требуется четыре цвета.
Сверить определения и условия
Объяснение и задачи написаны для erudeet. Эти источники используются для проверки понятий и границ модели.
- Yolcu, Wu, Heule: Mycielski graphs and PR proofs
Определение семейства графов Мычельского и хроматическое препятствие; раздел о кодировании раскраски фиксирует соседство оригиналов, теней и общей вершины.
Хроматический многочлен считает все правильные раскраски
Хроматическое число сообщает минимально достаточное число цветов, но не говорит, сколько различных назначений допускают ограничения. Хроматический многочлен P(G,q) считает правильные раскраски различимыми цветовыми метками. Удаление–стягивание разбивает множество назначений на две непересекающиеся категории и позволяет получить точное выражение по q, пригодное для нескольких значений числа цветов.
Перед началом: Правильная вершинная раскраска; Разбиение конечного множества по условию равенства.
Цветовые метки в этом подсчёте различимы
Конечный простой неориентированный граф; q — число доступных различимых цветов, использовать все цвета не обязательно.
Раскраска является функцией из множества вершин в {1,…,q}, различающей концы каждого ребра. Глобальная перестановка использованных меток обычно даёт другую считаемую функцию. Это важно отличать от поиска одного представителя с точностью до переименования цветов, который часто применяется при вычислении хроматического числа.
Для графа без рёбер P=q^n, поскольку цвет каждой вершины выбирается независимо. Для дерева P=q(q−1)^(n−1): после выбора цвета корня у каждой следующей вершины запрещён только цвет родителя. Наличие одной правильной q-раскраски доказывает лишь P(G,q)>0, а не определяет всё значение этого счётчика.
Удаление–стягивание отделяет равные концы
Возьмём ребро e=uv и временно удалим его. В каждой правильной раскраске G−e концы u,v либо различны, либо равны. Первый класс совпадает с раскрасками исходного G. Второй биективен раскраскам G/e, где u,v объединены в одну вершину. Поэтому P(G,q)=P(G−e,q)−P(G/e,q).
При стягивании сначала удаляется само e; оставшиеся параллельные копии рёбер можно объединять, потому что они задают одинаковое требование различия. Настоящая петля, напротив, запрещает любую правильную раскраску и даёт нулевой счётчик. Ошибка знака меняет вычитание недопустимого класса на его добавление.
Многочлен проверяет больше, чем хроматическое число
Повторение рекурсии до графов без рёбер доказывает, что счётчик является многочленом. Для простого n-вершинного графа старший коэффициент равен 1, а коэффициент при q^(n−1) равен минус числу рёбер. Эти свойства дают быстрые проверки результата, хотя сами по себе ещё не удостоверяют все коэффициенты.
Наименьшее положительное целое q с P(G,q)>0 возвращает хроматическое число. Но два графа с одинаковым минимумом могут иметь разные количества раскрасок при том же q. Рекурсия в общем случае разветвляется экспоненциально; компактная формула малого примера не превращает точный подсчёт произвольных графов в линейный алгоритм.
Квадрат с крышей: считать назначения, а не только три цвета
Условие. Граф имеет цикл 0—1—2—3—0 и крышу: вершина 4 соединена с 1 и 2. Выведите P(G,q), удаляя и стягивая ребро 0—3, затем посчитайте раскраски тремя различимыми цветами.
- После удаления 0—3 основание превращается в путь на четырёх вершинах. Он раскрашивается q(q−1)³ способами. Вершины 1,2 смежны и уже различны, поэтому цвет крыши выбирается q−2 способами.
- После стягивания 0—3 основание становится треугольником. Его можно раскрасить q(q−1)(q−2) способами; крыша по-прежнему имеет q−2 вариантов. Получаем q(q−1)(q−2)².
- Вычитаем: P=q(q−1)³(q−2)−q(q−1)(q−2)²=q(q−1)(q−2)(q²−3q+3). В развёрнутом виде это q⁵−6q⁴+14q³−15q²+6q.
- При q=3 результат равен 3·2·1·3=18. При q=2 он нулевой из-за треугольника крыши. Следовательно χ=3, но число правильных трёхцветных назначений равно восемнадцати, а не трём.
Ответ. P(G,q)=q(q−1)(q−2)(q²−3q+3); P(G,3)=18, χ(G)=3.
Проверка. Независимый перебор 3⁵=243 назначений находит ровно 18 правильных. Коэффициент при q⁴ равен −6, согласуясь с шестью рёбрами; перебор при q=4 даёт 168, как и формула.
Где легко ошибиться. Не делите автоматически число раскрасок на q!. Если некоторые доступные цвета не использованы, переименования могут иметь стабилизатор; в этой главе по определению считаются различимые метки.
Проверьте понимание
Вопросы к этой главе
Почему у крыши q−2 вариантов, а не q−1?
Её два соседа соединены ребром и потому имеют разные цвета. Запрещены две разные метки; это условие нужно проверить, прежде чем умножать число вариантов.
Что означает значение многочлена при нецелом q?
Алгебраическое выражение определено и там, но буквальное число раскрасок в данной постановке относится к неотрицательному целому числу доступных цветов. Нецелое значение не является количеством назначений.
Сверить определения и условия
Объяснение и задачи написаны для erudeet. Эти источники используются для проверки понятий и границ модели.
- ISI Bangalore — Chromatic Polynomials, Proposition 11.3
Определение счёта различимыми цветами, удаление–стягивание и первые коэффициенты многочлена. Граф с крышей, символическое выражение и конечные переборы подготовлены отдельно.
Источники и работа с материалом
Объяснение, примеры и вопросы написаны для erudeet. Факты и определения сверены по источникам ниже; это ссылки для самостоятельной проверки.
Продолжить разбираться
Сколько полных назначений разрешает совместимость: перманент без знаков перестановок
Посчитать все полные взаимно однозначные назначения по матрице совместимости и объяснить формулу Райзера через включения и исключения.
Открыть темуКакая стрелка зависимости лишняя: сохранение всех достижимых пар
Построить транзитивную редукцию DAG и проверить, что удаление прямых избыточных дуг сохранило все направленные зависимости по путям.
Открыть темуСколько разных остовов соединяет граф: определитель вместо выбора одного дерева
Посчитать все остовные деревья заданного простого графа через кофактор лапласиана и отличить этот результат от поиска минимального остова.
Открыть тему