Матрица инцидентности

,

.

Например:

Задан графG=(V, E),где

V={a, b, c, d},

E={ab, bc, ac, ad, dc}.

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

Степени вершин графа

Степень вершины deg(v)графа G– число инцидентных ей ребер.

Максимальная степеньвсех вершин графа G – D(G):

.

Минимальная степеньвсех вершин графаG – d(G):

.