Cтраница 4
Если при разрезании графа G ( X, U) в каждый кусок попадает по одной вершине, то такое разрезание называется поэлементным. Очевидно, что поэлементное и целое разрезания тривиальны и не представляют практического интереса. Заметим, что разрезание полного графа также не имеет смысла. [46]
Следует заметить, что граф может и не содержать минимальных массивов. В этом случае для разрезания графа на куски необходимо выделять квазиминимальные массивы с последующим объединением их в куски с максимальным числом внутренних ребер. [47]
Пусть разрезания / и g, порожденные на k - 1 - м шаге, подобны, и пусть / есть доминантное разрезание, a g таковым не является. Предположим, что существует разрезание графа G, например gn, полученное из g, величина которого больше величины любого разрезания графа G, полученного из /, и покажем, что это неверно. [48]
Клетки по главной диагонали матрицы R задают подграфы G i, включающиеся в куски G -, а все остальные клетки определяют наличие ребер между кусками G. Из условий (2.6) или (2.7) оптимальное разрезание графа G итерационными методами соответствует такому изоморфному преобразованию матрицы смежности, когда в клетках по главной диагонали будет сосредоточено максимальное количество элементов. [49]
Вторая глава посвящена решению задачи компоновки элементов схем дискретных устройств, которые решаются путем разрезания графа схемы на подсхемы с минимизацией числа соединительных ребер. Рассматриваются последовательные и итерационные алгоритмы разрезания графов на куски. Приводится методика разрезания графа на квазиминимальные массивы. Дан один из возможных методов покрытия функциональной схемы схемой соединения модулей. [50]
Кусок G, удаляется из графа G. Если i /, то процесс разрезания графа на I кусков закончен. [51]
Пусть разрезания / и g, порожденные на k - 1 - м шаге, подобны, и пусть / есть доминантное разрезание, a g таковым не является. Предположим, что существует разрезание графа G, например gn, полученное из g, величина которого больше величины любого разрезания графа G, полученного из /, и покажем, что это неверно. [52]
Нетрудно заметить, что такой путь решения характеризуется значительной избыточностью вычислительных операций. Действительно, при реализации первого этапа приходится искать кратчайшие пути в графе по всему множеству ребер или, как в алгоритме по типу разрезания графа, по ограниченному множеству. При реализации второго этапа формирование групп осуществляется в виде направленного поиска среди множества ОГ ( вершин графа), которое заведомо может быть сокращено более эффективным решением на первом этапе. К тому же приведенные выше методы не дают никаких указаний относительно автоматического выбора главного объекта в группе. Предложим подход, основанный на ином способе построения процедуры группировки. Будем реализовывать первый этап принятия решений, как процесс построения графа или нескольких графов, заведомо удовлетворяющих групповым свойствам включенных в него вершин. [53]