5.1 Матрицы графов

Пусть D = (V, X) – орграф, где V = {v₁, …, v_n}, X ={x₁, … , x_m}.

Определение. Матрицей смежности орграфа D называется квадратная матрица A(D) = [a_ij] порядка n, у которой

Определение. Если вершина v является концом ребра х, то говорят, что v и х – инциндентны.

Определение. Матрицей инциндентности оргафа D называется матрица размерности n×m B(D) = [b_ij], у которой

Пример матрицы инциденций и смежности для графов, изображенных на рисунках а) и б).

а)

б)