Матрица смежности

1. Матрица смежности – это двумерный массив размерности N×N.

Для неориентированного графа

Для неориентированного графа – это симметричная матрица с нулями на главной диагонали. Сумма цифр в любой строке или столбце равна степени соответствующей вершины.

Ниже представлена матрица смежности графа, изображенного на рис. 13.

Для ориентированных графов

Для ориентированных графов матрица смежности не будет симметрична относительно главной диагонали. Для ориентированных мульти- и псевдографов A[i,j] равно количеству дуг, соединяющих вершину i с вершиной j.

На рис. 14 изображен ориентированный мульти-псевдограф и его матрица смежности.

Матрица инциденций

Матрица инциденций отражает инцидентность вершин и ребер.

Для неориентированных графов

На рис. 15 изображен простой граф и его матрица инцидентности.

Для ориентированных графов

На рис. 16 изображен орграф и его матрица инцидентности.

Перечень ребер

Для хранения перечня ребер используют двумерный массив размерности |Е| × 2, каждая строка которого описывает ребро графа.

Для графа, изображенного на рис. 15, перечень ребер имеет вид:

Изоморфизм графов

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

На рис. 17 изображены изоморфные графы.

Достижимость и связность

Определение. Маршрут – это последовательность ребер (дуг) графа, в которой конец каждого ребра (дуги) совпадает с началом следующего ребра.

Определение. Число ребер маршрута называется его длиной.

Определение. Циклом называется замкнутый маршрут.

Например, в графе, изображенном на рисунке 18, вершины v₅ и v₃ соединены маршрутами (е₆, е₂) длины 2; (е₅, е₁, е₂) длины 3. Маршрут (е₅, е₁, е₂, е₃, е₄) является циклом.

Определение. Если существует маршрут из вершины графа v в вершину u, то говорят, что u достижима из v.

Связность в неориентированных графах

Определение. Неориентированный граф G связен, если существует хотя бы один маршрут в G между каждой парой вершин i и j.

Определение. Подграфом графа G(V,E) называется граф, все вершины которого принадлежат V(G), а все ребра принадлежат E(G).

Определение. Максимальный связный подграф графа G называется связной компонентой графа G. Замечание: максимальный не в смысле количества ребер, а в смысле нерасширяемости.

Например, на рис. 19 изображен несвязный граф с тремя компонентами связности.

Заметим, что каждая компонента связности неориентированного графа представляет собой неориентированный граф, а значит, для нее выполняется лемма о рукопожатиях.

Связность ориентированных графов

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

Определение. Ориентированный граф сильно связен, если для каждой пары вершин i и j существует по крайней мере один путь из i в j и по крайней мере один путь из j в i.

Определение. Максимальный сильно связный подграф орграфа называется сильно связной компонентой.

На рис. 20 – 22 изображены несвязный, связный, но не сильно и сильносвязный графы соответственно.

Циклы