Введение
Окраска графа, где элементам графа присваиваются наборы цветов. Фракционное окрашивание — это тема в молодой области теории графов, известной как фракционная теория графов. Оно является обобщением обычного раскрашивания графа. В традиционном раскрашивании графа каждой вершине графа присваивается некоторый цвет, и смежным вершинам — тем, которые соединены ребрами — должны присваиваться разные цвета. Однако при фракционном окрашивании каждой вершине графа присваивается набор цветов. Требование относительно смежных вершин по-прежнему действует, поэтому, если две вершины соединены ребром, у них не должно быть общих цветов. Фракционное раскрашивание графа можно рассматривать как линейное программирование, являющееся релаксацией традиционного раскрашивания графа. Действительно, задачи фракционного окрашивания гораздо лучше поддаются решению методами линейного программирования, чем традиционные задачи раскрашивания.
Fractional coloring is a topic in a young branch of graph theory known as fractional graph theory. It is a generalization of ordinary graph coloring. In a traditional graph coloring, each vertex in a graph is assigned some color, and adjacent vertices — those connected by edges — must be assigned different colors. In a fractional coloring however, a set of colors is assigned to each vertex of a graph. The requirement about adjacent vertices still holds, so if two vertices are joined by an edge, they must have no colors in common. Fractional graph coloring can be viewed as the linear programming relaxation of traditional graph coloring. Indeed, fractional coloring problems are much more amenable to a linear programming approach than traditional coloring problems.
Приложения
Применение дробного раскрашивания графов включает планирование задач. В этом случае граф G является графом конфликтов: ребро в G между вершинами u и v означает, что u и v не могут быть активны одновременно. Иными словами, множество активных вершин в любой момент времени должно быть независимым множеством в графе G. Оптимальное дробное раскрашивание графа G обеспечивает максимально короткий график, при котором каждая вершина активна в течение (как минимум) 1 единицы времени в общей сложности, и в любой момент времени множество активных вершин является независимым множеством. Если у нас есть решение x для указанной линейной программы, мы просто перебираем все независимые множества I в произвольном порядке. Для каждого I мы активируем вершины в I на время; при этом все вершины, не входящие в I, остаются неактивными. В более конкретных терминах, каждая вершина G может представлять собой радиопередачу в беспроводной сети связи; ребра G представляют собой интерференцию между радиопередачами. Каждая радиопередача должна быть активна в течение 1 единицы времени в общей сложности; оптимальное дробное раскрашивание графа обеспечивает график минимальной длины (или, эквивалентно, график максимальной полосы пропускания), не содержащий конфликтов.
An optimal fractional graph coloring in G then provides a shortest possible schedule, such that each node is active for (at least) 1 time unit in total, and at any point in time the set of active nodes is an independent set. If we have a solution x to the above linear program, we simply traverse all independent sets I in an arbitrary order. For each I, we let the nodes in I be active for time units; meanwhile, each node not in I is inactive. In more concrete terms, each node of G might represent a radio transmission in a wireless communication network; the edges of G represent interference between radio transmissions. Each radio transmission needs to be active for 1 time unit in total; an optimal fractional graph coloring provides a minimum length schedule (or, equivalently, a maximum bandwidth schedule) that is conflict free.
Сравнение с традиционным окрашиванием графов
Если бы дополнительно требовалось, чтобы каждый узел должен был находиться в активном состоянии непрерывно в течение 1 единицы времени (без периодического включения и выключения), то традиционное раскрашивание вершин графа обеспечило бы оптимальное расписание: сначала узлы цвета 1 активны в течение 1 единицы времени, затем узлы цвета 2 активны в течение 1 единицы времени, и так далее. При этом в любой момент времени множество активных узлов является независимым множеством. В общем случае, дробное раскрашивание графа позволяет получить более короткое расписание, чем целочисленное раскрашивание графа; существует разрыв целочисленности. Возможно, удастся найти еще более короткое расписание, за счет более одного включения и выключения устройств (например, радиопередатчиков).