Студопедия

КАТЕГОРИИ:

АстрономияБиологияГеографияДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРиторикаСоциологияСпортСтроительствоТехнологияФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника


Расстояние в графах




Пусть G = (V, X) – связный неориентированный граф.

v 1, v 2 – две его несовпадающие вершины.

Определение: Расстоянием между вершинами v i и v j называется длина кратчайшего (v i , v j) – маршрута. Обозначается ρ (v i , v j).

Введенное таким образом расстояние удовлетворяет следующим аксиомам метрики:

1) ρ (v i , v j) ≥ 0;

2) ρ (v i , v j) = 0 <=> v i = v j (если i = j);

3) ρ (v i , v j) = ρ (v i , v j) – симметричность;

4) ρ (v i , v j) ≤ ρ (v i ,w) + ρ (w , v j) – неравенство треугольника;

5) ρ (v i , v j) < ∞

Определение: Пусть G = (V, X). Если V = { v 1, v 2, …, v n}, то матрицейрасстояний называется матрица P = [ p ij] порядка n, у которой:

p ij = ρ(v i,v j) (i = 1,…, n; j = 1,…, n)

Замечание: PT = P, т. е. матрица P симметрична.

Определение: Для фиксированной вершины v величина

е(v) = max {ρ(v,w) | w V} называется эксцентриситетом вершины v. Таким образом, эксцентриситет вершины равен расстоянию от данной вершины до наиболее удаленной от нее.

Если P – матрица расстояний, то эксцентриситет е(v i) равен наибольшему из чисел, стоящих в i-й строке.

Определение: Диаметромграфа G называется эксцентриситет, максимальный среди всех эксцентриситетов вершин.

Обозначается d(G). d(G) = max {е(v i) / v i V }.

Определение:Вершина v называется периферийной, если е(v) = d(G).

Определение: Минимальный из эксцентриситетов графа G называется его радиусом. Обозначается r(G), т. е. r(G) = min {е(v i) | v i V }.

Определение: Вершина v называется центральной, если е(v) = r(G).


Поделиться:

Дата добавления: 2015-01-29; просмотров: 93; Мы поможем в написании вашей работы!; Нарушение авторских прав





lektsii.com - Лекции.Ком - 2014-2024 год. (0.008 сек.) Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав
Главная страница Случайная страница Контакты