Матрица - смежность - граф
Cтраница 3
Обратимся к формуле (3.56), определяющей матричную форму записи операции суперпозиции двух графов G и Н, и определим число различных матриц вида R ( Q X RHI, где R ( Q - Xt - й столбец матрицы смежности RG графа G, a RH - один из классов разбиения матрицы смежности RH графа Я на k подматриц. [31]
Обратимся к формуле (3.56), определяющей матричную форму записи операции суперпозиции двух графов G и Н, и определим число различных матриц вида R ( Q X RHI, где R ( Q - Xt - й столбец матрицы смежности RG графа G, a RH - один из классов разбиения матрицы смежности RH графа Я на k подматриц. [32]
Одним из наиболее распространенных машинных представлений простого графа является матрица смежностей или соединений. Матрица смежностей графа G ( V, E) есть Vx У - матрица А1ац ], в которой atj-l, если в G существует ребро, идущее из t - й вершины в j - ю, и а - - 0 в противном случае. [33]
Следует заметить, что, используя рассмотренный выше алгоритм выделения семейства максимальных внутренне устойчивых подмножеств множества вершин графа ( максимальных пустых подграфов), можно выделять семейство Ф максимально полных подграфов. Для этого необходимо в матрице смежности R графа все единичные элементы заменить на нулевые и наоборот. В результате получим R и применяем алгоритм 1 без изменений. [34]
Методика выделения квазиминимальных массивов заключается в следующем. Квазиминимальные массивы определяются по матрице смежности R графа G. Сначала в каждой строке матрицы отыскивается элемент Гц с максимальным весом, если таких элементов в строке несколько, то фиксируется их количество. Кроме того производится определение суммы элементов в каждой строке. В списке максимальных чисел находится наибольшее. В том случае, когда в строке имеется несколько одинаковых максимальных чисел, то предпочтение отдается строке, в которой таких чисел меньше. [35]
 |
Разрез гитары токарно-винторезного станка. [36] |
А, определяется характером размерных цепей и фиксируется в алгоритме их распознавания. Затем на основе полученной выборки составляется матрица смежности графа конструкции. [37]
Если п - простое число, то Матрица смежности R графа G не может иметь вид ПК. [38]
На главной диагонали A ( G) должны стоять нули. Матрица A ( G) в противоположность матрице смежности обычного графа не обязана быть симметрической: она обладает этим свойством тогда и только тогда, когда любые две разные вершины орграфа либо не смежны, либо соединены двумя противоположно направленными дугами. [39]
Как упоминалось в разд. О является ЗНП с такой матрицей Г, которая получается в результате транспонирования матрицы смежности графа О с единичными элементами на главной диагонали. [40]
Как упоминалось в разд. G является ЗНП с такой матрицей Т, которая получается в результате транспонирования матрицы смежности графа G с единичными элементами на главной диагонали. [41]
Ориентация на человека, а не на машину требует, чтобы шаги алгоритма записывались в терминах тех объектов и отношений между ними, о которых идет речь в формулировке задач. В любом случае не должно быть работы с кодами этих объектов, например с состоящей из нулей и единиц матрицей смежности графа. [42]
Построение дуплекса произвольного графа происходит следующим образом: если исходный граф G, ( называемый материнским) имеет множество вершин V, то дуплекс G2 имеет множество вершин V U V, где V - двойник V, и G2 имеет ребра ( /, у) и ( / j), если и только если ( /, j) - ребро графа Gl. Этот способ можно удобно выразить с помощью соотношения между матрицами смежности исходного графа и его дуплекса: если А1 - матрица смежности графа С. [43]
Алгоритм раскраски вершин графа может быть реализован также в виде последовательности склеивания соцветных вершин графа. Поскольку при склеивании соцветных вершин графа Vf и Vj все цепи нечетной длины, соединяющие данные вершины, преобразуются в циклы нечетной длины, а все цепи четной длины - в циклы четной длины, степень желательности соцвет-ности вершин можно оценивать значением L ( vt, Vj) S3 ( i j) j / S2 ( i j), где S3 ( i j), S2 ( i j) - соответственно элементы куба и квадрата матрицы смежности S графа. [44]
Элементы матрицы на пересечении ее строк и столбцов определяют наличие или отсутстствие инцидентных вершинам дуг. Матрица смежности оказывается симметричной относительно главной диагонали. При составлении матрицы смежности графа будем считать равными 1 только те элементы, которые соответствуют парам вершин, ориентированным по направлению связывающих их дуг. [45]
Страницы: 1 2 3 4