Page 40 - 4386

Рисунок 3.6

Розв'язок.

Згідно алгоритму, відстань від вершини 7 будемо шукати в

такий спосіб.

1. A ={7}.
0
2. A ={1 , 3 , 6 }.
7
1
7
7
3. A ={2 , 5 , 4 }.
2
1,3
3,6
3
Більше непозначених вершин немає. Тобто відстані від
вершини 7 до кожної з вершин графа наступні:
d(7, 1)=d(7, 3)=d(7, 6)=1;

d(7, 2)=d(7, 4)=d(7, 5)=2.

3.7 Ексцентриситет, радіус, діаметр, центр,
периферійні вершини графа

Ексцентриситетом вершини v∈V зв’язного графа G=(V,E)

називається величина e(v)=max{d(v, w) | w∈V}, тобто найбільша з

відстаней між вершиною v та іншими вершинами графа.

Діаметром зв’язного графа G називається найбільший з усіх

ексцентриситетів його вершин і позначається D(G). Жодна

відстань у графі не перевищує його діаметра.

Радіусом зв’язного графа G називається найменший з усіх

ексцентриситетів його вершин і позначається R(G).

Якщо e(v)=R(G), то вершина v називається центральною.

Центром графа називається множина всіх його центральних

вершин.

39