Инструменты пользователя

Инструменты сайта


examination:diskretka:question13

Вопрос №13. Расстояния в неориентированном графе

Пусть G - связный неориентированный граф (V, E)

v,w ∈V

ρ(v,w)=min length(M), M - маршрут из v в w

Отметим, что в силу условия связности величина ρ всегда определена; мы будем называть ее расстоянием от v до w в графе G.

В силу предыдущего § маршрут реализующий расстояние от v до w заведомо является простой цепью; таких маршрутов может быть больше 1.

Перед тем, как перечислить основные свойства ρ, отметим, что ρ принимает только неотрицательные целые значения .

Свойства расстояния: Перечисленные ниже свойства не являются специфичными для нашей функции ρ, а являются стандартными свойствами любого расстояния в произвольном метрическом пространстве.

  1. ρ(v,w)≥0
  2. ρ(v,w)=0 т.т.т.к. v=w
  3. ρ(v,w)=ρ(w,v)
  4. ρ(v,w)≤ρ(v,u)+ρ(u,w)

В силу симметрии мы говорим не расстояние от v до w, а расстояние между v и w.

examination/diskretka/question13.txt · Последние изменения: 2014/01/15 12:14 (внешнее изменение)