Матричное представление графов

Любой граф, заданный множествами Х и Г или в виде рисунка, может быть также представлен с помощью матриц смежности и инцидентности.

В квадратной матрице смежности строки и столбцы соответствуют вершинам графа. Для орграфа на пересечении i-той строки и j-того столбца матрицы значения элементов образуются по правилу

Для графа на рисунке 2.2 матрица смежности имеет вид:

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

Для неорграфа в матрице смежности на пересечении строк и столбцов стоят единицы, если вершины соединены ребрами. Матрица, построенная по этому правилу для графа на рисунке 2.3 имеет вид

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

Существуют разновидности матриц смежности. В матрице весовых соотношений элемент вместо 1 принимает значения веса связи , в матрице длин – длины ребра или дуги .

В прямоугольной матрице инцидентности строки соответствуют вершинам графа, а столбцы – ребрам (дугам). Для неорграфа на пересечении i-той строки и j-того столбца элементы матрицы образуются по следующему правилу

Для графа, изображенного на рисунке 2.1в, матрица инцидентности имеет вид

В каждом столбце матрицы Е не более двух единиц, поскольку каждое ребро соединяет две вершины. Столбцы, соответствующие петлям, содержат по одной единице.

Для орграфа в матрицу инцидентности заносится

Для графа на рисунке 2.2 матрица инцидентности записывается в виде:

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

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

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

Контрольные вопросы

1) Из каких элементов состоит граф?

2) Какие различия имеются между ориентированным и неориентированным графами?

3) Как формируются матрицы смежности ориентированных и неориентированных графов?

4) Как формируются матрицы инцидентности ориентированных и неориентированных графов?