• a24plus: Я - нейросеть а24+. Помогу с решением задачи

Готовлю ответ ...

Медиана графа – такая вершина x, суммарное расстояние от которой до всех остальных вершин графа минимально.Cуммарное расстояние от вершины до всех остальных вершин – СВВ(i) определяется соотношением СВВ(i)= Σdi,j  – суммарное расстояние от вершины i до всех j.

СВВ(x)=min {СВВ(i)}

Заметим, что сумма значений элементов i-й строки матрицы DN расстояний вершина-вершина равна сумме расстояний от вершины ко всем остальным вершинам графа, т. е. равна СВВ(i). Следовательно, медиана соответствует любой строке матрицы DN, для которой сумма значений элементов минимальна. Элементы матрицы DN могут быть расчитаны с помощью алгоритма Флойда или Данцига. Представим теперь алгоритм поиска медианы.
Алгоритм поиска медианы.

    • находим D0 – матрица, элементами которой являются ai,j – длины кратчайших дуг;
    • Ищем  DN –  матрицу длин кратчайших путей между всеми вершинами графа по Флойду или Данцигу;
    • Определяем  СВВ(i);
    • Из всех СВВ(i) выбираем наименьшее, соответствующая вершина и будет медианой;

Пример
Необходимо определить медиану для графа представленого на рисунке:

граф для которого нужно найти медиану

Пронумеруем вершины исходного графа, и составим матрицу длин кратчайших дуг между каждой парой вершин D0, в случае, если дуги между вершиной i и j не существует, элементу ai,j матрицы присваивается значение ∞. Исходный граф с пронумероваными вершинами представлен на рисунке ниже.

граф с пронумерованными вершинами

Матрица D0:

D0= 0 12 28
12 0 10 43
10 0 10
28 43 17
0
31 10 0 8
14 0 6
6 0

C помощью алгоритма Флойда или Данцега получаем матрицу длин кратчайших путей между каждой парой вершин графа:

D7= 0 12 22 28 32 40 46
12 0 10 40 20 28 34
22 10 0 50 10 18 24
28 27 17 0 27 35 41
32 20 10 60 0 8 14
46 34 24 74 14 0 6
52 40 30 80 20 6 0

Основываясь на полученой нами матрице длин кратчайших путей, найдем CВВ(i) для каждой вершины графа

CВВ(i)=Σdi,j.

CВВ(1)==Σjd(1, j)=180
CВВ(2)==Σjd(2, j)=144
CВВ(3)==Σjd(3, j)=134
CВВ(4)==Σjd(4, j)=175
CВВ(5)==Σjd(5, j)=144
CВВ(6)==Σjd(6, j)=198
CВВ(7)==Σjd(7, j)=228
Медианой графа является такая вершина x, для которой СВВ(x)=min{СВВ(i)}. Минимальное значение имеет СВВ(3)=134, а это значит, что вершина 3 является медианой графа.

   
5.0
Yanahelp
НТУ "ХПИ", 2012 г., специалист. Опыт работы в написании: контрольных, курсовых, дипломных работ и рефератов более 9-ти лет. Работы выполняю ответственно, в срок или даже раньше! Владею русским и украинским языками.