Автор Тема: Определить диаметр и радиус неориентированного графа  (Прочитано 586 раз)

0 Пользователей и 1 Гость просматривают эту тему.

Оффлайн Александр

  • Пользователь
  • Сообщений: 10
    • Просмотр профиля
Определить диаметр и радиус неориентированного графа, заданного матрицей смежности
 

Оффлайн phobos

  • Модератор
  • Сообщений: 95
  • Поблагодарили: 85 раз(а)
    • Просмотр профиля
Изобразим граф, заданный данной матрицей смежности, графически.

Определим матрицу расстояний для данного графа. Под расстояние между вершинами \(  \large v_i  \) и \(  \large v_j  \) понимается длина минимального пути из вершины \(  \large v_i  \) в вершину \(  \large v_j  \) и обозначается через \(  \large d(v_i,\ v_j)  \). Так как граф неориентированный, то \(  \large d\left(v_i,\ v_j\right)=d(v_j,\ v_i)  \), то есть матрица расстояний будет симметрична относительно главной диагонали. При этом \(  \large d\left(v_i,\ v_i\right)=0  \).

\(  \large \begin{pmatrix}
 {0} & {1} & {2} & {3} & {3} & {2} & {1} \\
 {1} & {0} & {1} & {2} & {2} & {1} & {1} \\
 {2} & {1} & {0} & {1} & {3} & {2} & {2} \\
 {3} & {2} & {1} & {0} & {4} & {3} & {3} \\
 {3} & {2} & {3} & {4} & {0} & {1} & {3} \\
 {2} & {1} & {2} & {3} & {1} & {0} & {2} \\
 {1} & {1} & {2} & {3} & {3} & {2} & {0}
\end{pmatrix}  \)


Найдем эксцентриситет каждой вершины графа, то есть максимальное расстояние от этой вершины до некоторой другой вершины \(  \large r\left(v_i\right)={\max  d(v_i,\ v_j)\ }  \).

\(  \large r\left(1\right)=3,\ r\left(2\right)=2,\ r\left(3\right)=3,\ r\left(4\right)=4,\ r\left(5\right)=4,\ r\left(6\right)=3,\ r\left(7\right)=3.  \)

Тогда диаметр графа есть максимальный эксцентриситет, то есть \(  \large d\left(G\right)={\max  r\left(v\right)=\ }4  \), а радиусом графа будет минимальный эксцентриситет, то есть \(  \large r\left(G\right)={\min  r(v)\ }=2  \).
 
Сказали спасибо: Admin