Одной из главных тенденций в развитии современной науки является то обстоятельство, что объектом её исследований становятся всё более и более сложные системы. Развитие техники и производства требует для проектирования и конструирования привлечения новых, интеллектуально-ёмких и математически-насыщенных аппаратных и инструментальных средств. Кроме того, логика развития науки для более полного познания законов требует принимать во внимание те эффекты, которыми ранее пренебрегали, что также связано с весьма существенным усложнением, увеличением мерности рассматриваемых моделей реальных объектов. Так в теории больших систем и в прикладных науках появились принципы декомпозиции.
Одним из наиболее общих и эффективных путей исследования сложных систем является переход от исходной сложной системы к исследованию таких более простых в каком-то смысле систем, по свойствам которых можно восстановить точно или приближённо свойства исходной системы. Сложность решения и NP-полнота многих задач заставляют искать способы решения общим приёмом, который можно назвать декомпозицией.
Одним из видов перехода от сложной системы к более простой является именно пространственное разделение большой системы на квазиизолированные части. Так появляются графовые модели, в которых вершины соответствуют некоторым «кускам» системы, а рёбра — их взаимосвязям. Если части системы так или иначе подобны, то графы становятся фрактальными (предфрактальными), а типовой их фрагмент называется «затравкой».
Содержательный смысл исходной задачи позиционируется как переход от автоматизированного проектирования к автоматическому за счёт оптимального размещения элементов на монтажно-коммутационном пространстве (МКП), при котором автоматически выполняются «необходимые» (правда, не всегда «достаточные») условия для последующей успешной трассировки [1]. При этом метрические потоки проводников через боковые поверхности каждого пространственно-ограниченного фрагмента МКП не должны превышать метрических пропускных способностей этих поверхностей. Через решение этой исходной задачи выкристаллизовывается метапонятие «трассируемости» монтажно-коммутационного пространства.
Задача минимальной раскраски встречается во многих прикладных задачах автоматизированного проектирования. Раскраска электрических схем не сводится к раскраске эквивалентных им графов в связи с неполной релевантностью или неточным изоморфизмом схемы и графа, неоднозначностью представления схемы графом из-за особых свойств электрической цепи, соединяющей больше двух контактов активных элементов схемы. Цепи схемы неоднозначно представляются одним и тем же деревом или различными деревьями (в частности, цепями-маршрутами и цепями-веерами с противоположными метрическими свойствами) и т. д. Все эти трудности привели в своё время к появлению и развитию теории гиперграфов.
Задача раскраски вершин МКП-сети важна потому, что проводники на конструктиве могут соединять вершины только разных цветов. При одной цепи в схеме способ её реализации (представления) не играет роли, так как дерево-цепь всегда бихроматично (следствие 1 теоремы Кёнига). Если на вершины графа схемы одновременно наложено несколько цепей или пара цепей имеет две или более вершин пересечения цепей, то возможно появление циклов, в частности, простых циклов нечётной длины. Поэтому необходимо эквивалентно преобразовывать электрические цепи назначением особых вершин цепи (начало и конец цепи-маршрута, коническая вершина цепи-веера) на вершины графа схемы, чтобы превратить простые цепи и циклы в конструкции чётной длины, тогда число красок правильной раскраски электрической схемы становится минимальным.
Желание раскрасить сеть в минимальное число цветов заставило искать способы преобразования циклов нечётной длины в циклы длины чётной. Вследствие того, что в один момент вершины цепей назначаются на вершины сети, а различные вершины цепи имеют разные степени, можно производить эквивалентные преобразования цепей, изменяющие степень конкретной вершины цепи. Известно несколько алгоритмов (по крайней мере, четыре) таких преобразований.
Результаты работ по раскраске реальных электрических схем можно свести к гипотезе W: хроматическое число графа любой реальной электрической схемы равно хроматическому числу его суграфа, составленного из цепей-рёбер схемы, т. е. цепей, содержащих пару вершин и одного инцидентного им обеим ребра.
Основная задача — необходимым условием прокладки электрических цепей в виде печатных проводников является наличие свободного ресурса монтажно-коммутационного пространства в каждом произвольном сечении как по оси Х, так и по оси Y. При этом пропускная способность любого сечения на плоскости МКП была бы не меньше потока проводников (метрического количества прокладываемых связей) в этом сечении.
Для решения задачи по всему МКП был выбран математический аппарат потоков в сетях. Он позволил строго и точно решить задачи о максимальном потоке, о потоке минимальной стоимости, задачу о спросе и предложении, задачу о синтезе сети с заданными пропускными способностями. МКП является протяжённым в пространстве объектом, его преобразование с декомпозицией и объединением фрагментов составляет один из этапов исследования. Фрагментами МКП являются радиоэлементы, групповые элементы и макроэлементы, электрические цепи, соединяющие размещённые или размещаемые элементы, а также запрещённые зоны и групповые провода. Необходимым условием прокладки цепей в виде печатных проводников является наличие свободного ресурса монтажно-коммутационного пространства в каждом произвольном сечении, так, чтобы пропускная способность любого сечения на плоскости была не меньше количества прокладываемых связей. Одновременно требуется минимизировать длину прокладываемых связей, это может быть минимум суммарной длины, минимизация длины максимально-длинного проводника и т. д.
Задача может быть решена математическим аппаратом потоков в сетях, который решает разные варианты, разновидности общей потоковой проблемы: задача о максимальном потоке, задача о потоке минимальной стоимости, задача о спросе и предложении, задача синтеза сети с заданными пропускными способностями и т. д.
Графы, хроматическое число которых c(L) > 3, при преобразовании в «потоково-пригодный» вид начинают терять некоторые рёбра, так что модель становится не релевантной действительности. К счастью, как показало исследование, при работе с реальными электрическими цепями можно утверждать — гипотеза Y: любая практическая электрическая схема в «потоково-пригодном» виде трижды раскрашиваема.
Литература:
1. Винтизенко И. Г. Пространственная декомпозиция монтажно-коммутационного пространства в САПР. Диссертация на соискание учёной степени доктора технических наук по специальности 05.13.12 — системы автоматизации проектирования. — Томск: Томский институт автоматизированных систем управления и радиоэлектроники, 1989.
