Задання графа за допомогою матриці суміжності.
Матриця суміжності, це квадратна матриця  розміром  ( - кількість вершин графа), елементи якої величини  ,  ,  ,
де 
Для неорієнтованого графа  , тобто матриця суміжності – симетрична матриця.
Для орієнтованого графа  .Для орієнтованого графа  в тому випадку коли дуга починається в  -ті і закінчується в  -тій вершині. Складемо матриці суміжності для розглянутих вище прикладів.
Таблиці суміжності.
Для неорієнтованого графа і всі його ребра визначаються верхньою трикутною підматрицею матриці E. Причому кількість ребер дорівнює  , де -всі елементи трикутної підматриці E. Для орієнтованого графа – кількість ребер дорівнює  , де - всі елементи матриці E.
Дата добавления: 2015-09-27 | Просмотры: 770 | Нарушение авторских прав
|
