Раскраска графа

Распределения проводников по слоям (расслоение) сводится к отысканию такого расположения проводников в слоях, при котором число пересечений проводников является минимальным. Обычно проблему распределения проводников по слоям сводят к раскраске графа. Очередность прокладки проводников определяется с помощью эвристических алгоритмов, так как эта задача не формализуется теоретическими методами. [c.30]

Получив раскраску графа С, переходим к раскрашиванию графов О],. . которое можно выполнять путем алгоритма решения классической задачи, поскольку при этом нет необходимости соблюдать ограничение (2.29), так как это ограничение соблюдено при раскрашивании графа С. [c.94]

Рассмотренные алгоритмы в основном характерны для задач покрытия, разбиения и размещения. Для решения задач трассировки применяют другие алгоритмы. Различают два этапа решения задач трассировки. На первом этапе производится распределение соединений по слоям. Эта задача сводится к задаче построения минимального связывающего дерева. Наиболее распространенным алгоритмом для решения такого рода задач является алгоритм Прима [58]. Задачу распределения соединений по слоям (расслоение) можно свести также к проблеме раскраски специального графа [107]. Алгоритмы, предназначенный для решения задач первого этапа трассировки, можно назвать распределительными. [c.236]

Все операции над ПС-фафами, а также построение маршрутов, цепей, путей и другие действия отличаются от аналогичных действий с обыкновенными графами, так как здесь влияют особенности, связанные с раскраской вершин и ребер. [c.20]

Унитарная раскраска Р(С) ПС-графа в зависимости от входящих вершин есть функция персональных раскрасок этих вершин. Унитарная раскраска F G) ПС-фафа в зависимости от входящих ребер есть функция персональных раскрасок этих ребер. Унитарная раскраска Дб) ПС-графа с учетом одновременной зависимости от входящих вершин и ребер есть функция унитарных раскрасок F G)a и F(G) - [c.20]

Эти закономерности не определяют содержание функций, связывающих унитарную раскраску ПО-графа с персональными раскрасками его вершин и ребер. Рассмотрим некоторые из таких функций, особенно полезные на теоретико-множественном и логическом уровнях моделирования технических систем. [c.20]

Отношения, связывающие унитарную раскраску ПО-графа с персональными раскрасками вершин и ребер, вида [c.20]

Пусть унитарная раскраска Р(С) ПС-графа известна. Рассмотрим соотношение контуров Р С] и наперед заданного состава [c.21]

Определение унитарной раскраски ПО-графа можно представить как процесс вычисления состояний раскраски после присоединения очередной вершины (ребра). Все состояния, кроме последнего, будут промежуточными состояние после присоединения последней вершины (ребра) и будет унитарной раскраской ПО-графа. [c.22]

При последовательном вычислении унитарной раскраски ПО-графа, если существуют вершины и ребра с разными персональными раскрасками, при разных последовательностях присоединения вершин и ребер существуют различные промежуточные раскраски. Действительно, если имеется хотя бы пара вершин ai,uj с разными составами контуров, то, принимая на первом шаге вычислений за начальную вершину a или aj, получим [c.22]

Рассмотрим вычисление унитарной раскраски ПО-графа при КФС контуров. Например, при вычислении по формуле (1.1.17) промежуточное состояние раскраски [c.22]

Метод интервалов применяется для решения этой задачи. Дано некоторое множество горизонтальных отрезков цепей (интервалов) М = (Мь Мо,..., Л1 , отнесенных к одному каналу. Каждый отрезок задается координатами его концов [д 1,д 2, ]. Два отрезка считаются пересекающимися и не могут быть помещены на одну магистраль, если М1(]М,Ф0. Графом интервалов Ся(М, и) множества М называется граф, вершины которого соответствуют интервалам М а наличие ребер ,/= (М/, М/) соответствует пересечениям интервалов М,- и М/. На рис. 7.10, а дан пример множества интервалов, а на рис. 7.10, б — соответствующий ему граф Ся. Задача оптимального использования магистралей в канале сводится к задаче получения минимального количества цветов раскраски вершин графа интервалов 0 . [c.162]

Размещение 271, 325 Разреженность матрицы 225 Ранжирование 252 Раскраска графа 210 Расплывчатое множество 196 Расстояние 206 Ребро графа 198 Регнстровый подуровень 195 Редактор связей 369 Режим интерактивный 35 [c.396]

Раскраской вершины графа называют разбиение множества вершин X на / непересекающ,ихся классов (подмножеств) [c.210]

Если состав F P) преобразующих контуров определен по формулам (1.3.33), (1.3.34), то условие реализации объекта А с составом F A) преобразуемых контуров при КФС соответствует (1.3.31), (1.3.32). Это позволяет анализировать технологические возможности производственной системы и при ДФС и при КФС по единой методике, основанной на математическом аппарате анализа унитарной раскраски ПО-графа [см. формулы (1.1.20) — (1.1.31)]. Состав F P) контуров производственной системы применима как унитарная раскраска ПО-графа (1.3.14), вычисляемая при ДФС контуров верщин по формуле [c.94]

Энциклопедия по машиностроению XXL

Оборудование, материаловедение, механика и ...