Page 28 - 4386

Рисунок 2.4

Розв'язок. α=2.
Матриця суміжності Матриця інцидентності

a b c d e f g 1 2 3 4 5 6 7 8 9 10
a 1 1 0 0 0 0 0 a 2 1 -1 0 0 0 0 0 0 0

b 1 0 1 0 0 0 0 b 0 -1 1 1 0 0 0 0 0 0

c 0 0 0 1 1 0 0 c 0 0 0 -1 1 1 0 0 0 0
A= d 0 0 0 0 1 0 0 B= d 0 0 0 0 -1 0 1 -1 0 0

e 0 0 0 0 0 0 0 e 0 0 0 0 0 -1 -1 0 -1 0

f 0 0 0 1 1 0 1 f 0 0 0 0 0 0 0 1 1 1

g 0 0 0 0 0 0 0 g 0 0 0 0 0 0 0 0 0 -1

Список ребер

Ребро 1 2 3 4 5 6 7 8 9 10

початок a a b b c c d f f f
Вершини
кінець a b a c d e e d e g

Як відзначалося вище, всі розглянуті способи задання графів

однозначно визначають граф. Виникає питання: чи можливо

відновити діаграму графа по заданих матрицях інцидентності,

суміжності або списку ребер? Очевидна позитивна відповідь.

По матриці інцидентності число ребер і вершин

визначається з розмірності матриці: число ребер E графа

дорівнює числу стовпців m, а число вершин V - числу рядків n

матриці.

27