![]() |
Главная Случайная страница Контакты | Мы поможем в написании вашей работы! | |
|
Графы Г и Г 0 можно представить в аналитической форме либо матрицей смежности A, либо матрицей инцидентности B. Для нашего конкретного неориентированного графа Г матрицы A и B выглядят следующим образом:
![]() | ![]() |
A(Г) = ![]() | B(Г) = ![]() |
Матрица смежности для неориентированного графа всегда симметрична. Фигурирующая в ней 2 может быть в некоторых случаях заменена на 1. В матрице инцидентности сумма единиц по столбцам указывает на степень вершины vi. Нередко расположение вершин и ребер в этой матрице меняют местами (транспонируют). Так, для нашего конкретного орграфа Г 0 матрица A и B выглядят иначе:
![]() | ![]() |
A(Г0) = ![]() | B(Г0) = ![]() |
В общем случае матрица смежности для ориентированного графа уже не будет симметричной. В матрице инцидентности ставится 1, если дуга исходит из вершины, и – 1, если дуга заходит в нее.
Число дуг в пути минимальной длины от вершины vi до vj называется расстоянием r (vi, vj). Если между вершинами не существует никакого пути, то расстояние равно бесконечноти: r (vi, vj) = ∞.
Дата публикования: 2015-01-26; Прочитано: 203 | Нарушение авторского права страницы | Мы поможем в написании вашей работы!