Матрица - смежность
Cтраница 2
Матрица смежности устанавливает отношения между узлами орграфа. Число единиц в матрице смежности, как нетрудно убедиться, равно числу дуг П в орграфе. [16]
Матрица смежности показывает наличие или отсутствие связей между элементами технологической схемы. [17]
Матрица смежности может быть составлена для систем с любым числом соединений и компонентов. [18]
Матрица смежности А А ( Г) имеет три различных собственных пространства, и любая матрица с этими собственными пространствами есть линейная комбинация матриц /, А и / - / - А. В частности, существует такая их линейная комбинация F, что F имеет собственные значения О, 1 с кратностями п - f, f соответственно. [19]
Матрица смежности M ( G) графа G, Матрица M ( G) - это матрица, элементами которой являются числа 1 или 0 в зависимости от того, существует или не существует в G соответствующее ребро. Если граф является неориентированным, то ребра ( г, /) и ( /, г) существуют одновременно и, следовательно, матрица смежности получается симметричной. [20]
Матрица смежности орграфа, состоящего из п вершин и т дуг, имеет размер пх п и содержит m букв If. Будем размещать истинностные значения И выше главной диагонали матрицы смежности, задавая дуги орграфа, идущие от вершины с меньшим номером к вершине с большим номером. В этом случае, очевидно, построенный орграф не сможет содержать контуров. Если ячейка с вычисленным адресом ( i j) ( в случае г jf) или ( jf, г) ( в случае г jf) уже содержит If или г jf, будем считать данный шаг алгоритма неудачным и увеличим m на единицу. [21]
Матрица смежности B ] 6 - j графа G, содержащего N вершин, - это квадратная матрица с W строками и N столбцами, в которой число bijt стоящее на пересечении i - й строки и / - го столбца, равно 1, если в графе имеется дуга, идущая из i - й вершины в / - ю, и равно 0, если такой дуги нет. [22]
Матрица смежности неориентированного графа симметрична относительно главной диагонали, поэтому достаточно хранить в памяти только половину ее. Задание графа с помощью матрицы смежности удобно еще и тогда, когда граф взвешенный и элементами матрицы являются не нули и единицы, а веса дуг. [23]
Матрица смежности неориентированного графа симметрична относительно главной диагонали, но для ориентированного графа ( см. несколько ниже) это утверждение не справедливо. [24]
Матрица смежности полного графа Кп имеет п строк и п столбцов. На главной ее диагонали ( пересечение строк со столбцами того же номера) стоит Л, а вне ее - И. [25]
Матрица смежностей помеченного орграфа D определяется аналогично: Л Л ( D) - а - , где а 1, если дуга v V ] принадлежит D, и ац0 в противном случае. Таким образом, матрица Л ( D) не обязательно симметрична. Некоторые результаты для орграфов, в которых используется A ( D), будут даны в гл. Из определения матрицы A ( D) следует, что матрицу смежностей данного графа можно также рассматривать как матрицу смежностей симметрического орграфа. [26]
 |
Помеченный граф и его матрица смежностей. [27] |
Матрицей смежностей 1 Л а-7 - помеченного графа Сер вершинами называется ( рХр) - матрица, в которой atj, если вершина Vi смежна с vjt и й - 0 в противном случае. [28]
Матрицей смежности A ( G ] графа Gen вершинами называется квадратная матрица порядка п с элементами ciif. [29]
Матрицей смежности транзитивного замыкания G орграфа G служит матрица достижимости R ( G) графа G. [30]
Страницы: 1 2 3 4