*** Метрика на графах ***
Пусть дан граф G = (X,E)
• Определение №1: ( Расстояние)
Расстоянием между 2-мя вершинами графа G наз-ся длина кратчашей цепи, соединяющей эти вершины в графе G.
• Аксиомы метрики:
1) d(x,x) = 0;
2) d(x,y) = d(y,x);
3) d(x,y) >= 0;
4) d(x,y) + d(y,z) >= d(x,z)
• Определение №2: ( Эксцентриситет )
Величина e(x) = max d(x,y), где x,y € X наз-ся эксцентриситетом вершины х.
• Определение №3: ( Радиус )
Радиус графа G - это величина r(G) = min e(x), где х € Х.
• Определение №4: ( Центральная вершина )
Вершина, эксцентриситет которой равен радиусу графа наз-ся центральной вершиной.
В общем случае может быть несколько центральных вершин.
• Определение №5: ( Центр )
Множество всех центральных вершин графа называется центром графа.
• Определение №6: ( Диаметр )
Величина d(G) = max e(x), где х € Х, называется диаметром графа.
• Определение №7: ( Переферия )
Вершины, эксцентриситет которых равен диаметру графа, называются переферийными.
• Определение №8: ( Диаметральная цепь )
Цепь, длина которой совпадает с диаметром графа называется диаметральной цепью
->Пример:
e(x) = max{0,1,2,1,2} = 2
e(y) = max{1,0,1,1,2} = 2
e(z) = max{2,1,0,1,1} = 2
e(u) = max{1,1,1,0,1} = 1
e(w) = max{1,1,1,0,1} = 1
=> r(G) = 1, центр графа -> u
d(G) = 2
Переферия {x,y,z,w}