Page 18 - 4336

Список ребер

Ребро 12345678910

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

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

однозначно визначають граф. Виникає питання: чи можливо
відновити граф по заданих матрицях інцидентності, суміжності

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

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

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

матриці.

По матриці суміжності число вершин визначається з

розмірності матриці. Як було відзначено, матриця суміжності н-

графа симетрична щодо головної діагоналі і кількість ребер

визначається верхнім правим трикутником матриці,

розташованим над головною діагоналлю, включаючи останню.

Тобто, число ребер н-графа дорівнює сумі елементів,

розташованих на головній діагоналі та у верхньому правому

трикутнику. У матриці суміжності орграфа симетрія відсутня, а

число ребер дорівнює сумі всіх елементів матриці суміжності.

Список ребер є скороченим варіантом матриці

інцидентності. Кількість ребер очевидна, а кількість вершин

дорівнює максимальному номеру всіх перерахованих вершин зі

списку. Тобто, матриця інцидентності та список ребер

еквівалентні. Отже, знаючи матрицю інцидентності можна

записати список ребер і навпаки.

18