Матрицы смежности и инцидентности. Существуют различные способы задания графов

Существуют различные способы задания графов. Один из них – графический, был рассмотрен выше. Большинство задач, в частности задач информатики, часто удобнее решать, используя матричный способ задания графа.

Пусть - вершины графа , а - его ребра (в случае неориентированного графа) или дуги (в случае ориентированного графа). Матрицей смежности, соответствующей графу , называется матрица , элемент которой равен

1а) в случае неориентированного графа - числу ребер, соединяющих вершины ,

1б) в случае ориентированного графа – числу дуг, идущих из в .

Матрицей инциндентности, соответствующей графу , называется матрица, элемент которой равен 1, если верши на инцидентна ребру в неориентированном графе или дуга исходит из в ориентированном графе, равен -1, если дуга заходит в вершину только в ориентированном графе, и равен 0, если вершина не инцидентна ребру (дуге) .

Не нашли, что искали? Воспользуйтесь поиском: