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

 

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

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

 
 

 

 


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

 

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

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

 

 
 

 

 


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

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

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

 

 

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

 

 

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

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

 
 

 


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

 

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

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

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

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

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

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

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

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








Дата добавления: 2014-12-27; просмотров: 4286;


Поиск по сайту:

При помощи поиска вы сможете найти нужную вам информацию.

Поделитесь с друзьями:

Если вам перенёс пользу информационный материал, или помог в учебе – поделитесь этим сайтом с друзьями и знакомыми.
helpiks.org - Хелпикс.Орг - 2014-2024 год. Материал сайта представляется для ознакомительного и учебного использования. | Поддержка
Генерация страницы за: 0.004 сек.