Page 29 - 4386

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Побудова матриці інцидентності за списком ребер. Кожний

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

інцидентності з тим же номером. Для н-графа в кожному

стовпчику списку ребер зазначені номери елементів матриці

інцидентності рівні 1 (всі інші елементи – 0). Для орграфа

першою вказується вершина, що відповідає початку дуги (у

матриці інцидентності елемент рівний 1), а другою –

відповідному кінцю дуги (у матриці інцидентності елемент

рівний -1). При збігу елементів у стовпчику списку ребер, у

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

число, відмінне від -1, 0, 1, наприклад, 2 – така ситуація

відповідає наявності в графі петель.

Приклад 2.3. Побудувати матрицю інцидентності н-графа за

списком ребер:

28