2015-06-28
280
Матрица смежности – это квадратная матрица 
ij, строкам и столбцам которой соответствуют вершины графа. Для неориентированного графа ij ровно количеству ребер, инцидентных i-ой и j-ой вершинам. Для орграфа ij ровно количеству ребер с началом в i-ой вершине и концом j-ой вершине. Таким образом матрица смежности неориентированного графа симметрична, а орграфа – необязательно.
Пример: построим матрицы смежности для графов, рассмотренных ранее.
| I | II | III | IV | V | VI | VII | I | II | III | IV | V | VI | VII | |||
| I | I | |||||||||||||||
| II | II | |||||||||||||||
| III | III | |||||||||||||||
| IV | IV | |||||||||||||||
| V | V | |||||||||||||||
| VI | VI | |||||||||||||||
| VII | VII |
Матрица смежности неориентированного графа
|
|
|
Матрица смежности орграфа.
