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