Вам бонус- начислено 1 монета за дневную активность. Сейчас у вас 1 монета

Раскраска графов Примеры и применение

Лекция



Привет, сегодня поговорим про раскраска графов применение, обещаю рассказать все что знаю. Для того чтобы лучше понимать что такое раскраска графов применение , настоятельно рекомендую прочитать все из категории Дискретная математика. Теория множеств . Теория графов . Комбинаторика..


Раскраска графов Примеры и применение

Корректная раскраска вершин графа наименьшим набором цветов - тремя.

В теории графов, раскраска графов является частным случаем разметки графов. При раскраске элементам графа ставятся в соответствие метки с учетом определенных ограничений; эти метки традиционно называются “цветами”. В простейшем случае, такой способ окраски вершин графа, при котором любым двум смежным вершинам соответствуют разные цвета, называетсяраскраской вершин. Аналогично, раскраска ребер присваивает цвет каждому ребру так, чтобы любые два смежных ребра имели разные цвета.[1] Наконец, раскраска областей планарного графа назначает цвет каждой области, так, что каждые две области, имеющие общую границу, не могут иметь одинаковый цвет.

Раскраска вершин – главная проблема раскраски графов, все остальные задачи в этой области могут быть перенесены на эту модель. Например, раскраска ребер графа - это раскраска вершин его реберного графа, а раскраска областей планарного графа – это раскраска вершин двойственного графа.[1] Тем не менее, другие проблемы раскраски графов часто ставятся и решаются в изначальной постановке. Причина этого частично заключается в том, что это дает лучшее представление о происходящем и более показательно, а частично из-за того, что некоторые задачи таким образом решать удобнее (например, раскраска ребер).

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

Раскраска графов находит применение и во многих практических областях, а не только в теоретических задачах. Помимо классических типов проблем, различные ограничения могут также быть наложены на граф, на способ присвоения цветов или на сами цвета. Этот метод, например, используется в популярной головоломкеСудоку. В этой области все еще ведутся активные исследования.

Примечание: Многие термины, данные в этой статье, определены в Глоссарии теории графов.

Содержание

  • 1 История
  • 2 Определение и терминология
    • 2.1 Раскраска вершин
    • 2.2 Хроматический многочлен
    • 2.3 Реберная раскраска
    • 2.4 Тотальная раскраска
  • 3 Свойства
    • 3.1 Свойства хроматического многочлена
    • 3.2 Ограничения на хроматическое число
    • 3.3 Графы с большим хроматическим числом
    • 3.4 Ограничения на хроматический индекс
    • 3.5 Другие свойства
    • 3.6 Открытые вопросы
  • 4 Алгоритмы раскраски
    • 4.1 Полиномиальные алгоритмы
    • 4.2 Точные алгоритмы
    • 4.3 Сжатие
    • 4.4 Жадная раскраска
    • 4.5 Параллельные и распределенные алгоритмы
    • 4.6 Децентрализованные алгоритмы
    • 4.7 Сложность вычислений
  • 5 Применение
    • 5.1 Планирование
    • 5.2 Распределение регистров
    • 5.3 Цифровые водяные знаки
    • 5.4 Другие применения
  • 6 Примечания
  • 7 Источники

История

Первые результаты были получены для плоских графов в задаче раскрашивания карт. Пытаясь раскрасить карту округов Англии, Францис Гутри сформулировалпроблему четырех красок, отметив, что четырех цветов достаточно, чтобы раскрасить карту так, чтобы любые два смежных региона имели разные цвета. Его брат передал вопрос своему учителю по математике, Огастесу де Моргану, который упомянул о нем в своем письме Уильяму Гамильтону в 1852 году. Артур Кэли поднял эту проблему на встрече Лондонского математического сообщества в 1878 году. В том же году Тэйтом было предложено первое решение этой задачи. Раскраску вершин первоначального графа он свел к раскраске ребер двойственного графа и предположил, что эта задача всегда имеет решение.[2] В 1880 году Альфред Кемпеопубликовал бумагу, в которой утверждалось, что ему удалось установить результат, и на десятилетие проблема четырех цветов считалась решенной. За это достижение Кемпе был избран членом Лондонского Королевского общества и позже — президентом Лондонского математического сообщества.[3]

В 1890 году Хивуд отметил, что аргументы, приведенные Кемпе, были неверными. Тем не менее, в этой статье он доказал теорему пяти красок, показав, что любая плоская карта может быть раскрашена не более, чем пятью цветами. При этом он опирался на идеи Кемпе. В следующем столетии было разработано большое количество теорий в попытках уменьшить минимальное число цветов. Теорема четырех красок была окончательно доказана в 1977 году учеными Кеннетом Аппелем иВольфгангом Хакеном.Идея доказательства во многом опиралась на идеи Хивуда и Кемпе и игнорировала большинство промежуточных исследований.[4] Доказательство теоремы четырех цветов является одним из первых доказательств, в которых был использован компьютер.

В 1912 году Джордж Дэвид Биркхоф предложил использовать хроматический многочлен для изучения проблем раскраски, которые он обобщил на многочлен Тутте, являющийся важной частью в алгебраической теории графов. Кемпе в 1879 году уже обращал внимание на общий случай, когда граф не являлся плоским.[5] Много результатов обобщений раскраски плоских графов на поверхности более высоких порядков появилось в начале 20 века.

В 1960 году Клод Бердж сформулировал другое представление о раскраске графов, утверждение о совершенных графах, мотивированное информационно-теоретическим концептом, названным нулевой ошибкой емкости графа, представленным Шенноном. Утверждение оставалось неподтвержденным на протяжении 40 лет, пока не было доказано как знаменитая теорема о совершенных графах математиками Чудновской, Робертсоном, Сэймуром и Томасом в 2002 году.

Раскраска графов начала изучаться как алгоритмическая проблема с 1970-х годов: определение хроматического числа — одна из 21 NP-полных задач Карпа с 1972 года. И примерно в то же время были разработаны разнообразные алгоритмы на базе поиска с возвратом и рекурсивного удаления-сжатия Зыкова.[6] С 1981 года раскраска графа применяется для распределения регистров в компиляторах.[7]

Определение и терминология

Раскраска вершин

Раскраска графов Примеры и применение

Этот граф может быть раскрашен 3 цветами 12 способами.

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

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

Раскраска с использованием Раскраска графов Примеры и применение цветов называется Раскраска графов Примеры и применение-раскраской. Наименьшее число цветов, необходимое для раскраски графа Раскраска графов Примеры и применение называется его хроматическим числом и часто записывается как Раскраска графов Примеры и применение. Иногда используется Раскраска графов Примеры и применение, с тех пор как Раскраска графов Примеры и применение обозначает Эйлерову характеристику. Подмножество вершин, выделенных одним цветом, называется цветовым классом, каждый такой класс формирует независимый набор. Таким образом, Раскраска графов Примеры и применение-раскраска - это то же самое, что и разделение вершин на Раскраска графов Примеры и применение независимых наборов.[1]

Хроматический многочлен[править ]

Хроматическое число

Хроматический многочлен - это функция Раскраска графов Примеры и применение, которая считает число t-раскрасок Раскраска графов Примеры и применение. Из названия следует, что для заданных Раскраска графов Примеры и применение эта функция - полином, зависящий от t. Этот факт был обнаружен Биркгофом и Льюисом при попытке доказать гипотезу четырех красок.[8]

Раскраска графов Примеры и применение

Все не изоморфныеграфы из 3 вершин и их хроматические многочлены. Пустой графE3 (красный) допускает раскраску одним цветом, остальные - нет. Зеленый граф может быть раскрашен 3 цветами 12 способами.

Например, граф на изображении справа может может быть раскрашен 12 способами с использованием 3 цветов. Двумя цветами он не может быть окрашен в принципе. Используя 4 цвета, мы получаем 24+4*12 = 72 вариантов раскраски: при использовании всех 4 цветов, есть 4! = 24 корректных способа (каждое присвоение 4 цветов для любого графа из 4 вершин является корректным); и для каждых 3 цветов из этих 4 есть 12 способов раскраски. Тогда, для графа в примере, таблица чисел корректных раскрасок будет начинаться так:

Доступное число цветов 1 2 3 4
Количество способов раскраски 0 0 12 72

Для графа в примере, Раскраска графов Примеры и применение, и конечно, Раскраска графов Примеры и применение.

Хроматический многочлен содержит по меньшей мере столько же информации о раскрашиваемости Раскраска графов Примеры и применение, сколько и хроматическое число. В самом деле, Раскраска графов Примеры и применение - наименьшее целое положительное число, не являющееся корнем хроматического многочлена.

Раскраска графов Примеры и применение

Хроматические многочлены для некоторых графов
Треугольный Раскраска графов Примеры и применение Раскраска графов Примеры и применение
Полный граф Раскраска графов Примеры и применение Раскраска графов Примеры и применение
Дерево с Раскраска графов Примеры и применение ребрами Раскраска графов Примеры и применение
Цикл Раскраска графов Примеры и применение Раскраска графов Примеры и применение
Граф Петерсена Раскраска графов Примеры и применение

Реберная раскраска

Реберная раскраска

Реберная раскраска графа подразумевает под собой назначение цветов ребрам так, что никакие два ребра одного цвета не принадлежат одной вершине. Об этом говорит сайт https://intellect.icu . Эта задача эквивалентна разделению множества граней на множества независимых граней. Наименьшее число цветов, необходимое для реберной раскраски графа Раскраска графов Примеры и применение - это его его хроматический индекс, или реберное хроматическое число, Раскраска графов Примеры и применение.

Тотальная раскраска

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

Свойства

Свойства хроматического многочлена

  • Если Раскраска графов Примеры и применение - пустой граф [9],

Раскраска графов Примеры и применение

  • Если граф Раскраска графов Примеры и применение - объединение непересекающихся подграфов Раскраска графов Примеры и применение и Раскраска графов Примеры и применение [9],

Раскраска графов Примеры и применение

  • Если в Раскраска графов Примеры и применение есть петля [9],

Раскраска графов Примеры и применение

Ограничения на хроматическое число

  • Назначение всем вершинам разных цветов всегда дает правильную раскраску, так что

Раскраска графов Примеры и применение

  • Единственный вид графов, которые могут быть раскрашены одним цветом - это нулевые графы.
  • Полный граф Раскраска графов Примеры и применение, состоящий из Раскраска графов Примеры и применение вершин требует Раскраска графов Примеры и применение цветов.
  • При оптимальной раскраске должно быть по меньшей мере одно ребро из Раскраска графов Примеры и применение ребер графа между каждыми двумя цветовыми классами, так что [10]

Раскраска графов Примеры и применение

  • Если Раскраска графов Примеры и применение является объединением непересекающихся подграфов Раскраска графов Примеры и применение и Раскраска графов Примеры и применение, то

Раскраска графов Примеры и применение

  • Если Раскраска графов Примеры и применение содержит клики размера k, тогда необходимо минимум k цветов для раскраски этой клики, другими словами хроматическое число больше, либо равно размерности клики:

Раскраска графов Примеры и применение

Для интервальных графов это ограничение точно.

  • По теореме 4 цветов, любой плоский граф может быть раскрашен 4 цветами.
  • 2-раскрашиваемые графы - это двудольные графы, в том числе и деревья.

Граф Раскраска графов Примеры и применение является двудольным в том и только в том случае, если он не содержит циклов нечетной длины.[9]

  • Жадная раскраска показывает, что любой граф может быть окрашен при использовании на один цвет больше, чем его максимальная степень вершины [10],

Раскраска графов Примеры и применение

  • Полные графы имеют Раскраска графов Примеры и применение и Раскраска графов Примеры и применение, графы-циклы имеют Раскраска графов Примеры и применение и Раскраска графов Примеры и применение, так что для них это ограничение является наилучшим, во всех других случаях, ограничение может быть улучшено; Теорема Брукса[11] утверждает, что

Теорема Брукса: Раскраска графов Примеры и применение для связанного, простого графа Раскраска графов Примеры и применение, если Раскраска графов Примеры и применение не является ни полный графом, ни графов-циклом.

Графы с большим хроматическим числом

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

Теорема Мыцельского(Александр Зыков 1949, Jan Mycielski 1955): Существуют графы без треугольников со сколь угодно большими хроматическими числами.

  • Из теоремы Брукса, графы с большим хроматическим числом должны иметь высокую максимальную степень вершины. Другое локальное условие, из-за которого хроматическое число может быть большим - это наличие большого клика. Но раскрашиваемость графа зависит не только от локальных условий: граф с большимобхватом локально выглядит как дерево, так все циклы длинные, но его хроматическое число не равно 2:

Теорема Эрдоса: Существуют графы со сколь угодно большим обхватом и хроматическим числом. [10]

Ограничения на хроматический индекс

  • Реберная раскраска Раскраска графов Примеры и применение - это раскраска вершин его линейного графа Раскраска графов Примеры и применение, и наоборот. То есть,

Раскраска графов Примеры и применение

  • Более того [12],

Теорема Кенига: Раскраска графов Примеры и применение, если Раскраска графов Примеры и применение - двудольный.

  • В общем случае, связь намного сильнее, чем дает теорема Брукса для раскраски вершин [12]:

Теорема Визинга: Граф с максимальной степенью вершины Раскраска графов Примеры и применение имеет реберное хроматическое число Раскраска графов Примеры и применение или Раскраска графов Примеры и применение.

Другие свойства

  • Граф является k-хроматическим тогда и только тогда, когда он имеет ациклическую ориентацию, для которой длина наибольшего пути равна k. Это это было доказано в теореме Галлаи-Хассе-Роя-Витавера.[13]
  • Для плоских графов, раскраска вершин эквивалентна везде-ненулевому потоку.
  • Об бесконечных графах известно намного меньше. Ниже приведены два результата для раскраски бесконечных графов.
  1. Если все конечные подграфы бесконечного графа Раскраска графов Примеры и применение k-хроматические, то и Раскраска графов Примеры и применение тоже является k-хроматическим, по предположению аксиомы выбора. Это - формулировка теоремы Дэ Брейна–Эрдуша.[14]
  2. Если граф допускает полную n-раскраску для любого Раскраска графов Примеры и применение, то он допускает бесконечную полную раскраску.[15]

Открытые вопросы

Хроматическое число плоскости, в которой две точки являются смежными, если между ними единичное расстояние, неизвестно. Оно может быть равным 4, 5, 6, или 7. Другие открытые вопросы о хроматическом числе графов включают в себя гипотезу Хардвигера, утверждающую, что любой граф с хроматическим числом k имеет полный граф из k вершин, как его минор, Гипотезу Эрдуша–Фабера–Ловаса, которая ограничивает хроматическое число полных графов, которые имеют ровно одну общую вершину для каждой пары графов, и гипотезу Альбертсона о том, что среди k-хроматических графов полными являются те, которые имеют наименьшее число пересечений.

Когда Бирков и Льюис представили хроматический многочлен в их попытке решить теорему четырех цветов, они утверждали, что для плоских графов Раскраска графов Примеры и применение, многочлен Раскраска графов Примеры и применение не имеет нулей в области Раскраска графов Примеры и применение. Хотя известно, что такой хроматический многочлен не имеет нулей в области Раскраска графов Примеры и применение, и что Раскраска графов Примеры и применение, их утверждение остается недоказанным. Так же остается открытым вопрос, как отличать графы с одинаковым хроматическим многочленом, и как определять, что многочлен является хроматическим.

Алгоритмы раскраски

Полиномиальные алгоритмы

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

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

Алгоритм полного перебора для случая k-раскраски рассматривает все Раскраска графов Примеры и применение комбинаций расстановки цветов в графе с n вершинами и проверяет их на корректность. Чтобы вычислить хроматическое число и хроматический полином данный алгоритм рассматривает каждое k, и может работать эффективно только для небольших графов.

Используя динамическое программирование и оценку размера наибольшего независимого множества в графе возможность k-раскраски может быть разрешена за время Раскраска графов Примеры и применение [16]. Известны более быстрые алгоритмы для 3- и 4-раскрасок, сходящиеся за время Раскраска графов Примеры и применение [17] и Раскраска графов Примеры и применение [18] соответственно.

Сжатие

Сжатие Раскраска графов Примеры и применение графа Раскраска графов Примеры и применение — это граф, полученный отождествлением вершин Раскраска графов Примеры и применение и Раскраска графов Примеры и применение, удаление соединяющих их ребер, замена на одну вершину Раскраска графов Примеры и применение, куда перенаправляются ребра инцидентные вершинам Раскраска графов Примеры и применение и Раскраска графов Примеры и применение. Эта операция играет важную роль в анализе раскраски графов.

Хроматическое число удовлетворяет рекуррентному соотношению:

Раскраска графов Примеры и применение,

где Раскраска графов Примеры и применение и Раскраска графов Примеры и применение несмежные вершины, Раскраска графов Примеры и применение граф с добавленным ребром Раскраска графов Примеры и применение. Некоторые алгоритмы основаны на данном соотношении, выдавая как результат дерево, иногда называемое деревом Зыкова. Время выполнения зависит от метода выбора вершин Раскраска графов Примеры и применение и Раскраска графов Примеры и применение.

Хроматический полином удовлетворяет рекуррентному соотношению:

Раскраска графов Примеры и применение,

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

Выражения данные выше приводят к рекурсивной процедуре, названной алгоритм удаления-сжатия, сформировавшей основу для многих алгоритмов раскраски графов. Время работы удовлетворяет такому же рекуррентному соотношению, как и числа Фибоначчи, поэтому в наихудшем случае алгоритм будет работать за время Раскраска графов Примеры и применение для n вершин и m ребер.[19] На практике, метод ветвей и границ и отбрасывание изоморфных графов позволяет избежать некоторых рекурсивных вызовов, время работы зависит от метода подбора пары вершин.

Жадная раскраска

Раскраска графов Примеры и применение

Два результата работы жадного алгоритма при выборе разных порядков вершин.

Жадный алгоритм упорядочивает вершины Раскраска графов Примеры и применение,...,Раскраска графов Примеры и применение и последовательно присваивает вершине Раскраска графов Примеры и применение наименьший доступный цвет, не использовавшийся для окраски соседей Раскраска графов Примеры и применение среди Раскраска графов Примеры и применение,...,Раскраска графов Примеры и применение, либо добавляет новый. Качество полученной раскраски зависит от выбранного порядка. Всегда существует такой порядок, который приводит жадный алгоритм к оптимальному числу Раскраска графов Примеры и применение красок. С другой стороны, жадный алгоритм может быть сколь угодно плохим; например, корона с n вершинами может быть раскрашена 2 цветами, а упорядочивание может привести к числу цветов равному Раскраска графов Примеры и применение.

Для хордального графа и для его особых случаев(например, интервальный граф) алгоритм жадной раскраски может быть использован для нахождения оптимальной раскраски за полиномиальное время, выбирая порядок вершин обратным ксовершенному порядку исключения. Однако найти такой порядок — NP-сложная задача для данного графа.

Если вершины упорядочены в соответствии с их степенями, алгоритм жадной раскраски использует не более чем Раскраска графов Примеры и применение цветов, как максимум на 1 больше чем Раскраска графов Примеры и применение(Раскраска графов Примеры и применение — степень вершины Раскраска графов Примеры и применение). Этот эвристический алгоритминогда называют алгоритмом Уэлша-Пауэлла.[20] Другой алгоритм устанавливает порядок динамично, выбирая следующую вершину той, которая имеет наибольшее число смежных вершин разных цветов. Многие другие алгоритмы раскраски графов основаны на жадной раскраске и используют статические или динамические стратегии выбора порядка вершин.

Параллельные и распределенные алгоритмы

В области распределенных алгоритмов, раскраска графов тесно связана с проблемой нарушения симметрии. При достаточно большой максимальной степени вершин Раскраска графов Примеры и применение наиболее развитые вероятностные алгоритмы работают быстрее, чем детерминированные алгоритмы. Наиболее быстрые вероятностные алгоритмы используюттехнику множественных попыток.[21]

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

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

Наиболее простым интересным случаем является n-цикл. Ричард Коул и Узи Вишкин [22] показывают, что существует распределенный алгоритм, который уменьшает количество цветов от n до Раскраска графов Примеры и применение в одном синхронном шаге связи. Повторяя ту же процедуру, можно получить 3-раскраску n-цикла за Раскраска графов Примеры и применение раундов связи (при условии, что мы имеем уникальные идентификаторы узлов).

Функция Раскраска графов Примеры и применение, повторный логарифм, является чрезвычайно медленно растущей функцией, "почти константа". Следовательно, результаты Коула и Вишкина поднимают вопрос о том, есть ли распределенный алгоритм 3-раскраски n-цикла, который выполняется за константное время. Натан Линиал показал, что это не возможно: любой детерминированный распределенный алгоритм требует Раскраска графов Примеры и применение раундов связи для уменьшения N-раскраски до 3-раскраски в n-цикле.[23]

Техника Коула и Вишкина также может быть применена для произвольного графа с ограниченной степенью вершин, в этом случае время работы составляет Раскраска графов Примеры и применение.[24] Этот метод был обобщен для графа единичных кругов Шнайдером и др.[25]

Проблема раскраски ребер также изучалась в распределенной модели. Пансонецци и Рицци достигли Раскраска графов Примеры и применение-раскраски за Раскраска графов Примеры и применение в этой модели.[26]Нижняя граница для распределенной раскраски вершин достигнутая Линиалом также применима для задачи распределенной раскраски ребер.[27]

Децентрализованные алгоритмы

Децентрализованными называются алгоритмы, в которых не разрешена внутренняя передача сообщений(в отличии от распределенных алгоритмов, где процессы обмениваются между собой данными). Существуют эффективные децентрализованные алгоритмы, успешно справляющиеся с задачей раскраски графов. Эти алгоритмы работают в предположении, что вершина способна "чувствовать", что какая-либо из ее соседних вершин раскрашена в тот же цвет, что и она. Другими словами, есть возможность определить локальный конфликт. Такое условие довольно часто выполняется в реальных прикладных задачах — например, при передаче данных по беспроводному каналу передающая станция, как правило, имеет возможность детектировать, что другая станция пытается передавать одновременно в тот же канал. Способность к получению подобной информации является достаточным условием того, что алгоритмы основанные на обучающихся автоматах с единичной вероятностью правильно решат задачу раскраски графа[28] [29].

Сложность вычислений

Раскраска графа является вычислительно сложной задачей. Считается, что узнать допускает ли граф k-раскраску для заданного k - это NP-полная задача, кроме случаев k = 1 и k = 2. В частности, задача вычисления хроматического числа NP-сложна.[30] Задача о 3-раскраске NP-полная даже для случая планарного графа степени 4.[31]

Также NP-сложной задачей является раскраска 3-раскрашиваемого графа 4 цветами [32] и k-раскрашиваемого графа Раскраска графов Примеры и применение при достаточно больших значениях k.[33]

Вычисление коэффициентов хроматического полинома #P-сложная задача. Не существует на данный момент ни одного FPRAS для вычисления хроматического полинома ни для какого рационального числа k ≥ 1,5, кроме k = 2, если только не выполнится, что NP = RP.[34]

Применение

Планирование

Раскраска вершин моделирует многие проблемы планирования.[35] В своей простейшей постановке, заданный набор работ должен быть распределен по временным отрезкам, каждая такая работа занимает один отрезок. Они могут быть выполнены в любом порядке, но две работы могут конфликтовать в том смысле, что не могут быть выполнены одновременно, так как, например, используют общие ресурсы. Соответствующий граф содержит вершину для каждой из работ и грань для каждой конфликтующий пары. Хроматическое число построенного графа - это минимальное время выполнения всех работ без конфликтов.

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

Распределение регистров

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

Один из подходов к этой задаче состоит в перенесении ее на модель раскраски графов. Компилятор строит интерференционный граф, где вершины соответствуют регистрам, а грань соединяет две из них, если они нужны в один и тот же момент времени. Если этот граф k-хроматический, то переменные могут храниться в kрегистрах.

Цифровые водяные знаки

Технология цифровых водяных знаков (англ. digital watermarking) позволяет вместе с данными (будь то медиафайлы, исполняемые файлы и прочие) передать некое скрытое сообщение («водяной знак», Watermark). Такое скрытое сообщение может быть применено в защите авторских прав для идентификации владельца данных.

Это важно, например, для установления источника их распространения нелегальным образом. Или же для подтверждения прав на данные, например — программное обеспечение систем на кристалле (system-on-chip).

Сообщение можно закодировать в том числе и в графе. Одну из таких техник предложили Qu и Potkonjak (поэтому ее иногда называют QP-алгоритмом) в [37].

Состоит она вот в чем: допустим, у нас есть граф Раскраска графов Примеры и применение, раскраска которого используется в программе — причем, используется так, что допустимо поменять содержимое графа с небольшим увеличением его хроматического числа. Что важно, одним из таких примеров является граф несовместимости(интерференционный граф) распределения регистров процессора, о котором говорилось выше, — а значит, мы сможем закодировать послание в программном продукте с помощью распределения регистров.

Извлечь его можно путем сравнения полученного графа с исходным; существуют и способы удостовериться в том, было ли некое сообщение закодировано в графе без использования исходного — подробнее извлечение описано, например, в [38].

Развитие и уточнение мыслей Qu и Potkonjak, попытки улучшения алгоритма происходит в работах [39], [40], [38].

Другие применения

Задача раскраски графов была поставлена во многих других областях применения, включая сравнение с шаблоном.

Решение головоломки Судоку можно рассматривать как завершение раскраски 9 цветами заданного графа из 81 вершины.

Надеюсь, эта статья про раскраска графов применение, была вам полезна, счастья и удачи в ваших начинаниях! Надеюсь, что теперь ты понял что такое раскраска графов применение и для чего все это нужно, а если не понял, или есть замечания, то не стесняйся, пиши или спрашивай в комментариях, с удовольствием отвечу. Для того чтобы глубже понять настоятельно рекомендую изучить всю информацию из категории Дискретная математика. Теория множеств . Теория графов . Комбинаторика.

Ответы на вопросы для самопроверки пишите в комментариях, мы проверим, или же задавайте свой вопрос по данной теме.

создано: 2015-01-07
обновлено: 2020-12-29
133631



Рейтиг 5 of 10. count vote: 3
Вы довольны ?:


Найди готовое или заработай

С нашими удобными сервисами без комиссии*

Как это работает? | Узнать цену?

Найти исполнителя
$0 / весь год.
  • У вас есть задание, но нет времени его делать
  • Вы хотите найти профессионала для выплнения задания
  • Возможно примерение функции гаранта на сделку
  • Приорететная поддержка
  • идеально подходит для студентов, у которых нет времени для решения заданий
Готовое решение
$0 / весь год.
  • Вы можите продать(исполнителем) или купить(заказчиком) готовое решение
  • Вам предоставят готовое решение
  • Будет предоставлено в минимальные сроки т.к. задание уже готовое
  • Вы получите базовую гарантию 8 дней
  • Вы можете заработать на материалах
  • подходит как для студентов так и для преподавателей
Я исполнитель
$0 / весь год.
  • Вы профессионал своего дела
  • У вас есть опыт и желание зарабатывать
  • Вы хотите помочь в решении задач или написании работ
  • Возможно примерение функции гаранта на сделку
  • подходит для опытных студентов так и для преподавателей



Комментарии


Оставить комментарий
Если у вас есть какое-либо предложение, идея, благодарность или комментарий, не стесняйтесь писать. Мы очень ценим отзывы и рады услышать ваше мнение.
To reply

Дискретная математика. Теория множеств . Теория графов . Комбинаторика.

Термины: Дискретная математика. Теория множеств . Теория графов . Комбинаторика.