Алгебраическое представление графа

Помимо графического и теоретико-множественного часто исполь­зуют и алгебраическое представление графа в виде матрицы.

Рассмотрим орграф G, содержащий n вершин и m ребер. Мат­ри­цей смежности орграфа G называется матрица A размера n´n

,

где

Иногда матрицу смежности называют матрицей отношений, или матри­цей не­пос­ред­ст­вен­ных связей.

Матрицей инцидентности (или матрицей инциденций) орграфа G на­зы­вается матрица B размера n´m, у которой

Для введения матрицы смежности нужно пронумеровать вершины, а для матрицы инцидентности - и ребра графа.

Алгебраическое представление позволяет алгоритмизировать в удоб­ной для программи­рования на ЭВМ форме процедуру определения структурных количественных параметров системы.

Рассмотрим теперь некоторые методы решения практических за­дач, ис­пользуя введен­ный нами математический формализм.