3.2.2. Расстояния в графе. Диаметр, центр, радиус графа

Утверждение. Если для двух вершин существует маршрут, связывающий их, то обязательно найдется минимальный маршрут, соединяющий эти вершины. Обозначим длину этого маршрута через d(v, w).

Определение.

Величину d(v, w) (конечную или бесконечную) будем называть расстоянием между вершинами v, w. Это расстояние удовлетворяет аксиомам метрики: d(v, w) ? 0, причем d(v, w) = 0 тогда и только тогда, когда v=w; d(v, w) = d(w, v); d(v, w) £ d(v, u) + d(u, w).

Определение. Диаметром связного графа называется максимально возможное расстояние между двумя его вершинами.

Определение. Центром графа называется такая вершина, что максимальное расстояние между ней и любой другой вершиной является наименьшим из всех возможных; это расстояние называется радиусом графа.

Пример 82.

Для графа G, изображенного на рисунке 34, найти радиус, диаметр и центры.

Решение.

Чтобы определить центры, радиус, диаметр графа G, найдем матрицу D(G) расстояний между вершинами графа, элементами dij которой будут расстояния между вершинами vi и vj. Для этого воспользуемся графическим представлением графа. Заметим, что матрица D(G) симметрична относительно главной диагонали.

С помощью полученной матрицы для каждой вершины графа G определим наибольшее удаление из выражения: для i, j = 1, 2, …, 5. В результате получаем: r(v1) = 3, r(v2) = 2, r(v3) = 2, r(v4) = 2, r(v5) = 3. Минимальное из полученных чисел является радиусом графа G, максимальное – диаметром графа G. Значит, R(G) = 2 и D(G) = 3, центрами являются вершины v2, v3, v4.

<< | >>
Источник: Лекции - Дискретная математика. 2016

Еще по теме 3.2.2. Расстояния в графе. Диаметр, центр, радиус графа:

  1. Глоссарий:
  2. Технологическое правило построения сетевых моделей.
  3. РАЗРАБОТКА ШТАБА ВМФ О ВЫСАДКЕ В АНГЛИЮ
  4. Осмотр места взрыва
  5. § 1. Следы рукЗначениеследов рук
  6. ОСМОТР ОГНЕСТРЕЛЬНОГО ОРУЖИЯ И СЛЕДОВ ЕГО ДЕЙСТВИЯ
  7. § 4. Защита культурных ценностей во время вооруженных конфликтов
  8. ГИПАТИЯ, ИЛИ РАСТЕРЗАННАЯ МУЗА. К 1600-ЛЕТИЮ КАЗНИ ОТ РУК ФАНАТИКОВ-ХРИСТИАН
  9. АристархСамосский
  10. Космология Бруно
  11. 3.1. Элементы теории графов
  12. §4. Рамус о геометрических определениях.
  13. § 2. Динамика