Раскраска - вершина
Cтраница 4
На графе функциональным группам ( см. рис. 1.1 3) соответствуют висячие вершины, окрашенные белым цветом в отличие от черных узлов, обозначающих мономерные звенья. Если полимер состоит из звеньев или групп различных типов, то число цветов для раскраски вершин молекулярного графа должно быть соответственно увеличено. [46]
Прежде чем развивать менее тривиальный подход к поиску минимальных раскрасок, нам надо понять: а нужно ли рассматривать проблему в полной всеобщности. При всей увлеченности очередной интересной математической задачей надо помнить, что в контексте нашего исследования раскраска вершин графа нам нужна не сама по себе, а как средство экономного распределения памяти. Может быть, графы несовместимости, получающиеся для операторных схем, обладают какими-нибудь специальными свойствами, которые могли бы облегчить поиск минимальной раскраски. Например, известно, что любой плоский граф можно раскрасить не более чем пятью красками. [47]
Обзор литературы показывает, что все известные точные алгоритмы раскраски чрезвычайно трудоемки и позволяют раскрашивать лишь графы с числом вершин в пределах сотни, что явно недостаточно для решения реальных задач логического проектирования дискретных устройств. Трудности, препятствующие существенному повышению размерности точно решаемых задач, носят принципиальный характер: задача раскраски вершин графа является ЛФ-трудной. Поэтому для решения практических задач обычно приходится использовать приближенные алгоритмы раскраски. В работе [17] приведены результаты исследования известных и предлагаемых приближенных алгоритмов раскраски, позволившие выявить наиболее эффективные алгоритмы и области их предпочтительного использования. [48]
Отметим, что результат совпал с результатом, который был получен с помощью метода, основанного на раскраске вершин графа. [49]
 |
Склеппатпте вортин графа. а До склейки, б После склейки. [50] |
Мы не просто нашли некоторую наглядную переформулировку первого подхода к алгоритму раскраски, а ввели в некотором смысле совершенно новую трактовку процесса раскраски вершин. Вместо раскраски мы осуществляем последовательные преобразования графа G, состоящие в склеивании несмежных вершин. [51]
Каждому покрытию семантической таблицы соответствует одна или несколько многокомпонентных раскрасок графа сцепления в три краски. Среди раскрасок выбираем такую, в которой совпадению значений компонент раскрасок вершин, коин-цидентных ребрам, составляющим покрытие, соответствует совпадение значений компонент раскрасок вершин, в которые осуществляется переход под действием входных векторов, взвешивающих ребра графа сцепления, вошедшие в покрытие. [52]
Граф О называют г-хроматическим, если его вершины могут быть раскрашены с использованием г цветов ( красок) так, что не найдется двух смежных вершин одного цвета. Задача нахождения хроматического числа графа называется задачей о раскраске ( или задачей раскраски) графа. Соответствующая этому числу раскраска вершин разбивает множество вершин графа на г подмножеств, каждое из которых содержит вершины одного цвета. Эти множества являются независимыми, поскольку в пределах одного множества нет двух смежных вершин. [53]
Страницы: 1 2 3 4