Page 41 - 4386

Якщо e(v)=D(G), то вершина v називається периферійною.

Діаметр графа дорівнює 1 тоді і тільки тоді, коли граф

повний. У повному графі ексцентриситети всіх вершин рівні,

тому його центр збігається з множиною всіх вершин. Крім того,

D(K )=R(K ) у довільному повному графі K .
n
n
n
Для довільного зв’язного графа G виконується
R(G)≤D(G)≤2R(G).

Для визначення центра і радіуса графа необхідно

побудувати для нього матрицю відстаней D, кожен елемент якої

d описує відстань між вершинами i та j графа G, тобто
i,j
d =d(v , v ). Очевидно, що матриця відстаней D симетрична щодо
j
i
i,j
головної діагоналі (елементи якої дорівнюють нулю, тому що
d(v ,v )=0).
i
i
Приклад 3.9. Визначити центр, периферійні вершини,

радіус і діаметр графа G, зображеного на рис. 3.7.

Рисунок 3.7

Розв'язок.

Матриця відстаней D графа G зображена на рис. 3.8.

Знайдемо ексцентриситет кожної вершини e(v ): e(v )=4,
i
1
e(v )=3, e(v )=2, e(v )=3, e(v )=3, e(v )=4, e(v )=4, e(v )=4, e(v )=4.
9
8
6
3
2
4
7
5
Отже, згідно з визначеннями, центром графа є вершина v ,
3
периферійними вершинами є v , v , v , v , v . Радіус графа R(G)=2,
9
6
1
8
7
діаметр графа D(G)=4.
40