ТОР 5 статей: Методические подходы к анализу финансового состояния предприятия Проблема периодизации русской литературы ХХ века. Краткая характеристика второй половины ХХ века Характеристика шлифовальных кругов и ее маркировка Служебные части речи. Предлог. Союз. Частицы КАТЕГОРИИ:
|
Нахождение центра ориентированного графаОпределим понятие центральной вершины орграфа. Пусть v - произвольная вершина орграфа G=(V, E). Эксцентриситет (максимальное удаление) вершины v определяется как max{минимальная длина пути от вершины w до вершины v }. Центром орграфа G называется вершина с минимальным эксцентриситетом, т.е. это вершина, для которой максимальное расстояние (длина пути) до других вершин минимально. Рассмотрим помеченный орграф, показанный на рис. 46. В этом графе Рис. 46 – Помеченный орграф
вершины имеют следующие эксцентриситеты.
Откуда видно, что центром данного орграфа является вершина d. Пусть С – матрица стоимостей для орграфа G. Тогда центр орграфа можно найти, применив следующий алгоритм. 1. Применить алгоритм Флойда к матрице С для вычисления матрицы А, содержащей все кратчайшие пути орграфа G. 2. Найти максимальное значение в каждом столбце i матрицы А. Это значение равно эксцентриситету вершины i. 3. Найти вершину с минимальным эксцентриситетом. Она и будет центром графа G. Матрица всех кратчайших путей для орграфа из рис. 46 представлена на рис. 47. Максимальные значения в каждом столбце приведены под матрицей.
Рис. 47 – Матрица кратчайших путей
Не нашли, что искали? Воспользуйтесь поиском:
|