Дискретная математика: Учебное пособие. Часть 3 - Основы теории графов, страница 5

В табл. d) представлена матрица смежности для ориентированного графа (см. рис. 10), но при условии, что строки заданы вершинами-истоками, а столбцы - вершинами-стоками. Поэтому итоговый столбец таблицы- d_i⁺ показывает полустепень каждой вершины-истока, а итоговая строка- d_I^- - полустепень каждой вершины-стока.

По структуре матрицы смежности ориентированного и неориентированного графов можно сделать следующие выводы:

·  каждый ненулевой элемент главной диагонали соответствует петле на графе;

·  матрица смежности для неориентированного графа симметрична относительно главной диагонали;

·  матрица смежности для ориентированного графа несимметрична относительно главной диагонали;

·  если в графе необходимо добавить вершину, несмежную с остальными вершинами, то к матрице смежности следует добавить столбец и строку, элементы которой содержат только “0”;

·  столбец ориентированного графа, все элементы которого имеют значение “0”, соответствует вершине-истоку всего графа;

·  строка ориентированного графа, все элементы которой имеют значение “0”, соответствует вершине-стоку всего графа.

Матрица достижимости. В отличие от матрицы смежности матрица достижимости позволяет определять связность вершин графа через промежуточные вершины этого же графа. Поскольку h_xi={x_j} есть множество смежных вершин графа, которые достижимы из x_i за один “шаг”, то отображение h(h(x_i))=h_xi² есть множество вершин достижимых из x_i за два “шага”. Так как любая вершина связанного графа должна быть достижима за p£n “шагов”, то множество вершин достижимых из вершины x_i за это число “шагов” может быть представлено в виде: h_i⁺=I Èh_xiÈh_xi²È..È h_xi^p=I_j=1È^ph_xi^j, где I –диагональ матрицы.

Для построения матрицы достижимости ||h⁺|| удобно использовать матрицу смежности ||r_i,j||, т.е.

||h⁺||=IÈ||r_i.j||È||r_i,j² ||È||r_i,j³||È..È||r_i,jⁿ ||=I_p=1È ⁿ||r_i,j^p||.

Для возведения в степень матрицы смежности используют правило умножения булевых матриц:

r_i,j²=_k=1Úⁿ (r_i,k× r_k,j),

r_i,j³=_k=1Úⁿ (r_i,k × r_k,j²) и так далее.

 Матрица весов. Протяжённость ребра или затраты времени на перемещение транспортной или информационной единицы формирует рёберно-взвешенный граф. 

Элементы матрицы весов такого графа определяются соотношением:

 0, если i=j;

r_ij =     l_i,j, если вершина x_i  смежна вершине x_j и вес ребра l_i,j;

                     ¥, если вершина x_i  несмежна вершине x_j.

          В табл. е) дана матрица весов для графа (см. рис. 17).

Табл. е)