Главная > Математика > Теория графов. Алгоритмический подход
<< Предыдущий параграф
Следующий параграф >>
<< Предыдущий параграф Следующий параграф >>
Макеты страниц

8.2. Матрица инциденций

Пусть дан граф вершинами и дугами. Матрица инциденций графа обозначается через и является матрицей размерности определяемой следующим образом:

Для графа, приведенного на рис. 1.8, матрица инциденций имеет вид

Поскольку каждая дуга инцидентна двум различным вершинам, за исключением того случая, когда дуга образует петлю, то

каждый столбец либо содержит один элемент, равный 1, и один — равный —1, либо все элементы столбца равны 0.

Если является неориентированным графом, то его матрица инциденций определяется так же, как и выше, за исключением того, что все элементы, равные —1, заменяются на

9. Задачи

(см. скан)

(см. скан)

10. Список литературы

(см. скан)

<< Предыдущий параграф Следующий параграф >>
Оглавление