Раскраска - вершина
Cтраница 1
Раскраски вершин S2 и S7 совпадают по второй компоненте. Поскольку раскраски вершин S5 и S2 также совпадают по второй компоненте, то для переходов, взвешенных входным вектором Х3, недетерминированности не возникает. Таким образом, данная многокомпонентная раскраска определяет кодирование внутренних состояний автомата в 3-значном структурном алфавите, при котором элементы памяти функционально несвязны. [1]
Нахождение раскраски вершин графа минимальным числом цветов так, чтобы ни одно ребро не соединяло двух вершин одного цвета. [2]
Алгоритм раскраски вершин графа может быть реализован также в виде последовательности склеивания соцветных вершин графа. Поскольку при склеивании соцветных вершин графа Vf и Vj все цепи нечетной длины, соединяющие данные вершины, преобразуются в циклы нечетной длины, а все цепи четной длины - в циклы четной длины, степень желательности соцвет-ности вершин можно оценивать значением L ( vt, Vj) S3 ( i j) j / S2 ( i j), где S3 ( i j), S2 ( i j) - соответственно элементы куба и квадрата матрицы смежности S графа. [3]
Сводя раскраску вершин графа к их последовательному склеиванию, нам нужно убедиться, что на этом пути мы не утрачиваем потенциальной возможности получить минимальную раскраску исходного графа. Конечно, можно сразу сообразить, что если взять некоторую минимальную раскраску в X красок и склеить между собой все вершины, окрашенные одним цветом, то в результате у нас получится - полный граф, однако на самом деле нам требуется более сильное утверждение, которое мы оформим в виде теоремы. [4]
Обобщения задачи раскраски вершин графа применительно к проектированию дискретных устройств. [5]
Если при раскраске вершин куба используются три разных цвета, то сколько возможно различных кубов. [6]
Постройте алгоритм для раскраски вершин данного графа G, использующий минимально возможное число красок и такой, что никакие две смежные вершины не имеют одного и того же цвета. [7]
Условие (4.11) обеспечивает раскраску вершины в один и только один цвет. [8]
В степенях свободы при раскраске вершины v есть две градации: одна - это какую краску выбрать из уже использованных, и вторая - взятие свежей краски. [9]
 |
Гиперграф с группой автоморфизмов порядка 12. [10] |
Именно благодаря группе автоморфизмов возникают эквивалентные раскраски вершин. Исключение составляют гиперграфы, группы автоморфизмов которых единичные. Такие гиперграфы называются асимметрическими. [11]
Типичным примером локального свойства является раскраска вершин графа так, чтобы смежные вершины имели разные цвета. Множество регуляторов равно числу красок. Топология задается парами смежных вершин. Настраиваемость среды относительно локального свойства, задающего неравенство красок для смежных вершин, соответствует возможности правильной раскраски всего графа. [12]
В главе 4 задача о раскраске вершин рассматривается как особый случай задачи о покрывающих множествах, изучавшейся в предыдущей тлаве. Даны приложения задачи раскрашивания к составлению расписаний, размещению ресурсов, а также ее обобщения на задачу доставки. [13]
Снова столкнувшись с необходимостью рассматривать задачу раскраски вершин графа в ее полной всеобщности в поисках более эффективного алгоритма нахождения минимальной раскраски, мы должны установить себе определенные рамки этого поиска. Поясним, что мы имеем в виду. Мы установили, что для решения задачи в лоб нам нужно построить п раскрасок и на каждую раскраску потратить еще какое-то количество операций, чтобы определить ее правильность и подсчитать число использованных красок. [14]
Задачи логического проектирования, сводимые к раскраске вершин графа, образуют подкласс значительно более широкого и значительно менее изученного класса задач о минимальном разбиении данного множества, в которых условие попарной совместимости элементов подмножества необходимо, но не обязательно достаточно для их совместимости в совокупности. [15]
Страницы: 1 2 3 4