Главная
Рёберная раскраска — назначение «цветов» рёбрам графа таким образом, что никакие два смежных ребра не имеют один и тот же цвет. Рёберная раскраска — это один из видов различных типов раскраски графов. Задача рёберной раскраски задаётся вопросом, можно ли раскрасить рёбра заданного графа максимум в k {displaystyle k} различных цветов для заданного значения k {displaystyle k} или для минимального возможного числа цветов. Минимальное требуемое число цветов для раскраски рёбер заданного графа называется хроматическим индексом графа. Например, рёбра графа на иллюстрации можно раскрасить в три цвета, но нельзя раскрасить в два, так что граф имеет хроматический индекс 3.
По теореме Визинга число цветов, необходимых для рёберной раскраски простого графа, либо равно максимальной степени вершин Δ {displaystyle Delta } , либо Δ + 1 {displaystyle Delta +1} . Для некоторых графов, таких как двудольные графы и планарные графы высокой степени, число цветов всегда равно Δ {displaystyle Delta } , а для мультиграфов число цветов может быть вплоть до 3 Δ / 2 {displaystyle 3{Delta }/2} . Существуют алгоритмы полиномиального времени, создающие оптимальную раскраску двудольных графов и раскраску простого не двудольного графа с числом цветов Δ + 1 {displaystyle {Delta }+1} . Однако, в общем случае, задача поиска оптимальной рёберной раскраски NP-полна и самый быстрый из известных алгоритмов для неё работает за экспоненциальное время. Изучались много вариантов задачи рёберной раскраски, в которых условия назначения цвета ребру должны удовлетворять другим условиям, а не сопряжённости. Задачи рёберной раскраски имеют приложения в задачах расписания и в назначении частоты в оптоволоконных сетях.
Примеры
Граф-цикл может быть раскрашен в 2 цвета если длина цикла чётна — просто используем поочерёдно 2 цвета последовательно проходя рёбра цикла. Однако в случае нечётной длины потребуется 3 цвета.
Рёбра полного графа K n {displaystyle K_{n}} с n {displaystyle n} вершинами могут быть раскрашены n − 1 {displaystyle n-1} цветами, если n {displaystyle n} чётно. Это специальный случай теоремы Бараньяи. Сойфер даёт следующее геометрическое построение раскраски в этом случае: разместим n {displaystyle n} точек в углах и в центре правильного ( n − 1 ) {displaystyle (n-1)} -угольника. Для каждого класса цвета выберем одно ребро, соединяющее центр и одну из вершин многоугольника, и все перпендикулярные ему рёбра, соединяющие пары вершин многоугольника. Однако если n {displaystyle n} нечётно, требуется n {displaystyle n} цветов — каждый цвет можно использовать только для раскраски ( n − 1 ) / 2 {displaystyle (n-1)/2} рёбер, 1 / n {displaystyle 1/n} -ю часть всех рёбер.
Некоторые авторы изучали рёберную раскраску нечётных графов, n {displaystyle n} -регулярных графов, в которых вершины представляют команды из ( n − 1 ) {displaystyle (n-1)} игроков из общего числа 2 n − 1 {displaystyle 2n-1} игроков, и в которых рёбра представляют возможные пары этих команд (с одним игроком «вне игры» для судейства). В случае, когда n = 3 {displaystyle n=3} получаем хорошо известный граф Петерсена. Как объясняет Биггс, задача (для n = 6 {displaystyle n=6} ) состоит в том, что игроки хотят найти такое расписание, что команды играют каждую из шести игр в разные дни недели, исключая воскресенье для всех игроков. В математической формулировке они хотят найти 6-цветную рёберную раскраску 6-регулярных графов O 6 {displaystyle O_{6}} . Когда n {displaystyle n} равно 3, 4 или 8, рёберная раскраска графа O n {displaystyle O_{n}} требует n + 1 {displaystyle n+1} цветов, но для 5, 6 и 7 нужно только n {displaystyle n} цветов.
Определения
Как и в случае вершинной раскраски, рёберная раскраска графа, если не указано явно другое, всегда предполагает, что двум смежным рёбрам назначаются различные цвета. Два ребра считаются смежными, если они имеют общую вершину. Рёберную раскраску графа G {displaystyle G} можно рассматривать как эквивалент вершинной раскраски рёберного графов L ( G ) {displaystyle L(G)} , графа, имеющего по вершине для каждого ребра графа G {displaystyle G} и по ребру для каждой пары смежных рёбер G {displaystyle G} .
Правильная раскраска k {displaystyle k} различными цветами называется (правильной) рёберной k {displaystyle k} -раскраской. Если для графа можно найти (правильную) рёберную k {displaystyle k} -раскраску, говорят, что он рёберно k {displaystyle k} -раскрашиваем. Наименьшее число цветов, необходимых для (правильной) рёберной раскраски графа G {displaystyle G} называется хроматическим индексом, или рёберным хроматическим числом χ ′ ( G ) {displaystyle chi {prime }(G)} . Хроматический индекс иногда записывается в виде χ 1 ( G ) {displaystyle chi _{1}(G)} . В этой нотации индекс показывает, что рёбра являются одномерными объектами. Граф является рёберно k {displaystyle k} -цветным, если хроматический индекс в точности равен k {displaystyle k} . Хроматический индекс не следует путать с хроматическим числом χ ( G ) {displaystyle chi (G)} или χ 0 ( G ) {displaystyle chi _{0}(G)} , минимальным числом цветов, необходимых для правильной раскраски вершин графа G {displaystyle G} .
Если не указано противное, все графы предполагаются простыми, в противоположность мультиграфам, у которых два и более ребра могут соединять одну и ту же пару вершин и в которых могут быть петли (ребро, у которого конечные вершины совпадают). Для большинства задач рёберной раскраски простые графы ведут себя отлично от мультиграфов и требуется дополнительная осторожность при распространении теорем рёберной раскраски с простых графов на мультиграфы.
Связь с паросочетаниями
Паросочетанием в графе G {displaystyle G} называется множество рёбер, никакие два из которых не смежны. Паросочетание называется совершенным, если его рёбра содержат все вершины графа и максимальным, если оно содержит максимально возможное число рёбер. В рёберной раскраске рёбра одного цвета должны быть несмежны, так что они образуют паросочетание. Таким образом, правильная рёберная раскраска — это то же самое, что и разложение графа на непересекающиеся паросочетания.
Если размер максимального паросочетания в заданном графе мал, необходимо большое число паросочетаний для покрытия всех рёбер графа. Выражаясь более формально, это объяснение предполагает, что если граф имеет m {displaystyle m} рёбер и если максимум β {displaystyle eta } рёбер могут принадлежать максимальному паросочетанию, то каждая рёберная раскраска графа должна содержать по меньшей мере m / β {displaystyle m/eta } различных цветов. Например, планарный граф с 16 вершинами, показанный на иллюстрации, имеет m = 24 {displaystyle m=24} рёбер. В этом графе нет совершенного паросочетания — если центральна вершина принадлежит паросочетанию, оставшиеся вершины можно разбить на три связных группы с числом вершин 4, 5, 5. Получившиеся подграфы с нечётным числом вершин не имеют совершенного паросочетания. Тем не менее, граф имеет максимальное паросочетание с семью рёбрами, так что β = 7 {displaystyle eta =7} . Поэтому число цветов, необходимых для рёберной раскраски графа, равно как минимум 24/7, а поскольку число цветов должно быть целым, получаем как минимум 4 цвета.
Для регулярных графов степени k {displaystyle k} , не имеющих совершенного паросочетания, эта нижняя граница может быть использована, чтобы показать, что необходимо как минимум k + 1 {displaystyle k+1} цветов. В частности, это верно для регулярных графов с нечётным числом вершин. Для таких графов, по лемме о рукопожатиях, k {displaystyle k} должно быть, в свою очередь, чётным. Однако неравенство χ ′ ⩾ m β {displaystyle chi {prime }geqslant meta } не полностью объясняет хроматический индекс произвольного регулярного графа, поскольку есть регулярные графы, имеющие совершенное паросочетание, но не рёберно k-раскрашиваемы. Например, граф Петерсена регулярен с m = 15 {displaystyle m=15} и с β = 5 {displaystyle eta =5} рёбрами в совершенном паросочетании, но он не имеет рёберной 3-раскраски.
Связь со степенью
Теорема Визинга
Рёберное хроматическое число графа G {displaystyle G} тесно связано с максимальной степенью Δ ( G ) {displaystyle {Delta }(G)} (максимальное число рёбер, смежных любой отдельной вершине графа G {displaystyle G} ). Ясно, что χ ′ ( G ) ≥ Δ ( G ) {displaystyle chi {prime }(G)geq {Delta }(G)} , так что если Δ {displaystyle {Delta }} различных рёбер содержат вершину v {displaystyle v} , то все эти рёбра должны быть раскрашены в различные цвета, что возможно только если имеется как минимум Δ {displaystyle Delta } цветов. Теорема Визинга (названа в честь Вадима Визинга, опубликовавшего её в 1964 году) утверждает, что эта граница почти точна — для любого графа рёберное хроматическое число равно либо Δ ( G ) {displaystyle {Delta }(G)} , либо Δ ( G ) + 1 {displaystyle Delta (G)+1} . Если χ ′ ( G ) = Δ ( G ) {displaystyle chi {prime }(G)={Delta }(G)} , говорят, что G имеет класс 1, в противном случае говорят о классе 2.
Любой двудольный граф имеет класс 1 и почти все случайные графы имеют класс 1. Однако задача проверки, имеет ли произвольный граф класс 1, является NP-полной задачей.
Визинг доказал, что планарные графы максимальной степени не менее восьми имеют класс 1 и высказал гипотезу, что то же самое верно для планарных графов степени 7 или 6. С другой стороны, существуют планарные графы с максимальной степенью от двух до пяти, имеющие класс 2. С тех пор гипотеза доказана для семи. Планарные графы без мостов, Кубические графы имеют класс 1, и это равносильно формулировке задачи о четырёх красках.
Регулярные графы
1-факторизация k-регулярного графа, то есть разложение рёбер графа в совершенные паросочетания — это то же самое, что и рёберная k-раскраска графа. Таким образом, регулярный граф имеет 1-факторизацию тогда и только тогда, когда он имеет класс 1. Частный случай, рёберная 3-цветная раскраска кубических (3-регулярных) графов иногда называется раскраской Тайта.
Не всякий регулярный граф имеет 1-факторизацию. Например, Граф Петерсена не имеет. Снарки определяются как графы, которые, подобно графу Петерсена, не имеют мостов, 3-регулярны и имеют класс 2.
Согласно теореме Кёнига, любой двудольный регулярный граф имеет 1-факторизацию. Теорема сформулирована ранее в терминах проективных конфигураций и доказана Эрнстом Штайницем.
Мультиграфы
Для мультиграфов, в которых несколько рёбер могут соединять те же самые две вершины, известны похожие на теорему Визинга, но более слабые результаты относительно рёберного хроматического числа χ ′ ( G ) {displaystyle chi {prime }(G)} , максимальной степени Δ ( G ) {displaystyle Delta (G)} и кратности μ ( G ) {displaystyle mu (G)} , максимального числа рёбер в связке параллельных рёбер (то есть имеющих одни и те же конечные вершины). В качестве простого примера, показывающего, что теорема Визинга не обобщается на мультиграфы, рассмотрим мультиграф Шеннона, мультиграф с тремя вершинами и тремя связками μ ( G ) {displaystyle mu (G)} параллельных рёбер, соединяющих каждую пару вершин. В этом примере: Δ ( G ) = 2 μ ( G ) {displaystyle Delta (G)=2mu (G)} — каждая вершина смежна только двум из трёх связок μ ( G ) {displaystyle mu (G)} параллельных рёбер, но рёберное хроматическое число равно 3 μ ( G ) {displaystyle 3mu (G)} (в графе 3 μ ( G ) {displaystyle 3mu (G)} рёбер и любые два ребра смежны, так что все рёбра должны быть раскрашены в разные цвета). В работе, навеянной теоремой Визинга, Сойфер и Шеннон показали, что это худший случай — χ ′ ( G ) ≤ ( 3 / 2 ) Δ ( G ) {displaystyle chi {prime }(G)leq (3/2)Delta (G)} для любого мультиграфа G {displaystyle G} . Вдобавок, для любого мультиграфа G {displaystyle G} χ ′ ( G ) ≤ Δ ( G ) + μ ( G ) {displaystyle chi {prime }(G)leq Delta (G)+mu (G)} . Это неравенство сводится к теореме Визинга для простых графов (для них μ ( G ) = 1 {displaystyle mu (G)=1} ).
Алгоритмы
Поскольку задача проверки, имеет ли граф класс 1, является NP-полной, не известно полиномиального по времени алгоритма рёберной раскраски для любого графа, дающего оптимальную раскраску. Однако разработан ряд алгоритмов, ослабляющих один или больше критериев: они работают на подмножестве графов, или они не всегда дают оптимальное число цветов, или они не всегда работают за полиномиальное время.
Оптимальная раскраска некоторых специальных классов графов
В случае двудольных графов или мультиграфов с максимальной степенью Δ {displaystyle Delta } , оптимальное число цветов равно в точности Δ {displaystyle Delta } . В 2001 году показано, что оптимальная рёберная раскраска этих графов может быть найдена почти за линейное время O ( m log Δ ) {displaystyle O(m,log Delta )} , где m {displaystyle m} — число рёбер в графе. Более простые, но несколько более медленные алгоритмы описаны ранее Коулом и Хопкрофтом и Алоном . Алгоритм Алона начинает с того, что делает граф регулярным без существенного увеличения степени или существенного увеличения размера путём слияния пар вершин, принадлежащих одной доле двудольного графа, а затем добавлением небольшого числа вершин и рёбер. После этого, если степень нечётна, Алон находит совершенное паросочетание за линейное время, назначает ему цвет и удаляет из графа, что приводит к графу чётной степени. Наконец, Алон использует наблюдение Габова, что выбор чередующихся подмножеств рёбер в эйлеровом цикле графа разделяет его на два регулярных подграфа, преобразуя задачу рёберной раскраски в две меньшие задачи, так что его алгоритм теперь решает эти две подзадачи рекурсивно. Полное время работы алгоритма оценивается как O ( m log m ) {displaystyle O(m,log m)} .
Для планарных графов с максимальной степенью Δ ≥ 7 {displaystyle {Delta }geq 7} оптимальное число цветов снова равно в точности Δ {displaystyle Delta } . При более строгом предположении, что Δ ≥ 9 {displaystyle {Delta }geq 9} , можно найти оптимальную рёберную раскраску за линейное время.
Алгоритмы, использующие больше цветов, чем нужно для оптимальной раскраски
Существуют алгоритмы полиномиального времени раскраски любого графа с Δ + 1 {displaystyle Delta +1} цветами, что соответствует границе, задаваемой теоремой Визинга.
Для мультиграфов в 1987 году существует следующий алгоритм (приписываемый Эли Упфалу): исходный мультиграф G {displaystyle G} делается эйлеровым путём добавления вершины, соединённой рёбрами со всеми вершинами нечётной степени; находится эйлеров путь, выбирается ориентация для этого пути; создаётся двудольный граф H {displaystyle H} , который содержит две копии каждой вершины графа G {displaystyle G} , по одной в каждой доле, и рёбрами из вершины u {displaystyle u} в левой доле в вершину v {displaystyle v} в правой доле, когда ориентированный путь имеет дугу из u {displaystyle u} в v {displaystyle v} в графе G {displaystyle G} . Далее применяется алгоритм рёберной раскраски двудольного графа для графа H {displaystyle H} . Каждый цвет в H {displaystyle H} соответствует множеству рёбер в G {displaystyle G} , которое образует подграф с максимальной степенью два, то есть несвязное объединение путей и циклов так, что для каждого цвета в H {displaystyle H} можно образовать три цвета в G {displaystyle G} . Время работы алгоритма ограничено временем раскраски двудольного графа O ( m log Δ ) {displaystyle O(m,log Delta )} при использовании алгоритма Коула, Оста и Ширра. Число цветов, которое использует этот алгоритм, не превосходит 3 ⌈ Δ 2 ⌉ {displaystyle 3leftlceil {frac {Delta }{2}} ight ceil } , что близко, но не совсем то же самое, что граница Шеннона ⌊ 3 Δ 2 ⌋ {displaystyle leftlfloor {frac {3Delta }{2}} ight floor } . То же самое можно сделать с помощью параллельного алгоритма напрямую. В той же статье Карлофф и Шмойс предлагают также алгоритм с линейным временем работы для раскраски мультиграфов максимум третьей степени четырьмя цветами (что удовлетворяет как границе Шеннона, так и границе Визинга). Этот алгоритм работает по похожим принципам — алгоритм также добавляет вершину, чтобы сделать граф эйлеровым, находит эйлеров путь, а затем выбирает чередующиеся множества рёбер в пути чтобы разбить граф на два подмножества максимальной степени два. Пути и чётные циклы каждого подмножества можно выкрасить двумя цветами (по два цвета на подграф). Следующим шагом раскрашиваются рёбра нечётных циклов, в которых по меньшей мере одно ребро может быть раскрашено одним из двух цветов, принадлежащих противоположному подграфу. Удаление этого ребра из нечётного цикла оставляет путь, который можно раскрасить двумя цветами.
Алгоритм жадной раскраски, выбирающий последовательно рёбра графа или мультиграфа и назначающий первый допустимый цвет, может иногда использовать 2 Δ − 1 {displaystyle 2{Delta }-1} цветов, что может почти вдвое превосходить необходимое число цветов. Однако он имеет то преимущество, что может быть использован в онлайн алгоритмах, ничего не знающих заранее о структуре графа. При указанных условиях его конкурентный коэффициент равен двум, и этот коэффициент оптимален — никакой другой алгоритм не может дать показатели лучше. Однако, если рёбра поступают в случайном порядке и исходный граф имеет степень как минимум логарифмическую, можно получить меньший конкурентный коэффициент.
Некоторые авторы высказали гипотезу, что дробный хроматический индекс любого мультиграфа (число, которое можно вычислить за полиномиальное время с помощью линейного программирования) отличается от хроматического индекса не более чем на единицу. Если гипотеза верна, можно будет находить число, не отличающееся от хроматического индекса более чем на единицу в случае мультиграфов, что соответствует теореме Визинга для простых графов. Хотя, в общем случае, гипотеза не доказана, известно, что она верна, если хроматический индекс не меньше чем Δ + Δ / 2 {displaystyle {Delta }+{sqrt {{Delta }/2}}} , точно так же, как в случае мультиграфов с достаточно большой кратностью.
Точные алгоритмы
Просто проверить, можно ли рёберно раскрасить граф одним или двумя цветами так, что первый нетривиальный случай раскраски — проверка, можно ли раскрасить граф рёберно тремя цветами. В 2009 году показано, что проверить, существует ли рёберная раскраска графа тремя цветами, можно за время O ( 1.344 n ) {displaystyle O(1.344^{n})} при использовании лишь полиномиального пространства. Хотя эти временные границы экспоненциальны, это существенно быстрее, чем алгоритм поиска грубой силой путём просмотра всех возможных раскрасок рёбер. Любой двусвязный 3-регулярный граф с n {displaystyle n} вершинами имеет O ( 2 n / 2 ) {displaystyle O(2^{n/2})} рёберных 3-раскрасок. И всех их можно перечислить за время O ( 2 n / 2 ) {displaystyle O(2^{n/2})} (чуть медленнее времени поиска одной раскраски). Как заметил Куперберг, граф призмы над n / 2 {displaystyle n/2} -угольником, имеет много раскрасок, что показывает, что эта граница точна.
При применении точных алгоритмов раскраски вершин рёберного графа, можно рёберно раскрасить оптимально любой граф с m {displaystyle m} рёбрами, независимо от числа необходимых цветов за время 2 m m O ( 1 ) {displaystyle 2^{m}m^{O(1)}} , используя экспоненциальное пространство, или за время O ( 2.2461 m ) {displaystyle O(2.2461^{m})} и полиномиальное пространство.
Поскольку задача рёберной раскраски является NP-полной даже для трёх цветов, вряд ли она поддаётся фиксированной параметризации по числу цветов. Однако задача поддаётся параметризации по другим параметрам. В частности, Чжоу, Накано и Нишизеки показали, что для графов с древесной шириной w {displaystyle w} оптимальная рёберная раскраска может быть найдена за время O ( n w ( 6 w ) w ( w + 1 ) / 2 ) {displaystyle O(nw(6w)^{w(w+1)/2})} , которое растёт экспоненциально от w {displaystyle w} , но лишь линейно от числа вершин графа n {displaystyle n} .
В 1991 году задача рёберной раскраски сформулирована как задача целочисленного программирования и проведены эксперименты использования пакетов целочисленного программирования для рёберной раскраски графов, однако какого-либо анализа сложности таких алгоритмом не приведено.
Дополнительные свойства
Граф однозначно рёберно k {displaystyle k} -раскрашиваем тогда и только тогда, когда существует только один способ разбить рёбра на k {displaystyle k} классов цветов, не считая k ! {displaystyle k!} возможных перестановок цветов. Для k ≠ 3 {displaystyle k eq 3} однозначно рёберно k {displaystyle k} -раскрашиваемыми графами являются только пути, циклы и звёзды, но для k = 3 {displaystyle k=3} могут быть однозначно рёберно k {displaystyle k} -раскрашиваемыми и другие графы. Любой однозначно рёберно 3-раскрашиваемый граф имеет ровно три гамильтоновых цикла (образованных путём удаления одного из трёх цветов), однако существуют 3-регулярные графы, имеющие три гамильтоновых цикла, но не имеющие однозначной рёберной 3-раскраски, как, например, обобщённые графы Петерсена G ( 6 n + 3 , 2 ) {displaystyle G(6n+3,2)} для n ≥ 2 {displaystyle ngeq 2} . Известен всего один непланарный однозначно рёберно 3-раскрашиваемый граф, это обобщённый Граф Петерсена G ( 9 , 2 ) {displaystyle G(9,2)} , и есть гипотеза, что других не существует.
Фолкман и Фалкерсон исследовали невозрастающие последовательности чисел m 1 , m 2 , m 3 , . . . {displaystyle m_{1},m_{2},m_{3},...} , для которых существует рёберная раскраска заданного графа G {displaystyle G} с m 1 {displaystyle m_{1}} рёбрами первого цвета, m 2 {displaystyle m_{2}} рёбрами второго цвета, и так далее. Они заметили, что если последовательность P {displaystyle P} подходит в описанном смысле, и если она лексикографически больше, чем последовательность Q {displaystyle Q} с той же суммой, то Q {displaystyle Q} тоже подходит. В случае, если P > Q {displaystyle P>Q} лексикографически, P {displaystyle P} может быть преобразована в Q {displaystyle Q} пошагово, уменьшая на каждом шаге одно из чисел m i {displaystyle m_{i}} на единицу и увеличивая другое, идущее далее число m j {displaystyle m_{j}} ( i < j {displaystyle i<j} ), на единицу. В терминах рёберной раскраски, мы начинаем с раскраски P {displaystyle P} , затем последовательно обмениваем цвет i {displaystyle i} и j {displaystyle j} в цепи Кемпе, наибольшем пути из рёбер, чередующих два цвета. В частности, любой граф имеет справедливую рёберную раскраску, рёберную раскраску с оптимальным числом цветов, в которой два класса цветов по размеру отличаются максимум на единицу.
Теорема де Брёйна — Эрдёша может быть использована для переноса многих свойств рёберной раскраски с конечных графов на бесконечные. Например, теоремы Шеннона и Визинга о связи степени графа с его хроматическим индексом обе легко обобщаются для бесконечных графов.
В 2011 году рассмотрена задача поиска рисунка данного кубического графа со свойствами, что все рёбра в рисунке имеют один из трёх различных углов наклона и никакие два ребра не лежат на одной прямой. Если такое представление графа на рисунке существует, ясно, что угол наклона рёбер можно рассматривать как цвет рёбер в трёхцветной раскраске графа. Например, рисунок K 3 , 3 {displaystyle K_{3,3}} в виде рёбер и длинных диагоналей правильного шестиугольника представляет рёберную 3-раскраску графа таким способом. Показано, что 3-регулярный двудольный граф с заданной раскраской Тайта имеет графическое представление такого вида тогда и только тогда, когда он рёберно k-связен. Для недвудольных графов условие чуть сложнее — заданная раскраска может быть представлена такого рода рисунком, если двойное двудольное покрытие графа 3-рёберно связно и если удаление двух одинаково раскрашенных рёбер приводит к недвудольному подграфу. Все эти условия легко проверить за полиномиальное время, однако задача проверки, имеет ли рёберно 4-раскрашенный 4-регулярный граф рисунок с четырьмя углами наклона, соответствующих цветам, является полной для теории существования вещественных чисел, того же класса сложности, что и NP-полнота.
Имея связь с максимальной степенью и максимальным числом паросочетаний графа, хроматический индекс тесно связан также с древесностью l a ( G ) {displaystyle la(G)} графа G {displaystyle G} , минимальному числу линейных лесов (несвязному объединению путей), на которые рёбра графа могут быть разбиты. Паросочетание — это специальный вид линейного леса, но, с другой стороны, любой линейный лес может быть рёберно 2-раскрашен, так что для любого G {displaystyle G} l a ( G ) ≤ χ ′ ( G ) ≤ 2 l a ( G ) {displaystyle la(G)leq chi {prime }(G)leq 2la(G)} . Гипотеза Акияма утверждает, что l a ( G ) ≤ ⌈ Δ + 1 2 ⌉ {displaystyle mathop {mathrm {la} } (G)leq leftlceil {frac {{Delta }+1}{2}} ight ceil } , откуда следовало бы более сильное неравенство 2 l a ( G ) − 2 ≤ χ ′ ( G ) ≤ 2 l a ( G ) {displaystyle 2la(G)-2leq chi {prime }(G)leq 2la(G)} . Для графов максимальной степени три l a ( G ) {displaystyle la(G)} всегда в точности равно двум, так что ограничение χ ′ ( G ) ≤ 2 l a ( G ) {displaystyle chi {prime }(G)leq 2la(G)} соответствует границе, следующей из теоремы Визинга.
Другие типы рёберной раскраски
Число Туэ графа — это число цветов, нужных для рёберной раскраски, удовлетворяющей более сильным требованиям, чем любой путь чётной длины, а именно первая и вторая половина пути должны образовывать различные последовательности цветов.
Древесность графа — это минимальное число цветов, необходимых для раскраски таким образом, что рёбра любого цвета не содержат циклов (а не как в стандартной задаче раскраски — рёбра одного цвета несмежны). Таким образом, это минимальное число элементов леса, в которые можно разложить рёбра графа. В отличие от хроматического числа, ширина леса может быть вычислена за полиномиальное время.
Задача предписанной раскраски рёбер — это задача, в которой для заданного графа, для каждой дуги которого задан список цветов, нужно найти подходящую раскраску рёбер, в которой каждый цвет берётся из заданного списка. Предписанный хроматический индекс графа G {displaystyle G} — это наименьшее число k {displaystyle k} , при котором независимо от выбора списков цветов для рёбер, если для каждого ребра задано не менее k {displaystyle k} цветов, раскраска гарантированно существует. Предписанный хроматический индекс всегда не меньше хроматического числа. Гипотезу Диница о заполнении частичных латинских квадратов можно перефразировать как утверждение, что предписанное рёберное хроматическое число полного двудольного графа K n , n {displaystyle K_{n,n}} равно его рёберному хроматическому числу n {displaystyle n} . В 1995 году гипотеза разрешена, притом доказано более сильное утверждение, что для любого двудольного графа хроматический индекс и предписанный хроматический индекс равны. Высказана ещё более общая гипотеза о равенстве хроматического числа и предписанного хроматического числа для произвольных мультиграфов без петель. Эта гипотеза остаётся открытой.
Много изучавшихся вариаций задачи о вершинной раскраске распространены на рёберную раскраску. Например, задача о полной рёберной раскраске является вариантом полной раскраски, правильной раскраски вершин, при которой любая пара цветов должна присутствовать хотя бы раз в множестве сопряжённых вершин, и задача состоит в максимизации общего числа цветов. Строгая рёберная раскраска — это рёберный вариант строгой раскраски, при которой любые два ребра со смежными конечными вершинами должны иметь различные цвета. Строгая рёберная раскраска применяется в схеме размещения каналов для беспроводных сетей. Ацикличная рёберная раскраска — это вариант ациклической раскраски, в которой любые два цвета формируют ацикличный подграф (то есть, лес).
В 2008 году изучена рёберная 3-раскраска кубических графов с дополнительным свойством, что никакие два двуцветных цикла не имеют более чем одно общее ребро, в частности показано, что существование такой раскраски эквивалентно существованию рисунка графа на трёхмерной целой решётке с рёбрами на прямых, параллельных осям координат, и каждая такая прямая содержит максимум две вершины. Однако, как и в случае стандартной задачи рёберной 3-раскраски, поиск раскраски этого типа является NP-полной задачей.
Тотальная раскраска — это вид раскраски, комбинирующий вершинную и рёберную раскраски, при которой раскрашиваются как вершины, так и рёбра. Любая вершина и ребро, концом которого она является, или два смежных ребра должны иметь различные цвета, так же как и две смежных вершины. Существует гипотеза (комбинирующая теорему Визинга и теорему Брукса), что любой граф имеет тотальную раскраску, в которой число цветов не превосходит максимальной степени плюс два. Гипотеза не доказана.
Если 3-регулярный граф на поверхности рёберно 3-раскрашиваем, его двойственный граф образует триангуляцию поверхности, которая также рёберно раскрашиваема (хотя, в общем случае, рёберная раскраска неправильна) в том смысле, что каждый треугольник раскрашен в три цвета — по ребру на цвет. Другие раскраски и ориентации треугольников, вместе с другими локальными ограничениями, каким образом цвета распределяются по вершинам или граням триангуляции, можно использовать для кодировки некоторых типов геометрических объектов. Например, прямоугольные дробления (части прямоугольного разбиения прямоугольника на более мелкие прямоугольники, при этом в каждой точке встречаются три прямоугольника) можно описать комбинаторно «регулярной маркировкой», двуцветной раскраской рёбер триангуляционного графа, двойственного прямоугольному дроблению, с ограничением, что рёбра, смежные каждой вершине, образуют четыре группы рёбер идущих (по часовой стрелке) подряд. Внутри каждой группы рёбра выкрашены в один цвет и имеют одно направление. Эта маркировка двойственна раскраске самого дробления, в которой вертикальные рёбра имеют один цвет, а горизонтальные — другой. Похожие локальные ограничения на порядок следования раскрашенных рёбер для вершины могут быть использованы для кодирования вложения планарных графов в сетку, образованную прямыми линиями, и трёхмерных многогранников с гранями, параллельными координатным плоскостям. Для каждого из этих трёх типов регулярной маркировки множество регулярных маркировок образует дистрибутивную решётку, которая может быть использована для быстрого перечисления всех геометрических структур, основанных на том же графе, или найти структуру, удовлетворяющую дополнительным ограничениям.
Детерминированный конечный автомат может быть представлен как ориентированный граф, в котором каждая вершина имеет одну и ту же полустепень исхода вершин и в котором рёбра d {displaystyle d} -раскрашены таким образом, что любые два ребра с одной и той же начальной вершиной имеют различные цвета. Задача о раскраске дорог — это задача рёберной раскраски направленного графа с одной и той же полустепенью исхода, такой что результирующий автомат имеет синхронизирующее слово. Трахтман(Трахтман 2009) решил задачу раскраски дорог, доказав, что такая раскраска может быть найдена, если заданный граф сильно связен и апериодичен.
Теорема Рамсея касается задачи k {displaystyle k} -раскраски рёбер большого полного графа K n {displaystyle K_{n}} с целью избежать создания одноцветных полных подграфов K s {displaystyle K_{s}} некоторого заданного размера s {displaystyle s} . Согласно теореме, существует число R k ( s ) {displaystyle R_{k}(s)} такое, что при n ≥ R ( s ) {displaystyle ngeq R(s)} указанная раскраска невозможна. Например, R 2 ( 3 ) = 6 {displaystyle R_{2}(3)=6} , что означает, что если рёбра графа K 6 {displaystyle K_{6}} 2-раскрашены, всегда найдётся монохромный треугольник.
Приложения
Рёберная раскраска полных графов может быть использована для разбиения расписания в круговых турнирах в несколько кругов, так чтобы каждая пара играла в одном из кругов. В этом приложении вершины соответствуют участникам турнира, а рёбра соответствуют играм. Цвет рёбер ответствует кругам турнира. Похожая техника раскраски может быть использована для составления других спортивных расписаний, в которых не обязательно каждый играет с каждым. Например, в национальной футбольной лиге (США, Американский футбол), пары команд, которые будут играть в данном году, определены результатами команд в предыдущем году, а алгоритм рёберной раскраски применяется к графу, образованному множеством этих пар с целью распределить игры на выходные, по которым игры происходят. Для этого приложения теорема Визинга означает, что не имеет значения, какое множество пар выбрано (если никакие две команды не играют дважды в сезон), всегда имеется возможность найти расписание, которое захватывает максимум одни лишние выходные (по сравнению с числом игр одной команды).
Расписание для открытой линии — это задача планирования процесса производства, в котором имеется множество объектов, требующих изготовления. Каждый объект должен пройти некоторые процедуры (в любом порядке) и каждая работа должна быть проведена на определённой машине, при этом машина одновременно может выполнять только одну процедуру. Если все работы имеют одну и ту же длину, то задачу можно поставить как рёберную раскраску двудольного графа, в которой вершины одной доли представляют объекты, которые следует изготовить, а вершины другой доли графа представляют обрабатывающие машины. Рёбра представляют работы, которые необходимо выполнить, а цвета представляют временные интервалы, в которых работы должны быть выполнены. Поскольку рёберная раскраска двудольного графа может быть выполнена за полиномиальное время, то это же верно и для указанного специального случая расписания для открытой линии.
В 2005 году изучена задача расписания соединения для протокола связи множественного доступа с разделением по времени в беспроводных сенсорных сетях, как вариант рёберной раскраски. В этой задаче нужно выбрать временные промежутки для рёбер беспроволочной сети так, что каждая вершина сети может связываться с соседними вершинами без взаимного влияния. Использование строгой рёберной раскраски (при двух временных промежутках для каждого цвета рёбер, по одному в каждом направлении) решает задачу, но число используемых промежутком может оказаться больше, чем необходимо. Вместо этого они искали раскраску ориентированного графа, образованного заменой каждого неориентированного ребра двумя ориентированными дугами, при этом каждая дуга u v {displaystyle uv} должна иметь цвет, отличный от цветов дуг, исходящих из v {displaystyle v} и соседей v {displaystyle v} . Они предложили эвристический алгоритм для решения этой задачи, основанный на распределённом алгоритме для рёберного ( Δ + 1 ) {displaystyle ({Delta }+1)} -раскрашивания с последующим процессом исправления расписания для удаления возможных взаимных помех.
В волоконно-оптической связи задача назначения цвета — это задача назначения частоты света паре вершин, для которых необходима связь, и путей через оптоволоконную сеть для каждой пары, при этом существует ограничение, что никаких два пути не используют для общего сегмента волокна одну и ту же частоту. Путям, проходящим через один и тот же коммутатор, но не через один и тот же сегмент оптоволокна, разрешается иметь одну и ту же частоту. Если сеть построена в виде звезды с единственным коммутатором в центре, который соединён отдельным оптоволокном с каждой вершиной сети, задача назначения цвета может быть смоделирована в точности как задача раскраски рёбер графа или мультиграфа, в котором коммуникационные узлы образуют вершины графа, пары узлов, которым необходим обмен информацией, образуют дуги, а частота, которую можно использовать для каждой пары узлов, соответствуют раскраске дуг в задаче раскраски. Для сетей связи, имеющих более общую топологию дерева, локальные решения задач назначения цвета пути для звёзд, образованных каждым коммуникатором, могут быть собраны вместе, чтобы получить единое глобальное решение.
Открытые проблемы
Йенсен и Тофт перечислили 23 открытых проблемы, касающихся рёберной раскраски. Они включают:
- Гипотеза Голдберга, что хроматический индекс и дробный индекс отличаются не более чем на единицу, что позволило бы аппроксимировать хроматический индекс с ошибкой в один цвет за полиномиальное время.
- Некоторые гипотезы Якобсена (Jakobsen) и других авторов о структуре критических графов для рёберной раскраски графов класса 2 таких, что любой подграф либо имеет меньшую максимальную степень, либо имеет класс 1. Якобсен первоначально предположил, что все критические графы имеют нечётное число вершин, но, в конечном счёте, предположение опровергнуто. Несколько других гипотез, более слабых чем эта, а также гипотезы, ограничивающие число вершин критических графов и критических мультиграфов, остаются открытыми.
- Задача Визинга классификации максимальных степеней, что возможно для планарных графов класса 2.
- Гипотеза о переполненных графах Хилтона (A. J. W. Hilton), утверждающая, что граф со степенью не меньшей n / 3 {displaystyle n/3} либо имеет класс 1, либо содержит подграф той же степени Δ {displaystyle Delta } , что и исходный граф, а для нечётного числа вершин k {displaystyle k} такой, что число рёбер подграфа больше Δ ( k − 1 ) / 2 {displaystyle Delta (k-1)/2} . Близка к этой гипотеза Герберта Грёча и Пола Сеймура относительно планарных графов вместо графов высокой степени.
- Гипотеза Четвинда (Chetwynd) и Хилтона (Hilton) (возможно, имеющая корни в более ранних работах Дирака), что регулярный граф с чётным числом вершин n {displaystyle n} и степенью как минимум n / 2 {displaystyle n/2} имеет класс 1.
- Гипотеза Клауди Бержа и Делберта Фалкерсона, что 6-регулярные мультиграфы, образованные удвоением каждого ребра 3-регулярного простого графа без мостов, можно раскрасить шестью цветами.
- Гипотеза Фьорини и Вилсона, что любые планарные графы без треугольников, отличные от клешни K1,3, не раскрашиваемы рёберно однозначно в 3 цвета.
Примечательна также более современная гипотеза: если G {displaystyle G} является d {displaystyle d} -регулярным планарным мультиграфом, то G {displaystyle G} рёберно d {displaystyle d} -раскрашиваем тогда и только тогда, когда G {displaystyle G} нечётно рёберно d {displaystyle d} -связен. Эту гипотезу можно рассматривать как обобщение проблемы четырёх красок для d = 3 {displaystyle d=3} . Мария Чудновская, Катерина Эдвардс (Katherine Edwards) и Пол Сеймур доказали, что 8-регулярный планарный мультиграф имеет рёберное хроматическое число 8.