Дискретная математика

140 если г'-я вершина инцидентна у-у ребру, О, если /-я вершина не инцидентна ./-у ребру. Пусть имеем граф, изображенный иа рис. 5.17. Тогда матрица инциденций этого графа - матрица А, запишется в следующем виде справа от рис. 5.17. V2 Vj XJ VI ^=V2 V3 XS Х] ^2 ДГз П 0 А 1 1 0 0 0 1 .0 1 0. V4 Рис. 5.17 Каждая строка этой матрицы равна сумме по модулю 2 всех остальных строк. Рассмотрим ещё один пример графа, состоящего из трёх компонент связности, см. рис 5.18. Построим для этого графа матрицу инциденций - матрицу/4. д:1 ^2 ^5 Xj [ 0 0 0 0 0 0^ 2 1 1 0 0 0 0 3 0 1 0 0 0 0 4 0 0 1 0 0 0 5 0 0 1 0 0 0 6 0 0 0 1 0 1 7 0 0 0 0 1 1 8 . 0 0 0 1 1 Оу ^ V „ Рис. 5.18 • Для данного графа получили, что матрица инциденций является блочной матрицей с тремя блоками. Можно убедиться, что и для любого графа при соответствующей нумерации ребер и вершин графа матрица инциденций является блочной матрицей и каждый блок соответствует компоненте связности графа G. Последовательной нумерацией ребер и вершин графа внутри каждой компоненты связности гра^а можно получить блочно диагональное представление матрицы инциденций. Также блочно диагональное представление матрицы илциденций можно получить непосредственно с