Разработка системы планирования размещения точек водоснабжения в населенных пунктах

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

Министерство образования, науки, молодежи и спорта Украины

Донецкий Национальный Университет

Кафедра прикладной математики и

теории систем управления

Курсовая работа

На тему

«Разработка системы планирования размещения точек водоснабжения в населенных пунктах»

Выполнила

студентка гр. «4-И(ММ)»

математического фак-та

Беспалая Анна

Научный руководитель

доцент кафедры ПМ и ТСУ

Вайсруб Н. В.

2011г.

Содержание

Введение

Раздел 1. Актуальность использования информационных технологий для планирования размещения точек водоснабжения в населенных пунктах

1.1 Рост проблем водоснабжения в связи с ухудшением экологической ситуации

1.2 Задача оптимального размещения точек водоснабжения в населенных пунктах и их решения

1.1 Рост проблем водоснабжения в связи с ухудшением экологической ситуации

1.3 Актуальность использования информационных технологий для планирования размещения точек водоснабжения в населенных пунктах

1.4 Постановка задачи

Выводы к разделу 1

Раздел 2. Задача о размещении медиан в графе и методы ее решения

2.1 Основные понятия теории графов

2.2 Понятие медианы

2.3 Методы нахождения медиан графа

2.4 Алгоритм нахождения медиан графа

2.5 Примеры нахождения медиан графа

Выводы к разделу 2

Раздел 3. Программная реализация системы планирования размещения

точек водоснабжения в населенных пунктах

3.1 Описание функциональных возможностей разрабатываемого приложения

3.2 Информационная структура приложения. Программная реализация основных модулей

Выводы к разделу 3

Заключение

Список использованной литературы

Приложения

Введение

В настоящее время существует масса проблем, связанных с ухудшением экологической ситуации окружающей среды. К ним относится и занимает немало важное место и проблемы загрязнения водных ресурсов, которое связано с проблемами водоснабжения.

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

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

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

Раздел 1. Актуальность использования информационных технологий для планирования размещения точек водоснабжения в населенных пунктах

1.1 Рост проблем водоснабжения в связи с ухудшением экологической ситуации

Главная проблема водоснабжения -- нехватка чистой воды, загрязнение вод рек и озер бытовыми и промышленными стоками, стоками животноводческих комплексов. Поэтому необходимо широко внедрять системы оборотного водоснабжения, очистки сточных вод и их использования.

Водные ресурсы являются одним из наиболее важных и вместе с тем наиболее уязвимых компонентов окружающей среды. Их быстрое изменение под влиянием хозяйственной деятельности приводит к обострению ниже описанных проблем.

Нельзя допустить большие потери воды. Они велики не только на пути от водоисточника до потребителя (так, в 1991 г. при суммарном объеме забора воды из природных источников 117 км³, потери составили 9,1 км³), но весьма значительны и в промышленности - 25% и более (за счет утечек в сетях, фильтрации, несовершенства технологических процессов); в жилищно-коммунальном хозяйстве - от 20 до 40% (за счет утечек в жилых и общественных зданиях, коррозии и износа водопроводных сетей); в сельском хозяйстве (переполивы в растениеводстве, завышенные нормы подачи воды для целей животноводства).

Сохраняется многолетняя тенденции нарастания загрязнения поверхностных вод. Годовой объем сброшенных стоков за последние 5 лет практически не изменился и составляет 27 км³. Со сточными водами промышленности, сельского и коммунального хозяйства и водные объекты поступает огромное количество загрязняющих веществ. [7]

Результаты проверки качества водных источников показали: только12% обследованных водных объектов можно отнести к условно чистым (фоновым); 32% - находятся в состояний антропогенного экологического напряжения (умеренно загрязненные); 56% - являются загрязненными годными объектами (или их участками), экосистемы которых находятся в состоянии экологического регресса.

Питьевая вода в настоящее время далеко не высокого качества, показатели которого постоянно ухудшаются. Состояние водных источников (поверхностных и подземных) и систем централизованного водоснабжения не может гарантировать требуемого качества питьевой воды (191). Более 50% жителей вынуждены пользоваться водой, не соответствующей стандартам по различным показателям. Более 20% проб питьевой воды не удовлетворяет действующим нормам по химическим показателям и более 11% по микробиологическим, 4,3% проб питьевой воды представляют реальную опасность для здоровья населения. Основными причинами ухудшения качества питьевой воды являются: несоблюдение режима хозяйственной деятельности в зонах санитарной охраны (17% водоисточников и 24% коммунальных водопроводов из поверхностных источников вообще не имеют санитарно-охранных зон); отсутствие в ряде-случаев очистных сооружений на коммунальных водопроводах (13,1%) и обеззараживающих установок (7,2%), а также вторичное загрязнение воды в разводящих сетях при авариях, количество которых ежегодно возрастает .[8]

Поэтому в связи с ухудшением экологической ситуации окружающей среды тем самым возрастают проблемы водоснабжения. Для решения этих проблем рассмотрим задачи оптимального размещения точек водоснабжения в населенных пунктах.

1.2 Задача оптимального размещения точек водоснабжения в населенных пунктах и их решения

На сегодняшний день существует немало оптимизационных задач для размещения точек в населенных пунктах и за их пределами. К этим задачам относятся статистические, математические методы, а также методы для решения конкретных задач. Статистические методы основаны на общенаучных и экономико-географических методах обработки статистических данных, а с помощью математических методов есть возможность быстро обрабатывать цифровой материал и получать количественные оценки анализируемых явлений.

Рисунок 1. «Карта населенных пунктов»

В данной работе мы рассмотрим задачу оптимального размещения некоторого количества точек водоснабжения, в которой предусматривается, что сумма кратчайших расстояний от населенных пунктов до точек водоснабжения - минимальна. Будем располагать точки водоснабжения на графе, где населенные пункты - вершины графа, оптимально-расположенные точки водоснабжения - медианы графа, а расстояния между этими вершинами являются дугами, которые имеют заданный весовой коэффициент (см. рисунок 1). Таким образом, нам необходимо так расположить точки водоснабжения, чтобы сумма кратчайших расстояний от населенных пунктов до этих точек была минимально возможной. Оптимальное в указанном смысле место расположения точки называется медианой графа. Для решения поставленной задачи будем использовать алгоритм нахождения медиан заданного графа.

1.3 Актуальность использования информационных технологий для планирования размещения точек водоснабжения в населенных пунктах

Актуальность данной работы обусловлена тем, что большинство населения земли проживает в таких регионах, где наблюдается острая нехватка водных ресурсов, из-за чего значительно обостряется конкуренция в использовании поверхностных водных ресурсов. В этих условиях современные крупные города в равной степени нуждаются в разработке концепции развития не только питьевого водоснабжения, где принципиальные вопросы многими государствами в основном решены, но и технического водоснабжения, имеющего свою специфику решения различных водохозяйственных задач. Поэтому требуется решение задач относительно учета факторов риска при обосновании стратегий для вариантов инновационного развития, ресурсного обеспечения и оценки потенциала инфраструктуры водоснабжения городов.

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

Практическая значимость: предложенная программа может быть использована также как для оптимального размещения любого производства (например, больницы, пожарные части, сберегательные банки, товарные склады и т.п.) от населенных пунктов, так и для минимизации финансовых средств от транспортных перевозок. Также в различных формах часто встречаются задачи при выборе места расположения коммутаторов в телефонной сети, подстанций в электросетях, баз снабжения (складов) в сети дорог (где вершины представляют потребителей), отделов сортировки в почтовой связи и др.

1.4 Постановка задачи

Постановка задачи заключается в разработке программы, которая позволяет для заданной карты населенных пунктов, представленной с помощью связного неориентированного графа, определить размещение некоторого количества точек водоснабжения (медиан графа) так, чтобы сумма кратчайших расстояний от населенных пунктов (вершин графа) до точек водоснабжения была минимальной. Для нахождения медиан будем использовать алгоритм Флойда, который базируется на нахождении кратчайшего пути между всеми парами вершин графа.

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

Выводы к разделу 1

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

В большой мере этому способствует прогресс в области развития больших быстродействующих вычислительных машин. Поэтому особенно актуально использование информационных технологий для планирования размещения точек водоснабжения.

В связи с этим пользуясь разработками теоретико-методологических и методических основ концепции управления параметрами системы водоснабжения городов мы легко можем решить задачу оптимального расположения точек водоснабжения, применяя различные алгоритмы анализа графов. А чтобы рассмотреть эти алгоритмы для начала необходимо ознакомится с основными понятиями теории графов, рассмотренных в следующей главе.

Раздел 2. Задача о размещении медиан в графе и методы ее решения

2.1 Основные понятия теории графов

Граф G задается множеством точек (вершин) (которое обозначается через множество X) и множеством линий (ребер, дуг) (обозначаемых множеством A), соединяющих между собой все или часть этих точек. Граф задается парой (X,А).

Граф называют ориентированным (рис. 2), если его пары и (где ) считают различными. В графе ребро соединяет точку с и имеет направление из вершины в .

Рисунок 2. «Ориентированный граф»

Граф называют неориентированным (рис.3), если порядок записи элементов в парах и (где ) не имеет значения.



Рисунок 3.«Неориентированный граф»

Петлей называется дуга, начальная и конечная вершины которой совпадают.

Граф со взвешенными дугами - это граф, дугам которого приписаны (сопоставлены) некоторые числа , называемые весом (длиной, стоимостью или ценой) пути.

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

Две дуги называются смежными, если они различны и имеют общую вершину (независимо от того, является ли эта точка началом или концом для каждой из дуг).

Помеченный граф (или перенумерованный) - граф, вершины которого отличаются одна от другой какими-либо пометками. В качестве пометок обычно используются буквы или целые числа.

Степенью вершины в графе G называется число рёбер, инцидентных (т. е. количество ребер, имеющих граничной вершину).

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

Простая цепь - цепь, у которой все ребра различны. В противном случае цепь называют составной.

Цикл - это конечная цепь, начинающаяся в некоторой вершине и заканчивающаяся в той же вершине . Если в цикле все ребра различны, то его называют простым, в противном случае его называют составным.

Цикл с отрицательной суммарной длиной - цикл, обходя который, путь будет иметь сколь угодно малый вес .

Матрица весов - матрица , элементами которой являются длины дуг графа.

Путь - это последовательность дуг, в которой конечная вершина всякой дуги, отличной от последней, является начальной для следующей дуги.

Маршрут - это последовательность ребер в которой каждое ребро , за исключением, возможно, первого и последнего ребер, связано с ребрами и своими двумя концевыми вершинами.

Путь между двумя вершинами называется кратчайшим, если его стоимость минимальна среди стоимостей всех возможных путей между этими двумя вершинами .[4,6]

2.2 Понятие медианы

Для простоты изложения начнем с рассмотрения задачи о размещении точек водоснабжения на графе.

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

Исходя из природы целевой функции, такие задачи называются минисуммными задачами размещения.

В данной работе мы будем рассматривать минисуммные задачи размещения. В частности рассмотрим задачу о нахождении p-медианы данного графа G; это задача о размещении заданного числа (скажем, p) точек водоснабжения, при которых сумма кратчайших расстояний от вершин графа G до ближайших населенных пунктов принимает минимально возможное значение.

А теперь определим что является медианой.

Задача о p-медиане может быть несколько обобщена, если каждой вершине x_j сопоставить некоторый вес v_j (представляющий, например, ее размер и важность); тогда целевой функцией, подлежащей минимизации, станет сумма «взвешенных» расстояний.

Пусть дан граф G = (X, Г). Для каждой вершины x_i ? X (здесь и далее суммирование ведется по всем x_i ? X)

у_o(x_i) = ? v_j d(x_i, x_j) -- внешнее передаточное число,

у_t(x_i) = ? v_j d(x_j, x_i) -- внутреннее передаточное число,

где d(x_i, x_j) -- кратчайшее расстояние от вершины x_i до вершины x_j.

Вершина x_o*, для которой у_o(x_o* ) = min [ у_o(x_i) ], называется внешней медианой графа G, а вершина x_t*, для которой у_t(x_t*) = min [ у_t(x_i) ], называется внутренней медианой графа G.

Рассмотрим выбор точек водоснабжения.

Для этого вернемся к нашей задаче. Итак, повторюсь, что точки водоснабжения можно представить в виде вершин графа, а дороги, проложенные до населенных пунктов -- дуги. На практике каждой вершине присваивается вес v_j, представляющий ее «важность» (например, v_j может быть числом, равным длине пути, измеряемый, например, в километрах).

В этом случае задача сводится к нахождению места для размещения точек водоснабжения, чтобы сумма расстояний до населенных пунктов было минимальным. Таким образом, возвращаясь к обозначениям, введенным выше, необходимо найти такую вершину x_o,t*, чтобы сумма внешних и внутренних передаточных чисел была наименьшей. Тогда вершина x_o,t* может быть названа внешне-внутренней медианой. Далее покажем, что точка x_o,t* является оптимальной, т. е. для любой другой точки графа (вершины или произвольной точки дуги) общее расстояние при условии, что в этой точке будет располагаться точка водоснабжения, будет не меньше, чем для вершины x_o,t*.

Обобщим понятие медианы, определив p-медиану.

Пусть X_p -- подмножество множества вершин X графа G = (X, Г), и положим, что X_p содержит p вершин. Переопределим следующие обозначения

d(X_p, x_j) = min [ d(x_i, x_j) ] и d(x_j, X_p) = min [ d(x_j, x_i) ],

где минимум ищется по всем x_i ? X.

Если x_i? -- вершина из X_p, на которой достигается минимум в предыдущих формулах, то говорят, что вершина x_j прикреплена x_i?. Передаточные же числа множества вершин X_p определяются аналогично передаточным числам одиночной вершины:

у_o(x_i) = ? v_j d(X_p, x_j) -- внешнее передаточное число,

у_t(x_i) = ? v_j d(x_j, X_p) -- внутреннее передаточное число.

Множество же X_o*, для которого у_o(X_o*) = min [ у_o(x_i) ] (минимум ищется по всем X_p ? X), называется внешней p-медианой графа G, аналогично определяется внутренняя p-медиана.

Понятно, что нахождение p-медианы используя непосредственно вышеуказанные формулы нецелесообразно с вычислительной точки зрения.

Далее рассмотрим абсолютные p-медианы.

Для упрощения задачи будем далее рассматривать неориентированный граф G. Т. о. индексы t и o будут отсутствовать, т. к. внешние и внутренние передаточные числа будут совпадать. Точку графа (вершина или точка дуги), для которой передаточное число будет принимать наименьшее значение, будем называть абсолютной медианой графа G. [1]

2.3 Методы нахождения медиан графа

Существует несколько методов нахождения медиан графа.

К этим методам относятся:

1). Метод Беллмана-Форда.

Данный метод был предложен независимо Ричардом Бел-лманом и Лестером Фордом и позволяет найти кратчайшие пути из одной вершины ко всем остальным вершинам, для случая, когда веса ребер могут быть отрицательными.

Алгоритм вернет значение true, если в графе нет отрицательных циклов, и false, если таковой цикл имеется. Если в графе есть отрицательные циклы, то задача о поиске кратчайших путей (по крайней мере, для некоторых вершин) не существует [6].

2) Метод Дейкстры.

Этот метод основан:

- на приписывании вершинам графа временных пометок, причем пометка вершины дает верхнюю границу длины пути от к этой вершине;

- пометки (их величины) постепенно уменьшаются с помощью некоторой итеративной процедуры;

- на каждом шаге итерации одна из временных меток становится постоянной, т. е. эта пометка уже не является верхней границей, а дает длины кратчайшего пути от вершины к рассматриваемой вершине.

3) Эвристический метод.

Тейц и Барт предложили эвристический метод для нахождения p-медианы. Метод состоит в следующем: случайным образом выбираются p вершин, они образуют начальное множество S, аппроксимирующее p-медианное множество X_p*. Затем выясняется, может ли некоторая вершина x_j ? X \ S заменить вершину x_i ? S (как медианная вершина), для чего строят новое множество S* = (S ? {x_j}) \ {x_i} и сравнивают передаточные числа у(S*) и у(S). Если у(S*) < у(S), то S заменяют на S*, которое лучше аппроксимирует p-медианное множество X_p*. Затем аналогично исследуется множество S* и т. д., пока не будет построено множество S^, которое нельзя будет изменить по вышеуказанному принципу.

4). Метод Флойда.

Один из наиболее эффективных методов решения задачи о нахождении медиан графа предложил Флойд.

В данной работе мы находим медианы неориентированного графа.

Этот метод применяют, если необходимо найти кратчайшие пути между всеми парами вершин. Метод базируется на использовании последовательности из n преобразований начальной матрицы весов . При этом на каждой итерации матрица представляет собой длины кратчайших путей между каждой парой вершин с тем ограничением, что путь между и ; (для любых и) содержит в качестве промежуточных только вершины из множества .

2.4 Алгоритм нахождения медиан графа

Пользуясь рассмотренным выше методом Флойда распишем пошагово алгоритм нахождения медиан графа.

Предположим, что в начальной матрице весов для всех и , если в графе отсутствует дуга .

Присвоение начальных значений

Шаг 1. Положить.

Итерация:

Шаг 2. .

Шаг 3. Для всех , таких, что , и для всех , так,

что , введем операцию: .

Проверка на окончание:

Шаг 4. (а) Если , то в графе существует цикл

отрицательного веса, содержащий вершину и решения нет.

Остановка алгоритма.

(б) Если все и , то получено решение. Матрица

дает длины всех кратчайших путей. Остановка алгоритма.

(в) Если все и , то вернуться к шагу 2. [2]

2.5 Примеры нахождения медиан графа

Рассмотрим 2 примера, используя алгоритм Флойда. При чем в первом примере мы находим 1 медиану, а во втором 2.

Пример 1

Рисунок 4. «Пример 1»

Необходимо найти медиану графа (их может быть несколько).

Решение:

1. Получим матрицу длин кратчайших путей для заданного графа (см. рисунок 4). Применим для этого алгоритм Флойда.

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

D0: 0 3 ? ?

? 0 5 ?

? ? 0 7

6 ? ? 0

На основании матрицы D0, вычислим последовательно все элементы матрицы D1. Для этого мы используем рекуррентное соотношение di,j1=min{ di,10+ d1,j0; di,j0}.

d1,11=min{d1,10+d1,10d1,10}=min{0+0; 0}=0

d1,21=min{d1,10+d1,20d1,20}=min{0+3; 3}=3

d1,31=min{d1,10+d1,30d1,30}=min{0+?; ?}=?

d1,41=min{d1,10+d1,40d1,40}=min{0+?; ?}=?

d2,11=min{d2,10+d1,10d2,10}=min{?+0; ?}=?

d2,21=min{d2,10+d1,20d2,20}=min{?+3; 0}=0

d2,31=min{d2,10+d1,30d2,30}=min{?+?; 5}=5

d2,41=min{d2,10+d1,40d2,40}=min{?+?; ?}=?

d3,11=min{d3,10+d1,10d3,10}=min{?+0; ?}=?

d3,21=min{d3,10+d1,20d3,20}=min{?+3; ?}=?

d3,31=min{d3,10+d1,30d3,30}=min{?+?; 0}=0

d3,41=min{d3,10+d1,40d3,40}=min{?+?; 7}=7

d4,11=min{d4,10+d1,10d4,10}=min{6+0; 6}=6

d4,21=min{d4,10+d1,20d4,20}=min{6+3; ?}=9

d4,31=min{d4,10+d1,30d4,30}=min{6+?; ?}=?

d4,41=min{d4,10+d1,40d4,40}=min{6+?; 0}=0

Представим матрицу D1, включив в нее рассчитанные элементы.

D1: 0 3 ? ?

? 0 5 ?

? ? 0 7

6 9 ? 0

На основании матрицы D1, вычислим последовательно все элементы матрицы D2. Для этого мы используем рекуррентное соотношение di,j2=min{ di,21+ d2,j1; di,j1}.

d1,12=min{d1,21+d2,11d1,11}=min{3+?; 0}=0

d1,22=min{d1,21+d2,21d1,21}=min{3+0; 3}=3

d1,32=min{d1,21+d2,31d1,31}=min{3+5; ?}=8

d1,42=min{d1,21+d2,41d1,41}=min{3+?; ?}=?

d2,12=min{d2,21+d2,11d2,11}=min{0+?; ?}=?

d2,22=min{d2,21+d2,21d2,21}=min{0+0; 0}=0

d2,32=min{d2,21+d2,31d2,31}=min{0+5; 5}=5

d2,42=min{d2,21+d2,41d2,41}=min{0+?; ?}=?

d3,12=min{d3,21+d2,11d3,11}=min{?+?; ?}=?

d3,22=min{d3,21+d2,21d3,21}=min{?+0; ?}=?

d3,32=min{d3,21+d2,31d3,31}=min{?+5; 0}=0

d3,42=min{d3,21+d2,41d3,41}=min{?+?; 7}=7

d4,12=min{d4,21+d2,11d4,11}=min{9+?; 6}=6

d4,22=min{d4,21+d2,21d4,21}=min{9+0; 9}=9

d4,32=min{d4,21+d2,31d4,31}=min{9+5; ?}=14

d4,42=min{d4,21+d2,41d4,41}=min{9+?; 0}=0

Представим матрицу D2, включив в нее рассчитанные элементы.

D2: 0 3 8 ?

? 0 5 ?

? ? 0 7

6 9 14 0

На основании матрицы D2, вычислим последовательно все элементы матрицы D3. Для этого мы используем рекуррентное соотношение di,j3=min{ di,32+ d3,j2; di,j2}.

d1,13=min{d1,32+d3,12d1,12}=min{8+?; 0}=0

d1,23=min{d1,32+d3,22d1,22}=min{8+?; 3}=3

d1,33=min{d1,32+d3,32d1,32}=min{8+0; 8}=8

d1,43=min{d1,32+d3,42d1,42}=min{8+7; ?}=15

d2,13=min{d2,32+d3,12d2,12}=min{5+?; ?}=?

d2,23=min{d2,32+d3,22d2,22}=min{5+?; 0}=0

d2,33=min{d2,32+d3,32d2,32}=min{5+0; 5}=5

d2,43=min{d2,32+d3,42d2,42}=min{5+7; ?}=12

d3,13=min{d3,32+d3,12d3,12}=min{0+?; ?}=?

d3,23=min{d3,32+d3,22d3,22}=min{0+?; ?}=?

d3,33=min{d3,32+d3,32d3,32}=min{0+0; 0}=0

d3,43=min{d3,32+d3,42d3,42}=min{0+7; 7}=7

d4,13=min{d4,32+d3,12d4,12}=min{14+?; 6}=6

d4,23=min{d4,32+d3,22d4,22}=min{14+?; 9}=9

d4,33=min{d4,32+d3,32d4,32}=min{14+0; 14}=14

d4,43=min{d4,32+d3,42d4,42}=min{14+7; 0}=0

Представим матрицу D3, включив в нее рассчитанные элементы.



D3: 0 3 8 15

? 0 5 12

? ? 0 7

6 9 14 0

На основании матрицы D3, вычислим последовательно все элементы матрицы D4. Для этого мы используем рекуррентное соотношение di,j4=min{ di,43+ d4,j3; di,j3}.

d1,14=min{d1,43+d4,13d1,13}=min{15+6; 0}=0

d1,24=min{d1,43+d4,23d1,23}=min{15+9; 3}=3

d1,34=min{d1,43+d4,33d1,33}=min{15+14; 8}=8

d1,44=min{d1,43+d4,43d1,43}=min{15+0; 15}=15

d2,14=min{d2,43+d4,13d2,13}=min{12+6; ?}=18

d2,24=min{d2,43+d4,23d2,23}=min{12+9; 0}=0

d2,34=min{d2,43+d4,33d2,33}=min{12+14; 5}=5

d2,44=min{d2,43+d4,43d2,43}=min{12+0; 12}=12

d3,14=min{d3,43+d4,13d3,13}=min{7+6; ?}=13

d3,24=min{d3,43+d4,23d3,23}=min{7+9; ?}=16

d3,34=min{d3,43+d4,33d3,33}=min{7+14; 0}=0

d3,44=min{d3,43+d4,43d3,43}=min{7+0; 7}=7

d4,14=min{d4,43+d4,13d4,13}=min{0+6; 6}=6

d4,24=min{d4,43+d4,23d4,23}=min{0+9; 9}=9

d4,34=min{d4,43+d4,33d4,33}=min{0+14; 14}=14

d4,44=min{d4,43+d4,43d4,43}=min{0+0; 0}=0

Представим матрицу D4, включив в нее рассчитанные элементы.

D4: 0 3 8 15

18 0 5 12

13 16 0 7

6 9 14 0

В результате, нами получена матрица длин кратчайших путей между каждой парой вершин графа. Ниже представлена таблица путей. Каждый элемент Cij таблицы, это путь из вершины i в вершину j:

Таблица путей 1 2 3 4:

1 - d1-2=1-2 d1-3=1-2-3 d1-4=1-2-3-4

2 d2-1=2-3-4-1 - d2-3=2-3 d2-4=2-3-4

3 d3-1=3-4-1 d3-2=3-4-1-2 - d3-4=3-4

4 d4-1=4-1 d4-2=4-1-2 d4-3=4-1-2-3 -

2. Поиск медианы.

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

CВВ(i)=Уd(i, j).

CВВ(1)==Уjd(1, j)=26

CВВ(2)==Уjd(2, j)=35

CВВ(3)==Уjd(3, j)=36

CВВ(4)==Уjd(4, j)=29

Медианой графа является такая вершина x, для которой СВВ(x)=min{СВВ(i)}. Минимальное значение имеет СВВ(1)=26, а это значит, что вершина 1 является медианой графа.

Пример 2



Рисунок 5. «Пример 2»

1. Получим матрицу длин кратчайших путей для заданного графа (см. рис. 6).

На основании исходных данных формируем матрицу длин кратчайших дуг D⁰, каждый элемент которой равен длине кратчайщей дуги между вершинами i и j. Если такой дуги нет, положим значение элемента равным ?.

На основании матрицы D⁰, вычислим последовательно все элементы матрицы D¹. Для этого мы используем рекуррентное соотношение

d_i,j¹=min{ d_i,1⁰+ d_1,j⁰; d_i,j⁰}.

d_1,1¹=min{d_1,1⁰+d_1,1⁰d_1,1⁰}=min{0+0; 0}=0

d_1,2¹=min{d_1,1⁰+d_1,2⁰d_1,2⁰}=min{0+1; 1}=1

d_1,3¹=min{d_1,1⁰+d_1,3⁰d_1,3⁰}=min{0+?; ?}=?

d_1,4¹=min{d_1,1⁰+d_1,4⁰d_1,4⁰}=min{0+?; ?}=?

d_1,5¹=min{d_1,1⁰+d_1,5⁰d_1,5⁰}=min{0+?; ?}=?

d_1,6¹=min{d_1,1⁰+d_1,6⁰d_1,6⁰}=min{0+?; ?}=?

d_2,1¹=min{d_2,1⁰+d_1,1⁰d_2,1⁰}=min{?+0; ?}=?

d_2,2¹=min{d_2,1⁰+d_1,2⁰d_2,2⁰}=min{?+1; 0}=0

d_2,3¹=min{d_2,1⁰+d_1,3⁰d_2,3⁰}=min{?+?; 2}=2

d_2,4¹=min{d_2,1⁰+d_1,4⁰d_2,4⁰}=min{?+?; ?}=?

d_2,5¹=min{d_2,1⁰+d_1,5⁰d_2,5⁰}=min{?+?; ?}=?

d_2,6¹=min{d_2,1⁰+d_1,6⁰d_2,6⁰}=min{?+?; ?}=?

d_3,1¹=min{d_3,1⁰+d_1,1⁰d_3,1⁰}=min{?+0; ?}=?

d_3,2¹=min{d_3,1⁰+d_1,2⁰d_3,2⁰}=min{?+1; ?}=?

d_3,3¹=min{d_3,1⁰+d_1,3⁰d_3,3⁰}=min{?+?; 0}=0

d_3,4¹=min{d_3,1⁰+d_1,4⁰d_3,4⁰}=min{?+?; 2}=2

d_3,5¹=min{d_3,1⁰+d_1,5⁰d_3,5⁰}=min{?+?; ?}=?

d_3,6¹=min{d_3,1⁰+d_1,6⁰d_3,6⁰}=min{?+?; ?}=?

d_4,1¹=min{d_4,1⁰+d_1,1⁰d_4,1⁰}=min{?+0; ?}=?

d_4,2¹=min{d_4,1⁰+d_1,2⁰d_4,2⁰}=min{?+1; ?}=?

d_4,3¹=min{d_4,1⁰+d_1,3⁰d_4,3⁰}=min{?+?; ?}=?

d_4,4¹=min{d_4,1⁰+d_1,4⁰d_4,4⁰}=min{?+?; 0}=0

d_4,5¹=min{d_4,1⁰+d_1,5⁰d_4,5⁰}=min{?+?; 2}=2

d_4,6¹=min{d_4,1⁰+d_1,6⁰d_4,6⁰}=min{?+?; ?}=?

d_5,1¹=min{d_5,1⁰+d_1,1⁰d_5,1⁰}=min{?+0; ?}=?

d_5,2¹=min{d_5,1⁰+d_1,2⁰d_5,2⁰}=min{?+1; ?}=?

d_5,3¹=min{d_5,1⁰+d_1,3⁰d_5,3⁰}=min{?+?; ?}=?

d_5,4¹=min{d_5,1⁰+d_1,4⁰d_5,4⁰}=min{?+?; ?}=?

d_5,5¹=min{d_5,1⁰+d_1,5⁰d_5,5⁰}=min{?+?; 0}=0

d_5,6¹=min{d_5,1⁰+d_1,6⁰d_5,6⁰}=min{?+?; 3}=3

d_6,1¹=min{d_6,1⁰+d_1,1⁰d_6,1⁰}=min{2+0; 2}=2

d_6,2¹=min{d_6,1⁰+d_1,2⁰d_6,2⁰}=min{2+1; ?}=3

d_6,3¹=min{d_6,1⁰+d_1,3⁰d_6,3⁰}=min{2+?; ?}=?

d_6,4¹=min{d_6,1⁰+d_1,4⁰d_6,4⁰}=min{2+?; ?}=?

d_6,5¹=min{d_6,1⁰+d_1,5⁰d_6,5⁰}=min{2+?; ?}=?

d_6,6¹=min{d_6,1⁰+d_1,6⁰d_6,6⁰}=min{2+?; 0}=0

d_i,j²=min{ d_i,2¹+ d_2,j¹; d_i,j¹}.

d_1,1²=min{d_1,2¹+d_2,1¹d_1,1¹}=min{1+?; 0}=0

d_1,2²=min{d_1,2¹+d_2,2¹d_1,2¹}=min{1+0; 1}=1

d_1,3²=min{d_1,2¹+d_2,3¹d_1,3¹}=min{1+2; ?}=3

d_1,4²=min{d_1,2¹+d_2,4¹d_1,4¹}=min{1+?; ?}=?

d_1,5²=min{d_1,2¹+d_2,5¹d_1,5¹}=min{1+?; ?}=?

d_1,6²=min{d_1,2¹+d_2,6¹d_1,6¹}=min{1+?; ?}=?

d_2,1²=min{d_2,2¹+d_2,1¹d_2,1¹}=min{0+?; ?}=?

d_2,2²=min{d_2,2¹+d_2,2¹d_2,2¹}=min{0+0; 0}=0

d_2,3²=min{d_2,2¹+d_2,3¹d_2,3¹}=min{0+2; 2}=2

d_2,4²=min{d_2,2¹+d_2,4¹d_2,4¹}=min{0+?; ?}=?

d_2,5²=min{d_2,2¹+d_2,5¹d_2,5¹}=min{0+?; ?}=?

d_2,6²=min{d_2,2¹+d_2,6¹d_2,6¹}=min{0+?; ?}=?

d_3,1²=min{d_3,2¹+d_2,1¹d_3,1¹}=min{?+?; ?}=?

d_3,2²=min{d_3,2¹+d_2,2¹d_3,2¹}=min{?+0; ?}=?

d_3,3²=min{d_3,2¹+d_2,3¹d_3,3¹}=min{?+2; 0}=0

d_3,4²=min{d_3,2¹+d_2,4¹d_3,4¹}=min{?+?; 2}=2

d_3,5²=min{d_3,2¹+d_2,5¹d_3,5¹}=min{?+?; ?}=?

d_3,6²=min{d_3,2¹+d_2,6¹d_3,6¹}=min{?+?; ?}=?

d_4,1²=min{d_4,2¹+d_2,1¹d_4,1¹}=min{?+?; ?}=?

d_4,2²=min{d_4,2¹+d_2,2¹d_4,2¹}=min{?+0; ?}=?

d_4,3²=min{d_4,2¹+d_2,3¹d_4,3¹}=min{?+2; ?}=?

d_4,4²=min{d_4,2¹+d_2,4¹d_4,4¹}=min{?+?; 0}=0

d_4,5²=min{d_4,2¹+d_2,5¹d_4,5¹}=min{?+?; 2}=2

d_4,6²=min{d_4,2¹+d_2,6¹d_4,6¹}=min{?+?; ?}=?

d_5,1²=min{d_5,2¹+d_2,1¹d_5,1¹}=min{?+?; ?}=?

d_5,2²=min{d_5,2¹+d_2,2¹d_5,2¹}=min{?+0; ?}=?

d_5,3²=min{d_5,2¹+d_2,3¹d_5,3¹}=min{?+2; ?}=?

d_5,4²=min{d_5,2¹+d_2,4¹d_5,4¹}=min{?+?; ?}=?

d_5,5²=min{d_5,2¹+d_2,5¹d_5,5¹}=min{?+?; 0}=0

d_5,6²=min{d_5,2¹+d_2,6¹d_5,6¹}=min{?+?; 3}=3

d_6,1²=min{d_6,2¹+d_2,1¹d_6,1¹}=min{3+?; 2}=2

d_6,2²=min{d_6,2¹+d_2,2¹d_6,2¹}=min{3+0; 3}=3

d_6,3²=min{d_6,2¹+d_2,3¹d_6,3¹}=min{3+2; ?}=5

d_6,4²=min{d_6,2¹+d_2,4¹d_6,4¹}=min{3+?; ?}=?

d_6,5²=min{d_6,2¹+d_2,5¹d_6,5¹}=min{3+?; ?}=?

d_6,6²=min{d_6,2¹+d_2,6¹d_6,6¹}=min{3+?; 0}=0

d_i,j³=min{ d_i,3²+ d_3,j²; d_i,j²}.

d_1,1³=min{d_1,3²+d_3,1²d_1,1²}=min{3+?; 0}=0

d_1,2³=min{d_1,3²+d_3,2²d_1,2²}=min{3+?; 1}=1

d_1,3³=min{d_1,3²+d_3,3²d_1,3²}=min{3+0; 3}=3

d_1,4³=min{d_1,3²+d_3,4²d_1,4²}=min{3+2; ?}=5

d_1,5³=min{d_1,3²+d_3,5²d_1,5²}=min{3+?; ?}=?

d_1,6³=min{d_1,3²+d_3,6²d_1,6²}=min{3+?; ?}=?

d_2,1³=min{d_2,3²+d_3,1²d_2,1²}=min{2+?; ?}=?

d_2,2³=min{d_2,3²+d_3,2²d_2,2²}=min{2+?; 0}=0

d_2,3³=min{d_2,3²+d_3,3²d_2,3²}=min{2+0; 2}=2

d_2,4³=min{d_2,3²+d_3,4²d_2,4²}=min{2+2; ?}=4

d_2,5³=min{d_2,3²+d_3,5²d_2,5²}=min{2+?; ?}=?

d_2,6³=min{d_2,3²+d_3,6²d_2,6²}=min{2+?; ?}=?

d_3,1³=min{d_3,3²+d_3,1²d_3,1²}=min{0+?; ?}=?

d_3,2³=min{d_3,3²+d_3,2²d_3,2²}=min{0+?; ?}=?

d_3,3³=min{d_3,3²+d_3,3²d_3,3²}=min{0+0; 0}=0

d_3,4³=min{d_3,3²+d_3,4²d_3,4²}=min{0+2; 2}=2

d_3,5³=min{d_3,3²+d_3,5²d_3,5²}=min{0+?; ?}=?

d_3,6³=min{d_3,3²+d_3,6²d_3,6²}=min{0+?; ?}=?

d_4,1³=min{d_4,3²+d_3,1²d_4,1²}=min{?+?; ?}=?

d_4,2³=min{d_4,3²+d_3,2²d_4,2²}=min{?+?; ?}=?

d_4,3³=min{d_4,3²+d_3,3²d_4,3²}=min{?+0; ?}=?

d_4,4³=min{d_4,3²+d_3,4²d_4,4²}=min{?+2; 0}=0

d_4,5³=min{d_4,3²+d_3,5²d_4,5²}=min{?+?; 2}=2

d_4,6³=min{d_4,3²+d_3,6²d_4,6²}=min{?+?; ?}=?

d_5,1³=min{d_5,3²+d_3,1²d_5,1²}=min{?+?; ?}=?

d_5,2³=min{d_5,3²+d_3,2²d_5,2²}=min{?+?; ?}=?

d_5,3³=min{d_5,3²+d_3,3²d_5,3²}=min{?+0; ?}=?

d_5,4³=min{d_5,3²+d_3,4²d_5,4²}=min{?+2; ?}=?

d_5,5³=min{d_5,3²+d_3,5²d_5,5²}=min{?+?; 0}=0

d_5,6³=min{d_5,3²+d_3,6²d_5,6²}=min{?+?; 3}=3

d_6,1³=min{d_6,3²+d_3,1²d_6,1²}=min{5+?; 2}=2

d_6,2³=min{d_6,3²+d_3,2²d_6,2²}=min{5+?; 3}=3

d_6,3³=min{d_6,3²+d_3,3²d_6,3²}=min{5+0; 5}=5

d_6,4³=min{d_6,3²+d_3,4²d_6,4²}=min{5+2; ?}=7

d_6,5³=min{d_6,3²+d_3,5²d_6,5²}=min{5+?; ?}=?

d_6,6³=min{d_6,3²+d_3,6²d_6,6²}=min{5+?; 0}=0

d_i,j⁴=min{ d_i,4³+ d_4,j³; d_i,j³}.

d_1,1⁴=min{d_1,4³+d_4,1³d_1,1³}=min{5+?; 0}=0

d_1,2⁴=min{d_1,4³+d_4,2³d_1,2³}=min{5+?; 1}=1

d_1,3⁴=min{d_1,4³+d_4,3³d_1,3³}=min{5+?; 3}=3

d_1,4⁴=min{d_1,4³+d_4,4³d_1,4³}=min{5+0; 5}=5

d_1,5⁴=min{d_1,4³+d_4,5³d_1,5³}=min{5+2; ?}=7

d_1,6⁴=min{d_1,4³+d_4,6³d_1,6³}=min{5+?; ?}=?

d_2,1⁴=min{d_2,4³+d_4,1³d_2,1³}=min{4+?; ?}=?

d_2,2⁴=min{d_2,4³+d_4,2³d_2,2³}=min{4+?; 0}=0

d_2,3⁴=min{d_2,4³+d_4,3³d_2,3³}=min{4+?; 2}=2

d_2,4⁴=min{d_2,4³+d_4,4³d_2,4³}=min{4+0; 4}=4

d_2,5⁴=min{d_2,4³+d_4,5³d_2,5³}=min{4+2; ?}=6

d_2,6⁴=min{d_2,4³+d_4,6³d_2,6³}=min{4+?; ?}=?

d_3,1⁴=min{d_3,4³+d_4,1³d_3,1³}=min{2+?; ?}=?

d_3,2⁴=min{d_3,4³+d_4,2³d_3,2³}=min{2+?; ?}=?

d_3,3⁴=min{d_3,4³+d_4,3³d_3,3³}=min{2+?; 0}=0

d_3,4⁴=min{d_3,4³+d_4,4³d_3,4³}=min{2+0; 2}=2

d_3,5⁴=min{d_3,4³+d_4,5³d_3,5³}=min{2+2; ?}=4

d_3,6⁴=min{d_3,4³+d_4,6³d_3,6³}=min{2+?; ?}=?

d_4,1⁴=min{d_4,4³+d_4,1³d_4,1³}=min{0+?; ?}=?

d_4,2⁴=min{d_4,4³+d_4,2³d_4,2³}=min{0+?; ?}=?

d_4,3⁴=min{d_4,4³+d_4,3³d_4,3³}=min{0+?; ?}=?

d_4,4⁴=min{d_4,4³+d_4,4³d_4,4³}=min{0+0; 0}=0

d_4,5⁴=min{d_4,4³+d_4,5³d_4,5³}=min{0+2; 2}=2

d_4,6⁴=min{d_4,4³+d_4,6³d_4,6³}=min{0+?; ?}=?

d_5,1⁴=min{d_5,4³+d_4,1³d_5,1³}=min{?+?; ?}=?

d_5,2⁴=min{d_5,4³+d_4,2³d_5,2³}=min{?+?; ?}=?

d_5,3⁴=min{d_5,4³+d_4,3³d_5,3³}=min{?+?; ?}=?

d_5,4⁴=min{d_5,4³+d_4,4³d_5,4³}=min{?+0; ?}=?

d_5,5⁴=min{d_5,4³+d_4,5³d_5,5³}=min{?+2; 0}=0

d_5,6⁴=min{d_5,4³+d_4,6³d_5,6³}=min{?+?; 3}=3

d_6,1⁴=min{d_6,4³+d_4,1³d_6,1³}=min{7+?; 2}=2

d_6,2⁴=min{d_6,4³+d_4,2³d_6,2³}=min{7+?; 3}=3

d_6,3⁴=min{d_6,4³+d_4,3³d_6,3³}=min{7+?; 5}=5

d_6,4⁴=min{d_6,4³+d_4,4³d_6,4³}=min{7+0; 7}=7

d_6,5⁴=min{d_6,4³+d_4,5³d_6,5³}=min{7+2; ?}=9

d_6,6⁴=min{d_6,4³+d_4,6³d_6,6³}=min{7+?; 0}=0

d_i,j⁵=min{ d_i,5⁴+ d_5,j⁴; d_i,j⁴}.

d_1,1⁵=min{d_1,5⁴+d_5,1⁴d_1,1⁴}=min{7+?; 0}=0

d_1,2⁵=min{d_1,5⁴+d_5,2⁴d_1,2⁴}=min{7+?; 1}=1

d_1,3⁵=min{d_1,5⁴+d_5,3⁴d_1,3⁴}=min{7+?; 3}=3

d_1,4⁵=min{d_1,5⁴+d_5,4⁴d_1,4⁴}=min{7+?; 5}=5

d_1,5⁵=min{d_1,5⁴+d_5,5⁴d_1,5⁴}=min{7+0; 7}=7

d_1,6⁵=min{d_1,5⁴+d_5,6⁴d_1,6⁴}=min{7+3; ?}=10

d_2,1⁵=min{d_2,5⁴+d_5,1⁴d_2,1⁴}=min{6+?; ?}=?

d_2,2⁵=min{d_2,5⁴+d_5,2⁴d_2,2⁴}=min{6+?; 0}=0

d_2,3⁵=min{d_2,5⁴+d_5,3⁴d_2,3⁴}=min{6+?; 2}=2

d_2,4⁵=min{d_2,5⁴+d_5,4⁴d_2,4⁴}=min{6+?; 4}=4

d_2,5⁵=min{d_2,5⁴+d_5,5⁴d_2,5⁴}=min{6+0; 6}=6

d_2,6⁵=min{d_2,5⁴+d_5,6⁴d_2,6⁴}=min{6+3; ?}=9

d_3,1⁵=min{d_3,5⁴+d_5,1⁴d_3,1⁴}=min{4+?; ?}=?

d_3,2⁵=min{d_3,5⁴+d_5,2⁴d_3,2⁴}=min{4+?; ?}=?

d_3,3⁵=min{d_3,5⁴+d_5,3⁴d_3,3⁴}=min{4+?; 0}=0

d_3,4⁵=min{d_3,5⁴+d_5,4⁴d_3,4⁴}=min{4+?; 2}=2

d_3,5⁵=min{d_3,5⁴+d_5,5⁴d_3,5⁴}=min{4+0; 4}=4

d_3,6⁵=min{d_3,5⁴+d_5,6⁴d_3,6⁴}=min{4+3; ?}=7

d_4,1⁵=min{d_4,5⁴+d_5,1⁴d_4,1⁴}=min{2+?; ?}=?