МАТРИЧНОЕ ПРЕДСТАВЛЕНИЕ ГРАФОВ

Ориентированные и неориентированные графы можно описывать с помощью матриц, которые в алгебраической форме представляют структурные свойства графа. Основными матрицами, полностью описывающими структуру графа, являются матрица инциденций и матрица смежности вершин. Построение матрицы смежности ребер позволяет проводить операции, упрощающие постановку задач исследования структуры системы, а матриц разрезов, путей, циклов облегчает нахождение всех разрезов графа, максимального потока в сети и других.

Матрица инциденций. Пусть G - граф, имеющий п = 6 вершин и т = 8 ребер (рис. 5.19). Этому графу соответствует матрица размером п х т — (6x8), строки и столбцы которой соответствуют вершинам и ребрам графа G.

Исходный граф G

Рис. 5.19. Исходный граф G

Элемент матрицы инциденций определяется как

Для графа, представленного на рис. 5.19, матрица инциденций имеет вид

Так как ребро графа инцидентно двум вершинам, каждый столбец матрицы инциденций содержит только два единичных элемента.

Элементы матрицы инциденций направленного графа имеют значения

Если два графа имеют одни и тс же матрицы инциденций, то можно утверждать, что они изоморфны.

Матрица смежности вершин. Для ориентированных и неориентированных графов возможно построение квадратной матрицы смежности вершин. Элемент матрицы смежности вершин на пересечении /-й строки и у-го столбца равен числу ребер, инцидентных одновременно /-й и у'-й вершинам (или направленных от вершины / к вершине у в случае ориентированного графа).

Для неориентированного графа, представленного на рис. 5.19, матрица смежности вершин симметрична относительно главной диагонали и имеет вид

Матрица смежности ориентированного графа даст число ориентированных маршрутов длины п между любыми двумя вершинами.

В квадратной матрице смежности ребер Е строки и столбцы отвечают ребрам графа. Элемент матрицы смежности ребер ay = 1, если е, и ej различные ребра с общей граничной точкой, и ау = 0, если они не имеют общего конца.

Матрицу смежности ребер графа G можно рассматривать как матрицу смежности вершин для новою графа G вершинами которого являются ребра исходного графа (7, а ребрами - пары e,-t ej. Такой граф называется смежностным. Существование его объясняет двойственность между вершинами и ребрами. Для построения смежностного графа G' на каждом ребре исходного графа G (рис. 5.20) выбирается фиксированная точка е например, середина ребра. Пара таких точек е , e'j — новых вершин графа G' - соединяется ребром тогда, когда соответствующие ребра et и ej имеют общую вершину в графе G.

Исходный граф G (а); смежностный граф G' (б)

Рис. 5.20. Исходный граф G (а); смежностный граф G' (б)

Для связного графа с нумерованными вершинами можно построить матрицу путей (или цепей). Количество строк этой матрицы соответствует количеству путей из начальной вершины в конечную, а столбцы — ребра графа. Следовательно, элемент матрицы принимает значение 1 или 0 в зависимости от того, принадлежит ли данное ребро данному пути или нет.

Например, граф рис. 5.19 имеет матрицу путей из вершины V2 в vt:

Аналогично матрице путей составляются матрицы циклов и разрезов. Строки этих матриц соответствуют перечислению ребер, принадлежащих циклу или разрезу. Элементы этих матриц принимают значение 1 или 0 в зависимости от того, принадлежит данное ребро данному циклу (разрезу) или нет. Следует отметить, что большинство задач требует анализа минимальных разрезов, поэтому порядок матрицы разрезов может быть существенно сокращен.

 
Посмотреть оригинал
< Пред   СОДЕРЖАНИЕ   ОРИГИНАЛ     След >