Раскраска краев

редактировать
Раскраска по трем краям графа Дезарга.

В теории графов окраска ребер графа - это присвоение «цветов» ребрам графа таким образом, чтобы никакие два инцидентных ребра не имели одинаковый цвет. Например, на рисунке справа окраска краев графа в красный, синий и зеленый цвета. Раскраска ребер - это один из нескольких типов раскраски графа. Задача раскраски краев спрашивает, можно ли раскрасить ребра данного графа, используя не более k различных цветов, для значений k или наименьшего количества ведущих цветов. Минимальное необходимое количество цветов для ребер данного графа называется хроматическим индексом графа. Например, края графа на иллюстрации могут быть окрашены в три цвета, но не могут быть окрашены в два цвета, поэтому могут быть окрашены в три цвета, но не могут быть окрашены в два цвета.

Согласно теореме Визинга, количество цветов, необходимых для окраски края простого графа, равно либо его максимальной степени Δ, либо Δ + 1. Для некоторых графов, таких как двудольные графы и планарные графы высокой степени , количество цветов всегда равно Δ, а для мультиграфов количество цветов может достигать 3Δ / 2. Существуют алгоритмы с полиномиальным временем, которые строят оптимальные раскраски двудольных графов, и раскраски недвудольных простых графов, использующие не более Δ + 1 цвета; однако проблема поиска оптимальной раскраски ребер является NP-сложной, и самые быстрые известные алгоритмы для этого требуют экспоненциального времени. Было изучено множество вариантов раскраски ребрам. Цвета краев применяются в задаче планирования и при назначении частот для оптоволоконных сетей .

Содержание

  • 1 Примеры
  • 2 Определения
  • 3 Отношение к сопоставлению
  • 4 Отношение к степени
    • 4.1 Теорема Визинга
    • 4.2 Регулярные графы
    • 4.3 Мультиграфы
  • 5 Алгоритмы
    • 5.1 Оптимальная раскраска специальных классов графов
    • 5.2 Алгоритмы, использующие больше оптимального количества цветов
    • 5.3 Точные алгоритмы
  • 6 Дополнительные свойства
  • 7 Другие типы
  • 8 Приложения
  • 9 Открытые задачи
  • 10 Примечания
  • 11 Ссылки

Примеры

A граф цикла могут иметь окрашенные в два цвета, если длина цикла четная: просто чередуйте два цвета вокруг цикла. Однако, если длина нечетная, необходимы три цвета.

Геометрическое построение 7-краевой раскраски полного графа K8. Каждый из семи цветовых классов имеет одно ребро от центра до вершины многоугольника и три ребра, перпендикулярных к нему.

A полный граф Knс n вершинами окрашивается краями в n - 1 цвет, когда n - четное число; это частный случай теоремы Бараньяи. Soifer (2008) предлагает следующее геометрическое построение раскраски в этом случае: link n точек в вершинах и в правильном (n - 1) -стороннем многоугольника. Для каждого цветового класса включите одно ребро от центра до одной из вершин многоугольника и все перпендикулярные ребра, соединяющие пары вершин многоугольника. Однако, когда n нечетно, необходимо n цветов: каждый цвет может только для (n - 1) / 2 краев, что составляет 1 / n часть от общего числа.

Несколько авторов изучали окраску краев нечетные графы, n-регулярные графы, в вершины включают команды из n - 1 игроков, выбранных из пула из 2n - 1 игроков, а ребра включают возможные пары этих команд (с лишним игроком оставлен как "судить игру"). Случай n = 3 дает хорошо известный граф Петерсена. Как Биггс (1972) объясняет проблему (для n = 6), игроки хотят найти расписание для этих пар, чтобы каждая команда играла каждую из шести игр в разные дни недели, с воскресеньями. отключено для всех команд; то есть, формализовав задачу математически, они хотят найти 6-краевую раскраску 6-регулярного нечетного графа O 6. Когда n равно 3, 4 или 8, для окраски краев O n требуется n + 1 цвета, но когда это 5, 6 или 7, требуется только n цветов.

Определения

Как и в случае его вершинного аналога, окраска ребер графа, когда указывается без каких-либо оговорок, всегда правильной окраской ребер Это означает, что никаким двум смежным кромкам не назначается один цвет. Здесь два различных ребра, связанных, если они имеют общую вершину. Раскраска ребер графа G также может выглядеть как эквивалент раскраски вершин линейного графа L (G), графа, имеющего вершину для каждого ребра графа G и ребро для каждой пары смежных ребер в G.

Правильная раскраска ребер в k различных цветов называется (собственной) k-раскраской ребер. Граф, которому можно присвоить к-рёберную раскраску, называется к-рёберной раскраской. Наименьшее количество цветов, необходимое для (правильной) окраски ребер графа G, - это хроматический индекс, или краевое хроматическое число χ '(G). Хроматический индекс также иногда записывают с использованием обозначения χ 1 (G); в этом обозначении нижний индекс указывает, что ребра являются указанными объектами. Граф является k-реберно-хроматическим, если его хроматический индекс в точности равен k. Хроматический индекс не следует путать с хроматическим числом χ (G) или χ 0 (G), минимальным количеством цветов, необходимыми для правильной раскраски вершин G.

Если не указаны параметры, все графы простыми, в которых указано отличие от мультиграфов, в которых два или более ребра могут соединять одну и ту же пару конечных точек в которых могут быть петли. Для задач раскраски многих ребер простые графы ведут себя, чем мультиграфы, и требуется дополнительная осторожность, чтобы распространить теоремы о раскраске ребер простых графов на случай мультиграфов.

Отношение к сопоставлению

Этот 3-регулярный плоский граф имеет 16 вершин и 24 ребра, но только 7 ребер в любом максимальном сопоставлении. Следовательно, для любого раскраски ребер требуется четыре цвета.

A соответствие в графе G - это набор ребер, никакие два из которых не являются родственными; идеальное совпадение - это совпадение, которое включает ребра, соприкасающиеся со всеми вершинами графа, максимальное совпадение - это совпадение, которое включает в себя как можно больше рёбер. В раскраске ребер набор ребер любого одного цвета не должен быть совместимым друг с другом, поэтому они образуют соответствие. То есть правильная раскраска ребер - это то же самое, что разбиение графа на непересекающиеся сопоставления.

Если соответствующий размер будет мал, потребуется много сопоставлений, чтобы покрыть все ребра графа. Выражаясь более формально, это рассуждение подразумевает, что если граф имеет всего m ребер и если не более β ребер может использовать максимальную соответствие, то каждая окраска ребер графа должна использовать не менее m / β различных цветов. Например, планарный граф с 16 вершинами, показанный на иллюстрации, имеет m = 24 ребра. На этом графике не может быть идеального соответствия; поскольку, если центральная вершинападает, оставшиеся несовпадающие вершины могут быть сгруппированы в три различных связных компонента с четырьмя, пятью и пятью вершинами, а компоненты с нечетным составом вершин не могут быть полностью согласованы. Следовательно, цветов, необходимые для окраски ребер графа, составляют не менее 24/7, поскольку количество цветов должно быть целым числом, оно должно быть не менее четырех.

Для регулярного графа степени k, который не имеет идеального соответствия, эта нижняя граница может быть, чтобы показать, что требуется по крайней мере k + 1 цвет. В частности, это верно для регулярного графа с нечетным числом вершин (например, для нечетных полных графов); для таких графов по лемме о подтверждении связи k должно быть четным. Не неравномерно неравенство χ ′ ≥ m / β не полностью объясняет хроматический индекс каждого регулярного графа, потому что регулярные графы, которые имеют идеальное сопоставление, но не могут быть раскрашены по k-ребрам. Например, граф Петерсена является правильным, с m = 15 и β = 5 ребрами в его совершенных сопоставлениях, но он не имеет 3-краевой раскраски.

Отношение к степени

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

Хроматическое число ребер графа G очень связано с максимальной степенью Δ (G), наибольшее количество ребер, инцидентных любой одной вершине графа G. Ясно, что χ ′ (G) ≥ ∆ (G), так как если ∆ разные ребра пересекаются в одной вершине v, то всем этим ребрам нужно присвоить разные цвета друг от друга, а это возможно только при наличии как минимум Δ цветов, доступных для назначения. Теорема Визинга (названная в честь Вадима Г. Визинга, который опубликовал ее в 1964 году) утверждает, что эта граница почти точная: для любого графа хроматическое число ребер равно Δ (G) или Δ (G) + 1. Когда χ ′ (G) = Δ (G), G называется классом 1; в противном случае говорят, что он принадлежит к классу 2.

Каждый двудольный граф относится к классу 1, и почти все случайные графы к классу 1. Он является NP-полным, чтобы определить, принадлежит ли произвольный граф к классу 1.

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

Регулярные графы

A 1-факторизация k- регулярного графа, разбиение ребер графа на совершенное сопоставление, это то же самое, что раскраска k-ребер графа. То есть регулярный граф имеет 1-факторизацию тогда и только тогда, когда он принадлежит к классу 1. Как частный случай этого, 3-краевая раскраска кубического (3-регулярного) графа является иногда называется раскраской Тейта .

Не каждый регулярный граф имеет 1-факторизацию; например, граф Петерсена - нет. В более общем смысле, снарки определяют как графы, которые, как и граф Петерсена, являются 3-регулярными без мостов и имеют класс 2.

Согласно теореме Кёнига (1916), каждый двудольный регулярный граф имеет 1-факторизацию. Теорема была сформулирована ранее в терминах проективных конфигураций и была доказана Эрнстом Стейницем.

Мультиграфами

A Мультиграфом Шеннона со степенью шесть и кратностью, требуемой девяти цветов в любых раскраска ребер

Для мультиграфов, в которых несколько параллельных ребер могут соединять одни и те же две вершины, известны результаты, на теорему Визинга, но более слабые, чем теорема Визинга, связывающие хроматическое число ребер χ ′ (G), максимальная степень Δ (G), а кратность μ (G) - максимальное количество ребер в любом пучке параллельных ребер. В качестве примера, показывающего, что теорема Визинга не обобщается на мультиграфы, рассмотрим мультиграф Шеннона, мультиграф с тремя вершинами и тремя связками из μ (G) параллельных ребер, соединяющих каждую из трех пар вершин. В этом примере ∆ (G) = 2μ (G) (каждая вершина инцидентна двух из трех пучков параллельных ребер μ (G)), но хроматическое число ребер равно 3μ (G) (имеется 3μ (G) ребер всего, и каждые два ребра связаны соответствующими, поэтому всем ребрам должны быть присвоены разные цвета друг другу). В результате, вдохновившем Визинга, Шеннон (1949) показал, что это наихудший случай: χ ′ (G) ≤ (3/2) Δ (G) для мультиграфа G. Кроме того, для любого мультиграфа G, χ ′ (G) ≤ ∆ (G) + μ (G), неравенство, сводится к теореме Визинга в случае простых графов (для μ (G) = 1).

Алгоритмы

Временная проблема проверки того, является ли граф классом 1, NP-полным, не существует известного алгоритма полиномиального времени для окраски ребер каждого графа с помощью оптимального количества цветов. Тем не менее, разработан ряд алгоритмов, которые ослабляют один или несколько из этих критериев: они работают только с подмножеством графов, или они не всегда используют оптимальное количество цветов, или они не всегда работают за полиномиальное время.

Оптимальная раскраска специальных классов графов

В случае двудольных графов или мультиграфов с максимальной степенью Δальное оптимальное количество цветов равно Δ. Cole, Ost Schirra (2001) показал, что оптимальная окраска ребер этих графов может быть найдена в почти линейной временной границе O (m log Δ), где m - количество ребер в графе. ; более простые, но несколько более медленные алгоритмы стимулирования в Cole Hopcroft (1982) и Alon (2003). Алгоритм Alon (2003) начинается с того, что входной граф становится регулярным, без увеличения его степени или значительного увеличения размера, путем слияния пар вершин, принадлежащих одной стороне двудольного деления, и последующего добавления небольшого количества дополнительных вершин и ребер. Затем, если степень нечетная, Алон находит единственное идеальное соответствие за почти линейное время, присваивает ему цвет и удаляет его с графикой, в результате чего степень становится четной. Наконец, Алон применяет наблюдение Габоу (1976), согласно которому выбор чередующихся подмножеств ребер в эйлеровом обходе графа разбивает его на два регулярных подграфа, чтобы разбить проблему окраски ребер. на две меньшие подзадачи, и его алгоритм рекурсивно решает две подзадачи . Общее время его алгоритма составляет O (m log m).

Для плоских графов с максимальной степенью Δ ≥ 7 оптимальное количество цветов снова равно Δ. При более сильном предположении, что Δ ≥ 9, можно найти оптимальную раскраску ребер за линейное время (Cole Kowalik 2008).

Для d-регулярных графов, которые являются псевдослучайными в том смысле, что их матрица имеет второе по величине собственное значение (по модулю) не более d, d - оптимальное количество цветов (Ferber Jain 2018).

Алгоритмы, которые используют больше, чем оптимальное количество цветов

Misra Gries (1992) и Gabow et al. (1985) описывают полиномиальные временные алгоритмы для раскраски любого графа в Δ + 1 цвет, удовлетворяющий оценку, данной теоремой Визинга; см. алгоритм окраски краев Misra Gries.

Для мультиграфов Karloff Shmoys (1987) предлагает следующий алгоритм, который они приписывают Эли Апфал. Сделайте входной мультиграф G эйлеровым, добавив новую вершину, соединенную ребром с каждой вершиной нечетной степени, найдите эйлеров тур и выберите его ориентацию. Сформируйте двудольный граф H, в котором есть две копии каждой вершины G, по одной на каждой стороне двудольного раздела, с ребром от вершины u на левой стороне двудольного до вершины v на правой стороне двудольного. разный, когда ориентированный тур имеет ребро от u до v в G. Примените алгоритм раскраски двудольного графа к H. Каждый цветовой класс в H соответствует набору ребер в G, которые образуют подграф с максимальной степенью два; Это несвязное объединение путей и циклов, поэтому для каждого цветового класса в H можно настроить три цветовых класса в G. Время для алгоритма ограничено временем окраски двудольного графа, O (m log Δ) с использованием алгоритма Cole, Ost Schirra (2001). Этот алгоритм использует не более 3 ⌈ Δ 2 ⌉ {\ displaystyle 3 \ left \ lceil {\ frac {\ Delta} {2}} \ right \ rceil}3 \ left \ lceil {\ frac \ Дельта 2} \ вправо \ rceil , близко до, но не совсем то же самое, что и оценка Шеннона для ⌊ 3 Δ 2 ⌋ {\ displaystyle \ left \ lfloor {\ frac {3 \ Delta} {2}} \ right \ rfloor}\ left \ lfloor {\ frac {3 \ Delta} 2} \ правый \ rfloor . Он также может быть преобразован в параллельный алгоритм простым способом. В той же статье Карлофф и Шмойс также алгоритм линейного времени для раскраски мультиграфов максимального числа три в четыре цвета (совпадающих с границами Шеннона и Визинга), который работает на аналогичных принципах: их алгоритм новой вершины, чтобы сделать граф эйлеровым, находить обход Эйлера, а затем выбирает чередующиеся наборы ребер в обходе, чтобы разбить граф на два подграфа максимальной степени два. Пути и даже циклы каждого подграфа могут быть раскрашены двумя цветами на каждый подграф. После этого шага каждый оставшийся нечетный цикл содержит по крайней мере одно ребро, которое может быть окрашено в один из двух цветов, принадлежащих противоположному подграфу. Удаление этого ребра из нечетного цикла оставляет путь, который можно раскрасить двумя цветами для его подграфа.

A Алгоритм жадной раскраски, который рассматривает ребра графа или мультиграфа одно за другим, присваивая каждому ребру первый доступный цвет, иногда может использовать до 2Δ - 1 цвета, которые могут быть количеством цветов почти вдвое больше, чем необходимо. Однако он имеет то преимущество, что его можно использовать в настройке онлайн-алгоритма, в которой входной граф заранее неизвестен; в этой настройке его коэффициент конкуренции равен двум, и это оптимально: ни один другой онлайн-алгоритм не может достичь лучшей производительности. Однако, если рёбра прибывают в случайном порядке и входной граф имеет степень, по крайней мере, логарифмическую, тогда могут быть достигнуты меньшие конкурентные отношения.

Некоторые авторы высказали предположения, которые подразумевают, что дробное хроматический индекс любого мультиграфа (число, которое может быть вычислено за полиномиальное время с использованием линейного программирования ) находится в пределах одного из хроматических индексов. Если эти предположения верны, можно было бы вычислить число, которое никогда не будет отличаться более чем на единицу от хроматического индекса в случае мультиграфа, что соответствует тому, что известно из теоремы Визинга для простых графов. Хотя в целом эти гипотезы не доказаны, они, как известно, верны, когда хроматический индекс составляет не менее Δ + Δ / 2 {\ displaystyle \ Delta + {\ sqrt {\ Delta / 2}}}\ Delta + {\ sqrt {\ Delta / 2}} , что может случиться с мультиграфами с достаточно большой кратностью.

Точные алгоритмы

Несложно проверить, может ли граф быть раскрашен ребрами в один или два цвета, поэтому первый нетривиальный случай раскраски ребер проверяет, есть ли у графа трехкратная раскраска. Как показал Ковалик (2009), можно проверить, имеет ли граф трехреберную раскраску за время O (1.344), используя только полиномиальное пространство. Хотя эта временная граница экспоненциальна, она значительно быстрее, чем перебор всех возможных присвоений цветов краям. Каждый двусвязный 3-регулярный граф с n вершинами имеет O (2) 3-раскраски ребер; все это можно перечислить за время O (2) (несколько медленнее, чем время нахождения одной раскраски); как заметил Грег Куперберг, график призмы над n / 2-сторонним многоугольником имеет цвета Ω (2) (нижняя, а не верхняя граница), показывая, что эта граница жесткая.

Применяя точные алгоритмы раскраски вершин к линейному графу входного графа, можно оптимально раскрасить любой граф с m ребрами, независимо от количества необходимых цветов., во времени 2m в экспоненциальном пространстве или во времени O (2.2461) и только в полиномиальном пространстве (Björklund, Husfeldt Koivisto 2009).

Поскольку окраска краев является NP-полной даже для трех цветов, маловероятно, что управляемый фиксированный параметр при параметризации количеством цветов. Однако по другим параметрам он послушен. В частности, Zhou, Nakano Nishizeki (1996) показали, что для графов с шириной дерева w оптимальная окраска ребер может быть вычислена за время O (nw(6w)), оценка которая сверхэкспоненциально зависит от w, но только линейно от числа n вершин в графе.

Nemhauser Park (1991) формулируют проблему окраски краев как целочисленную программу и описывают свой опыт использования решателя целочисленного программирования для краевых цветных графов. Однако они не анализа сложности своего алгоритма.

Дополнительные свойства

Уникально трехкратный обобщенный граф Петерсена G (9,2). Один из трех его цветовых классов показаны светлыми краями, а два других можно найти, повернув светлые края на 40 ° в каждом направлении или разделив темный гамильтонов цикл на чередующиеся края.

График однозначно раскрашиваем по k-ребрам, если есть только один способ разбить ребра на k цветовых классов, игнорируя k! возможные перестановки цветов. При k ≠ 3 единственными графами, раскрашиваемыми однозначно по k ребрам, являются пути, циклы и звезды, но для k = 3 другие графы также могут быть однозначно раскрашенными по k ребрам. Каждый граф с уникальной трехкратной раскраской имеет ровно три гамильтоновых цикла (образованных удалением одного из трех цветовых классов), но существуют 3-регулярные графы, которые имеют три гамильтонова цикла и не являются однозначно трехкратными, такими как обобщенные графы Петерсена G (6n + 3, 2) для n ≥ 2. Единственным известным непланарным однозначно 3-раскрашиваемым графом является обобщенный граф Петерсена G (9,2), и он был предположил, что других не существует.

Полный двудольный граф K 3,3, каждый из его цветовых классов нарисован как параллельные отрезки на разных прямых.

Folkman Fulkerson (1969) исследовал невозрастающие последовательные числа m 1, m 2, m 3,... со своимством, которое существует правильная окраска ребер данного графа G с m 1 ребрами первого цвета, m 2 ребрами второго цвета и т. д. Они заметили, что если последовательность P допустима в этом смысле и больше в в лексикографическом порядке, чем последовательность Q с такой же суммой, то Q также допустима. Ибо, если P>Q в лексикографическом порядке, то P может быть преобразовано в Q последовательностью шагов, каждый из которых уменьшает одно из чисел m i на одну единицу и увеличивает другое более позднее число m j с i < j by one unit. In terms of edge colorings, starting from a coloring that realizes P, each of these same steps may be performed by swapping colors i and j on a цепочкой Кемпе, максимальным путем ребер, которые чередуются между двумя цветами. В частности, любой граф имеет справедливую раскраску ребер, раскраску ребер с оптимальным качеством цветов, в которой каждые два цветовых класса отличаются по размеру не более чем на одну единицу.

Теорема Де Брейна - Эрдеша может быть применима для переноса многих свойств окраски ребер конечных графов на бесконечные графы. Например, теоремы Шеннона и Визу, связывающие степень графа с его хроматическим индексом, напрямую обобщены на бесконечные графинга.

Richter (2011) рассматривает проблему поиска графа, представляющего задан кубический граф со свойствами, что все ребра на чертеже имеют один из трех разных наклонов и что никакие два ребра не лежат на одной линии друг с другом. Если такой рисунок существует, то очевидно, что наклоны ребер одна как цвета в раскраске трех ребер графа. Например, изображение графа полезности K 3,3 в виде ребер и длинных диагоналей правильного шестиугольника представляет собой раскраску с 3 ребрами график таким образом. Как показывает Рихтер, 3-регулярный простой двудольный граф с заданной раскраской Тейта имеет рисунок этого типа, который представляет собой раскраску тогда и только тогда, когда граф 3-реберно-связный. Для недвудольного графа условие немного сложнее: заданная раскраска может быть представлена ​​рисунком, если двудольное двойное покрытие графа 3-реберно связно, и если удалить любое одноцветное пара ребер приводит к подграфу, который все еще не двудольным. Все эти условия можно легко проверить за полиномиальное время; однако проблема проверки того, имеет ли 4-крашенный 4-регулярный граф с четырьмя краями рисунок с ребрами с четырьмя наклонами, представляющими цвета наклонами, является полным для экзистенциальной теории вещественных чисел, сложность класса по крайней мере так же сложен, как NP-полный.

За пределами максимальной степени и числа числа совпадений графа, хроматический индекс связан с линейной древовидностью la (G) графа G, минимальным количеством линейных лесов (непересекающихся объединений путей), на которые можно разбить ребра графа. Паросочетание - это особый вид линейного леса, и в обратном направлении любой линейный лес может быть 2-крашен по ребрам, поэтому для любого G следует, что la (G) ≤ χ ′ (G) ≤ 2 la (G). (назван в честь Джин Акияма ) утверждает, что la ⁡ (G) ≤ ⌈ Δ + 1 2 ⌉ {\ displaystyle \ mathop {\ mathrm {la}} (G) \ leq \ left \ lceil {\ frac {\ Delta +1} {2}} \ right \ rceil}{\ mathop {{\ mathrm {la}}}} (G) \ leq \ left \ lceil {\ frac {\ Delta + 1} {2}} \ right \ rceil , из которого более строго следует, что 2 la (G) - 2 ≤ χ ′ (G) ≤ 2 la (ГРАММ). Для графов максимальной степени три la (G) всегда ровно два, поэтому в этом случае оценка χ ′ (G) ≤ 2 la (G) совпадает с оценкой, данной теоремой Визинга.

Другие типы

Разбиение полное двудольного графа K 4,4 на три леса, показывающее, что он имеет древовидность три.

Число Туэ числа Граф - это количество цветов, необходимое для раскраски ребер, удовлетворяющей более строгому требованию, согласно которому в каждом пути четной длины первая и вторая половина пути образуют разные последовательность цветов.

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

Раскраска ребер списка - это задача, в которой задается граф, в котором задается каждый ребро списка цветов, и должен найти правильный цвет каждого ребра списка. Хроматический индекс списка графа G - это наименьшее число цветов со своим, независимо от того, как выбираются списки цветов для ребер, до тех пор, пока каждое ребро не менее k цветов в своем списке, окраска гарантированно будет возможно. Таким образом, хроматический индекс списка всегда по крайней мере хроматическому индексу. Гипотеза Диница по завершении частичных латинских квадратов может быть перефразирована как утверждение, что хроматическое число края списка полное двудольного графа K n, n равно его краевому хроматическому номеру n. Галвин (1995) разрешил гипотезу, доказав, в более общем смысле, что в каждом двудольном графе хроматический индекс и хроматический индекс списка равны. Предполагается, что равенство между хроматическим индексом и хроматическим индексом списка, даже в более общем смысле, для произвольных мультиграфов без петель; эта гипотеза остается открытой.

Многие другие обычно изучаемые варианты окраски вершин также были распространены на окраску краев. Например, полная раскраска ребер - это вариант раскраски ребер полный раскраски, правильная раскраска ребер, при которой каждая пара цветов должна быть представлена ​​по крайней мере одной парой дополнительных ребер и цель которой в том, чтобы максимально увеличить общее количество цветов. Сильная раскраска ребер - это вариант раскраски ребер сильной раскраски, раскраски ребер, при которой каждые два ребра со своими конечными точками должны иметь разные цвета. Сильная окраска краев имеет применение в схемах распределения каналов для беспроводных сетей.

Ациклическая окраска краев - это вариант ациклической окраски, окраска краев, для которой каждые два класса цветов образуют ациклический подграф (то есть лес). Ациклический хроматический индекс графа G {\ displaystyle G}G , обозначенный a '(G) {\ displaystyle a' (G)}a'(G), равен наименьшее количество цветов, необходимый для правильной ациклической окраски краев G {\ displaystyle G}G . Было высказано предположение, что a ′ (G) ≤ Δ + 2 {\ displaystyle a '(G) \ leq \ Delta +2}a'(G)\leq \Delta +2, где Δ {\ displaystyle \ Delta}\ Delta - максимальная степень G {\ displaystyle G}G . В настоящее время наиболее известная граница: a ′ (G) ≤ ⌈ 3.74 (Δ - 1) ⌉ {\ displaystyle a '(G) \ leq \ lceil 3.74 (\ Delta -1) \ rceil}a'(G)\leq \lceil 3.74(\Delta -1)\rceil . Проблема становится проще, когда G {\ displaystyle G}G имеет большой обхват. Более конкретно, существует константа c {\ displaystyle c}c такая, что если обхват G {\ displaystyle G}G составляет не менее c Δ журнал ⁡ Δ {\ displaystyle c \ Delta \ log \ Delta}c \ Delta \ log \ Delta , тогда a ′ (G) ≤ Δ + 2 {\ displaystyle a '(G) \ leq \ Delta +2}a'(G)\leq \Delta +2. Аналогичный результат - для всех ϵ>0 {\ displaystyle \ epsilon>0}\epsilon>0 существует g {\ displaystyle g}g такой, что если G {\ displaystyle G}G имеет обхват не менее g {\ displaystyle g}g , тогда a ′ (G) ≤ (1 + ϵ) Δ {\ displaystyle a '(G) \ leq (1 + \ epsilon) \ Delta}a'(G)\leq (1+\epsilon)\Delta .

Eppstein (2013) изучил раскраски трех ребер кубических графов с дополнительным свойством, что никакие два бихроматических цикла не имеют более одного ребра друг с другом. 62>рисунка графа на трехмерной целочисленной сетке с ребрами, параллельными осям координат, и каждой параллельной оси линией, как и в стандартной задаче раскраски по 3 ребрам, поиск раскраски этого типа явного типа ляется NP-полным.

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

Если 3-регулярный граф на поверхности окрашен в 3 цвета, его дуальный граф образует триангуляцию поверхности, которая также окрашена в цвет ребра (хотя не, как правило, правильно окрашенные края) таким образом, чтобы каждый треугольник имел по одному краю каждого цвета. Другие расцветки и ориентации триангуляции с локальными ограничениями на то, как располагаются в вершинах или гранях триангуляции. Например, прямоугольные подразделения (прямоугольные подразделения на меньшие три прямоугольники, с четырьмя прямоугольными подразделениями, встречающиеся в каждой вершине) могут быть разбиты комбинаторно с помощью «регулярной маркировки», двухкратной окраски реберангуляции, двойной подразделению, с ограничением, что ребра, инцидентные каждому вершины образуют четыре смежные подпоследовательности, в каждой из которых цвета одинаковы. Эта маркировка двойственна окраске самого прямоугольного подразделения, в котором вертикальные кромки имеют один цвет, а горизонтальные кромки - другой цвет. Аналогичные локальные ограничения на порядок, в котором цветные ребра могут появляться вокруг вершины, также могут использоваться для кодирования встраиваемых прямолинейных сеток плоских графов и трехмерных многогранников со сторонами, параллельными оси. Для каждого из этих трех типов регулярных разметок набор регулярных разметок фиксированного графа образует распределительную решетку, которую можно использовать для быстрого перечисления всех геометрических структур на основе одного и того же графа (например, всех осей- параллельные многогранники с одинаковым каркасом) или для поиска структур, удовлетворяющих дополнительным ограничениям.

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

Теорема Рамси касается проблемы k-раскраски ребер большого полного графа Kn, чтобы избежать создания монохроматических полных подграфов K s некоторого заданного размера s. Согласно теореме существует такое число R k (s), что при n ≥ R (s) такая раскраска невозможна. Например, R 2 (3) = 6, то есть, если ребра графа K 6 двухцветные, всегда будет монохроматический треугольник.

Путь в графе с краской цвета называется радужным путем, если на нем не повторяется ни один цвет. Граф называется радужным, если между любыми двумя парами вершин есть радужный путь. Раскраска ребер графа G в цвета 1... t - это интервал t раскраски, если используются все цвета, а цвета ребер, инцидентных каждой вершине G, различны и образуют интервал целых чисел.

Приложения

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

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

Gandham, Dawande Prakash (2005) изучают проблему планирования ссылок для временного разделения. множественного доступа протокол сетевых коммуникаций в сенсорных сетей как вариант окраски краев. В этой задаче необходимо выбрать временные интервалы для каждой сети связи, чтобы каждый узел сети мог связываться с каждым соседним узлом без помех. Использование сильной интервалов интервалов (и использование двух временных интервалов для каждого временного краев, по одному для каждого направления) решило бы проблему, но могло бы использовать больше временных интервалов, чем необходимо. Вместо этого они ищут направленное ориентированное графа, образованное удвоение каждого неориентированного ребра сети, с тем, что каждое ребро использует цвет, отличный от ребер, выходящих из v, и из соседей v. Эвристика для этой задачи, основанная на распределенном алгоритме (Δ + 1) -кратной раскраски вместе с фазой постобработки, которая перепланировывает края, которые могут мешать друг другу.

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

Открытые проблемы

Jensen Toft (1995) перечисляет 23 открытые проблемы, языски краев. К ним относится:

  • гипотеза Голдберга (1973) о том, что хроматический индекс и индексный индекс находится в пределах одного друг от друга, что позволяет аппроксимировать хроматический индекс в пределах одного цвета за полиномиальное время.
  • Несколько гипотез Якобсена и других о структуре критических графов для раскраски ребер, графов класса 2, что любой подграф либо имеет меньшую максимальную степень, либо имеет класс 1. Якобсен использует предположил, что все критические графы имеют нечетное количество вершин, но в итоге это было опровергнуто. Несколько других гипотез, ослабляющих эти гипотезу или ограничивающих количество вершин критических графов и критических мультиграфов, остаются открытыми.
  • Проблема Визинга о классификации максимальных степеней, которые возможны для плоских графов класса 2.
  • Гипотеза о переполнении подграфа А.Дж.В. Хилтона, утверждающая, что графы степень со степенью не ниже n / 3 либо к классу 1, либо содержат подграф с той же степенью Δ, что и исходный граф, и с нечетным числом k вершин, таких, что количество ребер в подграфе больше, чем Δ (k - 1) / 2, и аналогичная гипотеза Герберта Грётча и Пола Сеймура относительно плоских графов в место графов высокой степени.
  • Гипот Аманды Четвинд и Энтони Хилтона (возможно, восходящая к ранее работам Габриэля Эндрю Дирака ), что регулярные графы с четным числом вершин n и степенью не менее n / 2 класса к классу 1.
  • Гипотеза Клода Берже и Д. Р. Фулкерсон, что 6-регулярные мультиграфы, образованные удвоением каждого ребра 3-регулярного простого графа без мостов, могут быть окрашены ребрами в шесть цветов.
  • Гипотеза Фиорини и Уилсона о том, что каждые планарный граф без треугольников, кроме когтя K 1,3, не однозначно раскрашивается по 3 ребрам.
  • Гипотеза 2012 года, когда G нечетно d-реберно связно. Эта гипотеза является обобщением теоремы о четырех цветах, которая возникает при d = 3. Мария Чудновская, Кэтрин Эдвардс и Пол Сеймур доказали, что 8-регулярный плоский мультиграф имеет краевое хроматическое число 8.

Примечания

Ссылки

Последняя правка сделана 2021-05-18 06:56:35
Содержание доступно по лицензии CC BY-SA 3.0 (если не указано иное).
Обратная связь: support@alphapedia.ru
Соглашение
О проекте