Разстояние в графики
Нека G = (V, X) е свързан неориентиран граф.
v1,v2 са неговите два несъвпадащи върха.
Дефиниция:Разстояниетомеждувърховетеvi иvj е дължината на най-късия (vi ,vj) – маршрут. Означава се ρ (vi,vj).
Разстоянието, въведено по този начин, удовлетворява следните метрични аксиоми:
5) ρ (vi,vj) T = P, т.е. матрицата P е симетрична.
Дефиниция: За фиксиран връхv, стойността
e(v) = max v,w)wV> се наричаексцентричностна върхаv. По този начин ексцентричността на върха е равна на разстоянието от даден връх до най-отдалечения от него.
Ако P е матрица на разстоянието, тогава ексцентричността e(vi) е равна на най-голямото от числата в i-тия ред.
Дефиниция:Диаметър на графика G е ексцентрицитетът, който е максимален сред всички ексцентрицитети на върха.
Означава се d(G). d(G) = max v i) /vi V>.
Дефиниция: Връхvсе наричапериферен, ако e(v) = d(G).
Дефиниция: Най-малкият от ексцентрицитетите на графика G се нарича неинрадиус. Означава се с r(G), т.е. r(G) = min v i)vi V >.
Дефиниция: Връхvсе наричацентрален, ако e(v) = r(G).
Дефиниция: Наборът от всички централни върхове на граф се нарича неговцентър.
Съставете матрицата на разстоянието P =
e(1) = 2, e(2) = 1, e(3) = 2. e(4) = 2, e(5) = 2, тогава
d(G) = 2. Периферни върхове: 1, 3, 4, 5.
r(G) = 1, център . (центърът може да се състои от няколко върха).
Теорема : В пълната графика Knd(Kn) = r(Kn) = 1 (тъй като всички отделни върхове на Kn са съседни).
Проблемът с намирането на централните върхове възниква в практическата дейност на хората.
Например графът е мрежа от пътища, т.е. върховете съответстват на населените места, а ръбовете съответстват на пътищата между тях. Изисква се оптимално локализиране на болници, пунктове за обслужване и др. В такива ситуации оптимизацията се състои в минимизиране на разстоянието от пункта за обслужване до най-отдалеченото населено място. Следователно разположенията трябва да са централните върхове на графиката. Реалните задачи се различават от тази идеална по това, че трябва да се вземат предвид други обстоятелства - разстояния между населените места, цена, време за пътуване и т.н. За отчитане на тези параметри се използват претеглени графики (заредени).