Page 19 - 4336

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

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

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

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

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

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

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

кінцю дуги (у матриці інцидентності – елемент -1). При збігу

елементів у стовпчику списку ребер, у відповідному стовпчику

матриці інцидентності записується число, відмінне від -1, 0, 1,

наприклад, 2 – така ситуація відповідає наявності в графі петель.

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

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

Ребро 1234567 8

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

Розв'язок.

Матриця інцидентності, відповідно до списку ребер, має

вигляд:

12345678

a 10001000

b 00001010
c 00010100
B=
d 11000100

e 00110000

f 01100012

19