Раскраска - граф
Cтраница 1
Раскраска графа - необычная задача: как мы уже упоминали ранее, построение раскраски, достаточно близкой к оптимальной, дается столь же сложно, как и построение оптимальной раскраски. Число красок, даваемое наилучшим известным полиномиальным алгоритмом, более чем вдвое превышает оптимальное. Кроме того доказано, что если существует полиномиальный алгоритм, раскрашивающий вершины любого графа числом красок, превышающим оптимальное не более чем вдвое, то существует и полиномиальный алгоритм оптимальной раскраски любого графа. [1]
Раскраска графа G называется полной, если для каждых двух различных цветов существуют смежные вершины, окрашенные этими цветами. Хорошо известно, что минимальное число цветов в полной раскраске графа равно его хроматическому числу. [2]
Псевдополная раскраска графа не является в действительности его раскраской, но представляет собой такое приписывание цветов его вершинам, что для любых двух различных цветов найдутся две смежные вершины, окрашенные этими цветами. Заметим, что в псевдополной раскраске смежные вершины не обязательно должны быть окрашены в различные цвета. [3]
 |
Три раскраски графа. [4] |
Раскраской графа называется такое приписывание цветов его вершинам, что никакие две смежные вершины не получают одинакового цвета. Множество всех вершин одного цвета является независимым и называется одноцветным классом. В п-раскраске графа G используется п цветов, и, таким образом, эта раскраска разбивает V на п одноцветных классов. Хроматическое число % ( G) графа G определяется как наименьшее п, для которого граф G имеет и-рас-краску. [5]
Раскраской графа называется такое приписывание цветов его вершинам, что никакие две смежные вершины не получают одинакового цвета. Таким образом, раскраска графа в k цветов разбивает множество его вершин на k непересекающихся классов, в каждом из которых нет попарно несмежных вершин. Хроматическое число x ( G) графа G определяется как наименьшее k, для которого граф G имеет раскраску в k цветов. [6]
Если раскраска графа Рамсея порождает в точности число непременно возникающих монохроматических треугольников, то она называется экстремальной. Всегда ли существует экстремальная раскраска, при которой все непременно возникающие монохроматические треугольники оказываются одного и того же цвета. Такие раскраски получили название сине-пустых, означающее, что множество синих треугольников пусто, т.е. число их равно нулю. В 1961 г. Леопольд Сове показал, что при всех нечетных п за исключением п 1 ответ на этот вопрос должен быть отрицательным. Результат Сове наводит на мысль о новом классе задач. [7]
Задача раскраски графа тесно связана с построением независимых или внутренне устойчивых подмножеств, а также определением клик графа. Если две любые вершины подмножества X графа G ( X, U), X С X, не смежны, то оно называется внутренне устойчивым. Подмножество Ф С С X графа G ( X, U) называется максимальным внутренне устойчивым подмножеством или независимым, если добавление к нему любой вершины xi С X делает его не внутренне устойчивым. [8]
При раскраске графа любые две смежные вершины не должны иметь один и тот же цвет. Предположим, что имеются три вершины, соединенные в треугольник. Вершины X и У могут быть окрашены в красный или зеленый цвета. Вершина Z может быть окрашена в зеленый или голубой цвета. Задача раскраски графа может быть поставлена следующим образом. [9]
Рассмотрена задача раскраски графа и описан гибридный ГА ее решения. Основной стратегией для задач раскраски графа являются последовательные и жадные эвристики, которые дают с первой попытки результаты с локальным оптимумом. [10]
Рассмотрим задачу раскраски графа. [11]
Общий алгоритм раскраски графа при большом числе вершин очень громоздок. [12]
Поскольку при любой допустимой раскраске графа С множество вершин, окрашиваемых в один и тот же цвет, должно быть независимым множеством, то всякую допустимую раскраску можно интерпретировать как разбиение всех вершин графа О на такие независимые множества. Далее, если каждое независимое множество расширить до максимального ( путем добавления к нему других вершин), то раскраска графа С может быть тогда истолкована как покрытие вершин графа О максимальными независимыми множествами. Очевидно, что в последнем случае некоторые вершины графа С могут принадлежать более чем одному максимальному независимому множеству. Это говорит о возможности существования различных допустимых раскрасок ( использующих одно и то же число цветов), так как вершину, принадлежащую разным максимальным множествам, можно окрасить в любой из цветов, соответствующих тем максимальным независимым множествам, которым она принадлежит. [13]
Поскольку при любой допустимой раскраске графа G множество вершин, окрашиваемых в один и тот же цвет, должно быть независимым множеством, то всякую допустимую раскраску можно интерпретировать как разбиение всех вершин графа G на такие независимые множества. Далее, если каждое независимое множество расширить до максимального ( путем добавления к нему других вершин), то раскраска графа G может быть тогда истолкована как покрытие вершин графа G максимальными независимыми множествами. Очевидно, что в последнем случае некоторые вершины графа G могут принадлежать более чем одному максимальному независимому множеству. Это говорит о возможности существования различных допустимых раскрасок ( использующих одно и то же число цветов), так как вершину, принадлежащую разным максимальным множествам, можно окрасить в любой из цветов, соответствующих тем максимальным независимым множествам, которым она принадлежит. [14]
Поэтому в теории раскрасок графов наибольший интерес представляют оценки хроматического числа и приближенные методы раскраски. [15]
Страницы: 1 2 3 4