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

Нахождение центра ориентированного графа

Идеально сбалансированные бинарные деревья | Бинарные деревья поиска | Сбалансированные деревья поиска | Операции над деревьями | Вставка элемента в АВЛ-дерево | Основные определения ориентированных графов | Представление ориентированных графов | Операторы над ориентированными графами | Нахождение кратчайшего пути на ориентированном графе | Нахождение кратчайших путей между парами вершин |


Читайте также:
  1. A. підготовка балонів, готування концентрату, герметизація балонів, напо-внення балонів пропелентом, перевірка упакування на міцність і герметичність, висушування й упакування
  2. IV. Определение центра нагрузок.
  3. IV. Расчет центральносжатого фундамента под колонну.
  4. J-Lube — Легендарный порошкообразный концентрат
  5. А.С. Шишков приводит свидетельство ученого иностранца, графа Мейстера.
  6. Агитаторы в торговых центрах
  7. Б. Концентрация на слове

Определим понятие центральной вершины орграфа. Пусть v - произвольная вершина орграфа G=(V, E). Эксцентриситет (максимальное удаление) вершины v определяется как

max{минимальная длина пути от вершины w до вершины v }.

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

Рассмотрим помеченный орграф, показанный на рис. 46. В этом графе

Рис. 46 – Помеченный орграф

 

вершины имеют следующие эксцентриситеты.

 

Откуда видно, что центром данного орграфа является вершина d.

Пусть С – матрица стоимостей для орграфа G. Тогда центр орграфа можно найти, применив следующий алгоритм.

1. Применить алгоритм Флойда к матрице С для вычисления матрицы А, содержащей все кратчайшие пути орграфа G.

2. Найти максимальное значение в каждом столбце i матрицы А. Это значение равно эксцентриситету вершины i.

3. Найти вершину с минимальным эксцентриситетом. Она и будет центром графа G.

Матрица всех кратчайших путей для орграфа из рис. 46 представлена на рис. 47. Максимальные значения в каждом столбце приведены под матрицей.

 

Рис. 47 – Матрица кратчайших путей

 


Дата добавления: 2015-07-16; просмотров: 390 | Нарушение авторских прав


<== предыдущая страница | следующая страница ==>
Транзитивное замыкание| Обход ориентированных графов

mybiblioteka.su - 2015-2024 год. (0.005 сек.)