logo
ЭУМКД_ДиВМ3

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

Пусть D = (V, X) – орграф, где V = {v1, …, vn}, X ={x1, … , xm}.

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

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

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

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

а)

б)