Раскраска - граф
Cтраница 2
В задаче о раскраске графа требуется найти способ раскраски вершин графа в несколько цветов ( занумерованных целыми числами) таким образом, чтобы любые две соседние вершины были покрашены в различные цвета. Принятие решения заключается в том, чтобы установить, можно ли покрасить вершины в С или меньше цветов с соблюдением указанного требования, а оптимизация - в том, чтобы найти минимально необходимое число цветов. [16]
Основной стратегией для задач раскраски графа являются последовательные и жадные эвристики, которые дают с первой попытки результаты с локальным оптимумом. [17]
 |
Две полные раскраски графа. [18] |
Кп соответствует n - раскраске графа G, поскольку вершины графа Кп можно рассматривать как цвета и по определению гомоморфизма ни одна пара вершин графа G с одинаковым цветом не смежна. Любая раскраска, определенная полным гомоморфизмом, обладает тем свойством, что для любых двух цветов в графе G найдутся смежные вершины и и v, окрашенные в эти цвета. В данном случае мы получаем полную раскраску. На рис. 12.12 показан граф с полными раскрасками порядков 3 и 4; цвета указаны здесь положительными целыми числами. [19]
Рассмотрим теперь связь между раскрасками графа G и раскрасками его конечных частей. Возьмем такое конечное множество вершин F, что никакое пересечение FnCj в (14.1.1) не пусто. Ясно, что подграф G ( F) является ( G) - раскрашиваемым. [20]
Рассмотрим теперь связь между раскрасками графа G и раскрасками его конечных частей. Возьмем такое конечное множество вершин F, что никакое пересечение F Л С ( в (14.1.1) не пусто. [21]
Любое распределение памяти получается раскраской графа несовместимости связок информационных связей. [22]
В этой главе после определения раскраски графа и его хроматического числа излагается доказательство теоремы о пяти красках, а затем обсуждается гипотеза четырех красок. Исследуется тесная взаимосвязь между гомоморфизмами и раскрасками. Глава завершается описанием свойств хроматического многочлена. [23]
Оптимизация сводится тогда к задаче раскраски графа, где каждый цвет соответствует физическому регистру. Естественно, что не связанные между собой вершины графа могут быть раскрашены в одинаковые цвета, а связанные - не могут. [24]
Разработка бесконфликтного расписания экзаменов эквивалентна раскраске графов. Однако задача раскраски графов принадлежит к классу NP, поэтому разработка бесконфликтного расписания за разумное время невозможна. Кроме того при планировании экзаменов обычно требуется, чтобы у студента было не больше двух экзаменов в день, а экзамены по различным частям курсам назначаются в один день. Очевидно, что разработка совершенного плана экзаменов невозможна, и поэтому необходима другая техника для получения по крайней мере неплохих планов. [25]
Представление (14.1.1) называется k - раскраской графа G. Эта терминология подсказывается такой иллюстрацией, при которой каждый класс имеет свой цвет. Тогда каждая вершина окрашивается так, что концы любого ребра всегда имеют разный цвет. [26]
 |
Граф G [ IMAGE ] Колесо W7. [27] |
Так как жадная и последовательная эвристики раскраски графа достаточно быстрые, то предлагается совместить их с ГА с учетом концепций ЭМ. Стратегия совмещения предполагает, что используется кодирование нашего алгоритма для гибридного ГА. Кодировка, используемая в жадной эвристике, основана на упорядочивании вершин графа. Она упорядочивает вершины по уменьшению значений локальных степеней вершин и затем декодирует эту последовательность, назначая каждой вершине по порядку первый реальный цвет, где реальность основана на использовании цветов при раскраске предыдущих вершин. Такой способ кодировки при решении проблемы раскраски графа упорядочивает вершины графа определенным способом, а затем декодирует их в соответствии с жадной эвристикой. [28]
Многие практические задачи сводятся к построению раскрасок графов. [29]
Сложность оптимального выбора DCDP-связей эквивалентна проблеме оптимальной раскраски графа. [30]
Страницы: 1 2 3 4