n="justify"> Завдання 6
Організувати граф матричним способом і побудувати порядкову функцію, функцію Гранді.
Рішення:
В основі алгоритму упорядкування лежить матриця суміжності.
X1X2X3X4X5X101100X200010X300011X400000X500000 Таблиця
L 121200 L 2000 **
Ізоморфне упорядкований граф виглядає наступним чином:
Функція Гранді:
Порядкова функція:
Завдання 7
Визначити метричні характеристики графа: діаметр, радіус, ексцентриситет кожної вершини, центральні вершини.
Рішення:
. Визначимо відстані між парами вершин:
(x1, x2)=1 (x1, x3)=1 d (x2, x3)=2 (x1, x4)=2 d (x2, x4)=1 d (x3, x4)=1 (x1 , x5)=2 d (x2, x5)=3 d (x3, x5)=1 d (x4, x5)=2
. Визначимо діаметр як
d (G)=max d (xi, xj): d (G)=3
. Визначимо ексцентриситет кожної вершини:
r (x1)=2 r (x2)=3 r (x3)=2 r (x4)=2 r (x5)=3
. Визначимо радіус графа як
r (G)=min r (xi): r (G)=2
граф функція діаметр матричний
5. Визначимо центральні вершини: x1, x3, x4.
