Дробная раскраска - это тема молодого раздела теории графов, известного как теория дробных графов . Это обобщение раскраски обычных графов . В традиционной раскраске графа каждой вершине графа назначается какой-то цвет, а смежным вершинам, соединенным ребрами, должны быть присвоены разные цвета. Однако при дробной раскраске каждой вершине графа назначается набор цветов. Требование о смежных вершинах по-прежнему выполняется, поэтому, если две вершины соединены ребром, они не должны иметь общих цветов.
Дробную раскраску графов можно рассматривать как релаксацию линейного программирования традиционной раскраски графов. Действительно, задачи дробной раскраски гораздо более поддаются линейному программированию, чем традиционные задачи раскраски.
Определения
Б -кратна окраска графа G является присвоением множеств размера б до вершин графа таким образом, что соседние вершины получают непересекающиеся множества. : Б -раскраска является б - кратная раскраски из через доступных цветов. Эквивалентно, его можно определить как гомоморфизм графу Кнезера KG a , b . В B -кратного хроматическое число - наименьшее a такое, что существует a : b -раскраска.
Дробное число хроматической определяется как
Обратите внимание, что ограничение существует, потому что является субаддитивным , что означает
Дробное хроматическое число может быть эквивалентно определено в вероятностных терминах. является наименьшим к , для которого существует распределение вероятностей над независимыми множествами из G такое , что для каждой вершины V , учитывая независимый набор S взяты из распределения,
Характеристики
У нас есть
где n ( G ) - порядок группы G , α ( G ) - число независимости , ω ( G ) - кликовое число , и- хроматическое число .
Кроме того, дробное хроматическое число приближается к хроматическому числу с точностью до логарифмического коэффициента [1], фактически:
Графы Кнезера дают примеры, когда произвольно велико, так как пока
Формулировка линейного программирования (LP)
Дробное хроматическое число графа G можно получить как решение линейной программы . Позволять- множество всех независимых множеств группы G , и пусть- множество всех тех независимых множеств, которые включают вершину x . Для каждого независимого множества I , определим неотрицательное действительной переменной х I . потом минимальное значение
при условии
для каждой вершины .
Двойные эта линейной программа вычисляет «дробное число клики», релаксацию к рациональным числам целочисленной концепции кликова числа . То есть такое взвешивание вершин G , что общий вес, присвоенный любому независимому набору, не превышает 1 . Сильная двойственность теорема линейных гарантий программирования , что оптимальные решения как линейные программы имеют одинаковое значение. Однако обратите внимание, что каждая линейная программа может иметь размер, который экспоненциально зависит от числа вершин графа G , и что вычисление дробного хроматического числа графа является NP-трудным . [2] Это контрастирует с проблемой дробной раскраски ребер графа, которую можно решить за полиномиальное время. Это прямое следствие теоремы Эдмондса о парных многогранниках. [3] [4]
Приложения
Применения дробной раскраски графа включают планирование действий . В этом случае граф G является графом конфликтов : ребро в G между узлами u и v означает, что u и v не могут быть активными одновременно. Помещенный в противном случае, множество узлов , которые активны одновременно должен быть независимым множеством в графе G .
Оптимальная раскраска дробного графа в G затем обеспечивает кратчайшее возможное расписание, так что каждый узел активен в течение (как минимум) 1 единицы времени в целом, и в любой момент времени набор активных узлов является независимым набором. Если у нас есть решение x указанной выше линейной программы, мы просто обходим все независимые множества I в произвольном порядке. Для каждого I мы позволяем узлам в I быть активными в течениеединицы времени; между тем, каждый узел, не входящий в I , неактивен.
Говоря более конкретно, каждый узел G может представлять радиопередачу в сети беспроводной связи; края G представляют собой помехи между радиопередачами. Каждая радиопередача должна быть активна в общей сложности 1 единицу времени; оптимальная раскраска дробного графа обеспечивает бесконфликтное расписание минимальной длины (или, что эквивалентно, расписание максимальной пропускной способности).
Сравнение с традиционной раскраской графиков
Если дополнительно требуется, чтобы каждый узел был активен непрерывно в течение 1 единицы времени (без его выключения и включения время от времени), то традиционная раскраска вершин графа обеспечит оптимальное расписание: сначала узлы цвета 1 активны 1 раз. единицы, то узлы цвета 2 активны в течение 1 единицы времени и так далее. Опять же, в любой момент времени набор активных узлов является независимым набором.
В общем, дробная раскраска графа обеспечивает более короткое расписание, чем нефракционная раскраска графа; есть разрыв целостности . Возможно, удастся найти более короткий график за счет включения и выключения устройств (например, радиопередатчиков) более одного раза.
Заметки
- ^ Ласло Ловас : " О соотношении оптимальных целочисленных и дробных покрытий ", Дискретная математика. 13: 4 (1975), с. 383-390.
- ^ Карстен Лунд и Михалис Яннакакис : " О сложности аппроксимации задач минимизации ", J. ACM 41: 5 (1994), стр. 960-981.
- ^ Hajek, B .; Сасаки, Г. (1988). «Планирование ссылок за полиномиальное время». IEEE Transactions по теории информации . 34 (5): 910–917. DOI : 10.1109 / 18.21215 .
- ^ Шрайвер, Александр (2003). Комбинаторная оптимизация: многогранники и эффективность . Берлин; Гейдельберг; Нью-Йорк, штат Нью-Йорк: Springer-Verlag. С. 474 . ISBN 978-3540443896.
Рекомендации
- Шайнерман, Эдвард Р .; Ульман, Дэниел Х. (1997), Теория дробных графов , Нью-Йорк: Wiley-Interscience, ISBN 978-0-471-17864-4.
- Годсил, Крис ; Ройл, Гордон (2001), алгебраическая теория графов , Нью-Йорк: Springer-Verlag, ISBN 978-0-387-95241-3.