Способы задания графов

В подавляющем большинстве случаев граф задается матрицей. Для расчетов на ЭВМ это единственный способ.

Если граф G = <V,U > имеет п вершин и т дуг, то матрица инциденций определяется следующим образом :

Если граф G = <V,U > имеет п вершин, то матрица смежности определяется следующим образом :

Пример. Задать граф, изображенный на рис. 4.9, матрицей инциденций и матрицей смежности

Рис. 4.9

□ Используя определения матриц инциденций и смежности, построим эти матрицы :

v₁ v₂ v₃ v₄ v₅

■

Пример. Задать граф, изображенный на рис. 4.10, матрицей инциденций и матрицей смежности

Рис. 4.10

□ Заданный граф является неориентированным. Значит в матрице инциденций не будет отрицательных единиц. В остальном построение матриц аналогично. Матрицы имеют вид :

v₁ v₂ v₃ v₄ v₅ v₁ v₂ v₃ v₄ v₅

■