Матрицы смежности и инцидентности

Матрицей смежности называется матрица у которой элемент равен количеству ребер, соединяющих вершины .

Матрицей инцидентности называется матрица , у которой элемент равен 1, если вершина инцидентна ребру , и равен 0 в противном случае.

Пример 12

Рис.2

Решение. Матрицы смежности и инцидентности имеют вид

,

Путь и цикл в графе

Путемот до называется такая последовательность ребер графа, ведущая от к , в которой два соседних ребра имеют общую вершину, и никакое ребро не встречается дважды. Длинной пути называется число ребер этого пути.

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