Cтраница 1
Разрезание графа определим по аналогии с разбиением множеств. [1]
Разрезание графа на / кусков, как и прежде, будем сводить к последовательному разрезанию на два куска. С этой целью в матрице R выделяем по главной диагонали две произвольные подматрицы ( клетки) Q и Q. Порядок подматрицы Q равен числу вершин первого выделяемого куска, а порядок Q - числу всех оставшихся вершин графа. [2]
Поэтому разрезание графа на / кусков будем сводить к последовательному разрезанию на два куска. Число вершин первого куска равно числу вершин куска, который необходимо выделить из графа G, а число вершин второго куска - числу всех оставшихся вершин графа. [3]
Задачей разрезания графа G ( X, U) является нахождение такой совокупности кусков, чтобы суммарное число реберного соединения удовлетворяло заданному критерию оптимальности. [4]
При разрезании графа задаются верхняя и нижняя оценки числа вершин в кусках. Верхняя оценка N соответствует полусумме общего числа вершин графа G, а нижняя М - наименьшему допустимому числу вершин графа, которые возможно поместить в кусок. [5]
При разрезании графа Гс удаляются некоторые ребра. Если удаляется ребро, соединяющее вершины Хг и Xj, то в ГСА неотмеченный вход условной вершины, содержащей Xi ( х), соединенный дугой с выходом условной вершины, содержащей х, ( Хг), отмечается дополнительной меткой. Если вес удаленного ребра dl, то в ГСА вводится несколько дополнительных меток. Таким образом, минимизация суммарного веса удаленных ребер способствует минимизации числа вновь вводимых дополнительных меток. [6]
При разрезании графов схем, содержащих 20, 60, 100, 140, 180, 220 вершин, потребовалось соответственно в среднем 0 1, 1, 2, 3, 7, 12 минут машинного времени. [7]
Пусть задано произвольное разрезание графа G. Выявим случаи, в которых целесообразно производить перестановку вершин из одного куска в другой. [8]
Рассмотренный алгоритм разрезания графа эффективен при разбиении модульных схем, однако он трудно поддается программированию. [9]
Рассмотрим методику дихотомического разрезания графов с использованием чисел связности. [10]
Найти способ разрезания графа БИС на подграфы, соответствующие минимальному числу разнотипных блоков. [11]
Задача о разрезании графа ( бесконтурного ориентированного) на минимальное число частей сводится к задаче целочисленного программирования. [12]
Программа позволяет производить разрезание графа, содержащего до 830 вершин, при условии, что для каждой вершины отводится 9 разрядов ячейки памяти ЦВМ, а для мультичисла - 3 разряда. Машинная программа после трансляции занимает 775 ( 8) команд. [13]
Сформулируем теперь алгоритм разрезания графа на произвольное число кусков. [14]
Сформулируем теперь алгоритм оптимального разрезания графа на I кусков по матрице смежности, в котором используется принцип поэлементных перестановок вершин из одного куска в другой. [15]