электронный учебник

"Экономико-математические методы"

 

На главную страницу

Графы и сети. Потоки в сетях

14.6.  МАТРИЦА  ГРАФОВ

       Граф может быть задан  разными способами: рисунком, перечислением вершин и ребер (или дуг) и т. д. Одним из самых удобных способов является задание  графа  с помощью  матрицы. Пусть  некоторый  граф  G имеет n вершин   и  m  ребер  .  Построим   матрицу,   имеющую n строк и m столбцов. Каждая строка матрицы будет соответствовать вершине, а столбец – ребру графа. В столбце  все элементы, кроме двух, будут равны нулю. Для ориентированного графа в строке, соответствующей начальной вершине дуги , ставят число +1, а в строке, соответствующей конечной вершине, ‑ число  –1.

      Для неориентированного графа в строках матрицы, соответствующих концевым вершинам ребра , ставят 1, а в остальных строках – 0. Построенные матрицы называются матрицами  инциденций  графа.

 Назад     Вперед