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

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

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

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

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

В этом графе вершины имеют следующие эксцентриситеты.

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

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

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

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

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

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

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