Алгоритмы на графах. Нахождение кратчайшего пути
Основные понятия и свойства эйлеровых и гамильтоновых цепей и циклов в теории графов. Изучение алгоритма Дейкстры и Флойда для нахождения кратчайших путей в графе. Оценки для числа ребер с компонентами связанности. Головоломка "Кенигзберзьких мостов".
| Рубрика | Математика |
| Вид | курсовая работа |
| Язык | русский |
| Дата добавления | 08.10.2014 |
| Размер файла | 2,4 M |
Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже
Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.
Размещено на http://www.allbest.ru/
Тема
Алгоритмы на графах. Нахождение кратчайшего пути
ВСТУПЛЕНИЕ
Годом возникновения теории графов единодушно считается год 1736, когда Леонард Эйлер опубликовал решение так называемой задачи о Кенигсбергских мостах, а также нашел общий критерий существования Эйлерового цикла в графе.
Получение дальнейших существенных результатов в этой области датируются серединой ХIХ века.
Однако начало проведения активных систематических исследований и становления теории графов как отдельного авторитетного раздела современной математики произошло еще почти 100 лет назад, то есть в середине ХХ века. Именно с этого времени граф становится одной из самых распространенных и популярных математических моделей во многих сферах науки и техники. Картинка в виде набора точек на плоскости и линий, проведенных между некоторыми из них, стала удобной и наглядной форме изображения самых разнообразных объектов, процессов и явлений.
Во многом это связано с возникновением, бурным развитием и распространением электронных вычислительных машин и, как следствие, значительным возрастанием роли задач дискретного характера. Математика от "обслуживания" преимущественно физики переходит к проникновению своих методов в другие сферы человеческой деятельности.
Одним из мощных инструментов такого проникновения является граф. С чисто формальной точки зрения граф можно рассматривать как один из разновидностей алгебраической системы (а именно, как модель), а следовательно, и всю теорию графов как раздел современной алгебры. Действительно, результаты и методы алгебры широко используются в теории графов. Однако за последние полвека активного, интенсивного и экстенсивного развития теория графов выработала свою достаточно специфическую собственную проблематику и методологию.
Одну из задач, которую можно решить с помощью графа является задача нахождения кратчайших расстояний между обьектами.
Нахождение кратчайшего пути - жизненно необходимо и используется практически везде, начиная от нахождения оптимального маршрута между двумя объектами на местности (напр. кратчайший путь от дома до академии), также используется в системах автопилота, используется для нахождения оптимального маршрута при перевозках коммутации информационного пакета Internet и мн. др.
Наиболее распространенные методы поиска кратчайших расстояний - это использование алгоритма Дейкстры (для нахождения кратчайшего пути между двумя вершинами), алгоритма Флойда (для нахождения кратчайших путей между всеми парами вершин) и алгоритма Йена (для нахождения k - кратчайших путей в графе).
Целью курсовой работы было изучить и реализовать на практике алгоритм Дейкстры и Флойда для нахождения кратчайших путей в графе. Задачи работы:
1. Исследовать свойства эйлеровых и гамильтоновых цепей и циклов в теории графов.
2. Изучение алгоритма Дейкстры и Флойда для нахождения кратчайших путей в графе.
3. Приведение примеров решения задач этими методами.
Для графов с конечным множеством вершин и ребер, как правило, проблема существования алгоритма решения задач, в том числе экстремальных, решается положительно. Решение многих задач, связанных с конечными графами, может быть выполнено с помощью полного перебора всех допустимых вариантов. Однако таким способом удается решить задачу только для графов с небольшим числом вершин и ребер. Поэтому существенное значение для графов имеет построение эффективных алгоритмов, находящих точное или приближенное решение.
Раздел I. ВВЕДЕНИЕ В ТЕОРИЮ ГРАФОВ
1.1 Основные понятия и определения
Основные элементы геометрических фигур, применяемых в теории графов приведены на рис.1. и состоят из вершин графа, ребер графа и дуг графа.
Сочетание этих элементов определяет понятия: неориентированный граф, ориентированный граф и смешаныйный граф [6].
Рис.1.1 Основные элементы графа (вершина, ребро, дуга)
Неориентированный граф (неограф) - это граф (рис.1.2), для каждого ребра которого несущественен порядок двух его конечных вершин.
Рис.1.2 Неориентированный граф (вершины и ребра)
Ориентированый граф (орграф) -- это граф, для каждого ребра которого существенен порядок двух его конечных вершин. Орграф представлен на рис.1.3, ребра орграфа иногда называют дугами.
Рис. 1.3 Ориентированный граф
Рис. 1.4 Смешаныйый граф
Смешаныйый граф (рис.1.4) - это граф, который содержит как ориентированные, так и неориентируемые ребра. Каждой из перечисленных видов графа может содержать одно или несколько ребер, в которых оба конца сходятся в одной вершине, такие ребра называются петлями (рис.1.5).
гамильтоновый головоломка цепь число
Рис. 1.5 Смешаный граф с петлями
Рис. 1.6 Общий случай графа
В общем случае множество ребер может состоять из трех непересекающихся подмножеств: подмножества звеньев, подмножества дуг и подмножества петель (рис.1.6).
Рис.1.7 Сущность геометрической конфигурации графа
Наглядно граф можно представлять как геометрическую конфигурацию (см. рис.1.7), которая состоит из точек (вершин графа 1,2,3,4,5,6) и ребер (линий или отрезков № 1 (1-3), № 2 (3-4), № 3 (4-5), № 4 (3-5), № 5 (2-3), № 6 (2-5), № 7 (5-6), № 8 (6 -2), № 9 (2-1), которые соединяют некоторые точки (вершины) по выбранному алгоритму обхода вершин графа) [5].
Дадим формальное математическое определение графа1Ядренко М.И. Дискретная математика : учебное пособие. - К.: Изд. - полиграф.центр „Экспресс”, 2003. - 244 с. Пусть -некоторая конечное множество (множество вершин), - множество всех неупорядоченных пар элементов (ребер или дуг графа) из множества вершин
,
Определение 1.1.
Граф - пара множеств . Множество -это множество вершин, множество -это множество ребер. Если , то мы говорим, что ребро соединяет вершину с вершиной , остальная терминология - ребро и вершины и - инцидентны.
Определение 1.2.
Граф называется полным, если , то есть граф состоит из максимально возможного количества ребер, которые попарно соединяющих точки его вершин (см. рис.1.8). Если множество содержит вершин, то, очевидно, число ребер полного графа равна .
Рис.1.8 Примеры полных графов
Определение 1.3.
Граф называется пустым, если граф не имеет ребра (см.рис.1.9).
Рис.1.9 Пример построения 3-х вершинного графа с разным количеством ребер
Естественно возникает вопрос: сколько существует разных графов с множественным числом вершин , если . Для этого докажем следующую теорему.
Теорема 1.1. Число всех разных графов с вершинами равняется :
Доказательство. Действительно, граф полностью определён, если указано множество , является подмножеством . Множество содержит элементов, поэтому число всех ее подмножеств равно .
Определение 1.4.
Вершины та графа инцидентны, если .
Определение 1.5.
Степенью вершины графа называется число вершин , какие инцидентные вершине ( число отрезков которые выходят из вершины ) - см.рис.1.10.
Рис.1.10 Определение степеней вершин графа по количеству ребер, исходящих из вершин
Определение 1.6.
Если , то вершина называется конечной вершиной графа . Если , то вершины называется изолированной(см. рис. 1.11)
Рис.1.11 Определение конечных и изолированных вершин графа
1.2 Лемма о рукожатии
Формулировка этой леммы простая - „количество рук, которые принимают участие в рукожатии N-пар людей, равняется 2*N”. Лемму можно представить в форме графа, где N вершин соединены ребрами d(хі,xj) рукожатия i и j - вершин (см. рис.1.12), выполнив следующее доказательство.
Рис.1.12. „Лемма о рукожатии” 5 лиц
Пусть граф с множественным числом верщин . Тогда
(1.1)
Доказательство. Заметим, что каждое ребро графа в сумме учитывается дважды (см. рис.1.12), и поэтому справедливо равенство (1.1). Заметим, что сумма степеней всех вершин в графе (или мультиграф без петель) должно быть чётным. Это следует из того, что если взять вершины, вообще не связаны друг с другом, то сумма степеней этих вершин равна нулю. Добавляя любое ребро, связывает две вершины, увеличиваем сумму всех степеней на 2 единицы. Таким образом, сумма всех степеней вершин парная. Из равенства 1.1 следует такое утверждение: число вершин нечетной степени в графе обязательно является четным числом. Теорема доказана.
Определение 1.7.
Матрица смежности - это симметричная матрица, элементы которой равны нулю или единице (диагональные элементы равны нулю) и такая, что сумма чисел в любой строке и любом столбце равна степени соответствующей вершины. Так, для графа, приведенного на рис.1.13, матрица смежности построится в виде:
Рис.1.13. К построению матрицы смежности 3-х вершинного графа
Определение 1.8.
Последовательность ребер , в которой соседние ребра инцидентны одной и той же вершине называются цепью. Цепь называется простой, если все вершины, принадлежащие ей (кроме, возможно, первой и последней), различны; число в этом случае называют длиной цепи.
Если , то цепь называется циклом. Цикл, в котором все вершины различны, называется простым. Примеры простых цепей и простых циклов приведены на рис.1.14:
(1,3), (3,4), (4,6) - простая цепь;
(1,2), (2,5), (5,6) - простая цепь;
(1,3), (3,4), (4,6), (6,5), (5,2) (2,1) - простой цикл.
Рис 1.14. Пример графа с простыми цепями и простыми циклами
Определение 1.9.
Граф является подграфом графа , если . Если , то подграф называется остовним подграфом.
Определение 1.10.
Граф является суммой графов , если
эта сумма называется прямой, если , .
1.3 Оценки для числа ребер с компонентами связанности
Определение 1.11.
Граф называется связанным, если любые вершины и соединенные цепью с началом в и концом в . Из симметрии следует, что в этом случае и вершина соединена с вершиной .
Теорема 1.2.
Каждый граф является прямой суммой связных графов.
Доказательство. На множестве вершин граф определим отношение , если сочетается с . Отношение является отношением еквивалентности. Обозначим через . Тогда и является разбиение на классы эквивалентности. Графы являются связанными графами и
(1.2)
является прямой суммой связных графов. Теорема доказана.
Эти графы называются компонентами связности.
Рассмотрим оценки для числа ребер с компонентами связности.
Теорема 1.3.
Пусть граф, который состоит из вершин, ребер и компонент связанности. Тогда выполняются неравенства
(1.3)
Доказательство. Докажем сначала неравенство . Будем доказывать индукцией по числу ребер. Предположим, что неравенство справедливо для всех графов с числом ребер . Пусть граф из вершин, ребер и компонентами связности. Вычеркнем максимальное возможное число ребер так, чтобы не изменялось число компонент связности. Число ребер в полученном графе обозначим .
Рассмотрим для примера граф, изображенный на рисунке (1.15)
Рис. 1.15. Пример 1 графа для оценки связности
В нем .Вычеркнув два ребра, получим граф . Вычеркнуть дальше какое-либо ребро, не нарушая связаности, уже нельзя (см. рис.1.16)
Рис. 1.16. Пример 1 графа для оценки связности
Вернемся к графу, полученного из . Вычеркнув в нем еще одно ребро, мы получим граф с числом компонент связности на единицу больше. В силу индуктивного предположения, справедливого, ибо имеем, , откуда .
Для доказательства верхней оценки в неравенстве (1.3) заменим каждую компоненту полным графом. Пусть и два полных, полученных из компонент связности и , а и число ребер в этих компонентах. Заменим на полный граф, добавив одну вершину, а заменим на полный граф, отняв одну вершину. Тогда общее число вершины не изменится, а число ребер увеличится на положительную величину
Следовательно, для того, чтобы число ребер в графе было максимально возможным (при фиксированных и ), граф должен состоять из изолированных вершин и полного графа с вершинами. Отсюда и следует неравенство (1.3). Теорема доказана.
Из неравенства (1.3) следует такое следствие.
Следствие. Любой граф из и больше чем ребрами является связным.
Действительно, если граф с вершинами имеет два компонента связности, то максимальное число ребер не превышает .
Найти компоненты сильной связности графа на рис.1.17.
Ответы
Рис.1.17. 7-ми вершинный граф для вычисления компонентов связности Хаггарти Р Дискретная математика для программистов. - М.: «Техносфера», 2003. - 320 с..
1.4 Ориентированы графы, графы, с петлями, графы с параллельными дугами
Дадим определение ориентированных графов, графов с петлями и графов с параллельними дугами.
Неформально, граф выглядит как диаграмма, есть множество точек плоскости (вершин или узлов), соединенных между собой линиями (ребрами). Диаграмма дает представление о связи между элементами (вершинами), но ничего не говорит о метрических свойствах (длина линий, их форма и т.д.).
В зависимости от типа ребер отличаются несколько типов графов. Петля - это ребро, соединяющий вершину саму с собой. В мультиграфе петли не допускаются, но пары вершин могут соединяться несколькими ребрами, которые называются кратными, или параллельными. В псевдографе допускаются петли и кратные ребра.
В обычном графе нет ни петель, ни кратных ребер.С помощью графов подаются структурные зависимости между элементами, соответствующий граф называется ориентированным, или орграфом, а его ориентированные ребра - дугами. Граф, который состоит из ориентированных и неориентированных ребёр одновременно, называется смешанным.
Рис.1.18. Виды ориентированных графов
Определение 1.12.
Пусть множественное число вершин, - множественное число упорядоченных пар элементов с ( будем называть их дугами). Орієнтованим графом будем называть пару множеств , где .
Дуга называется дугой из в (см. рис.1.19).
Рис. 1.19. Ориентированный 3-х вершинный граф
Теорема 1.4. Число всех ориентированных графов с вершинами равняется .
Доказательство. Действительно, число упорядоченных пар элементов из равен , поэтому число всех возможных множеств дуг равна . Теорема доказана.
Определение 1.13.
Пусть -множество вершин. Ориентированным графом с петлями будем называть пару множеств , где (см. рис.1.20).
Рис.1.20. Ориентированый граф с петлями
Теорема 1.5. Число ориентированных графов с петлями, которые имеют вершин, равна .
Доказательство. Действительно, число различных множеств (подмножеств множества ) равно . Теорема доказана.
Если рассматривается одновременно несколько типов графов, то графы описываемых определение (1.1), будем называть простыми графами.
Если в определении (1.1) к множеству неупорядоченных пар присоединить еще множество всех пар вида , то соответствующий граф называется простым графом с петлями.
Из теоремы 1.5 следует вывод для теоремы 1.6 о простых графах.
Теорема 1.6. Число всех простых графов с вершинами и петлями равен
В дальнейшем, мы будем рассматривать простые графы.
РАЗДЕЛ ІІ ЭЙЛЕРОВЫЕ ГРАФЫ
2.1 Эйлерова Головоломка «Кенигзберзьких мостов»
Для решения серьезных математических задач математик Эйлер (Euler) использовал наглядные головоломки. Одна из них положила начало совершенно новой области исследований, выросла впоследствии в самостоятельный раздел математики - теорию графов и топологии. Особенность этой теории - в геометрическом подходе к изучению объектов.
Теория графов - одна из немногих математических дисциплин, дата рождения которой может быть установлена абсолютно точно.
Первая работа по теории графов принадлежит Леонарду Эйлеру. Она появилась в публикациях Санкт-Петербургзськои Академии наук в 1736 году.
Труд Эйлера начиналась с рассмотрения одной головоломки так называемой "задачи о кенигзберзьких мостах".
Город Кенигзберг (ныне Калининград) расположен на берегах реки Прегель и двух островах. Различные части города соединены семью мостами. Еженедельно жители города любили совершать прогулки по городу. Эйлер поставил вопрос: можно совершить прогулку, выйдя из дома и повернувшись к нему, такую, чтобы по каждому мосту пройти ровно один раз.
Сформулируем задачу, как задачу теории графов. Схематическая карта города изображена на рисунке 2.1.
Четыре части города изображены буквами Поскольку нас интересують лишь переходы через мосты, мы можем считать вершинами графа, ребра которого отвечают мостам. Этот граф изображено на рисунку 2.2.
Рис. 2.1. Схема мостов в Кенигзберзи 6. Ядренко М.И. Дискретная математика : учебное пособие. - К.: Изд. - полиграф.центр „Экспресс”, 2003. - 244 с.
Рис. 2.2 Граф «Кенигзберзьких мостов»
Эйлер отметил, что этот граф не имеет единого цикла, с какой бы вершины мы не стали бы обход, мы не можем обойти весь граф и вернуться назад, не проходя каждое ребро дважды. Если бы такой цикл существовал, то из каждой вершины выходило бы столько ребер, сколько в нее входит, иначе говоря степень каждой вершины была бы четным числом. Таким образом, ответ на вопрос Эйлера отрицательный.
Изложив решения задачи о кенигзберзьких мостах, Эйлер в своей работе поставил вопрос: на каких графах можно найти цикл, содержащий все ребра графа, причем каждое ребро встречается в цикле ровно один раз?
Это дало начало системному математическому подходу к построению и изучению свойства графов.
2.2 Основные понятия и определения эйлерових графов
Определение 2.1.
Связанный граф называется эйлеровим графом, если существует замкнутая цепь, которая проходит через каждое ребро.
Такую цепь будем называть эйлеровою цепью, или эйлеровским циклом (см. рис.2.3)
Рис.2.3 Структура вершин и ребер в неориентированном эйлеровом графе * - отмечено точку входа в эйлеровскую цепь
Определение 2.2
Граф называется полуэйлеровим, если существует цепь, которая проходит через каждое его ребро ровно один раз (см. рис.2.4).
Рис.2.4 Структура вершин и ребер в неориентированном полуэйлерованном графе
Рис.2.5 Пример неэйлерового графа
Исследовав структуру неэйлерового графа, приведенном на рис.2.5, рассмотрим необходимые и достаточные условия для того, чтобы граф был эйлеровим. Докажем лемму, которая дальше будет играть существенную роль.
Лемма 2.1
Если степень каждой вершины графа не менее двух, то граф содержит цикл.
Доказательство. Если в графе есть петли или кратные дуги, то утверждение леммы очевидно. Поэтому в дальнейшем будем предполагать, что является простым графом. Пусть х - произвольная вершина графа .
Построим по индукции маршрут
избирая вершину , смежную из , а при избирая вершину , смежную с и отличающуюся от (существование такой вершины следует из условия леммы). Поскольку имеет конечное число вершин, то в конце концов мы придем к вершине , из которой вышли. Получим цикл .
Лемма доказана.
Теорема 2.1
Для связного графа следующие условия эквивалентны:
1. - эйлеровый граф;
2. каждая вершина имеет парную степень;
3. множественное число ребер графа можно разбить на простые циклы.
Доказательство.
Пусть - эйлеровский цикл графа . Будем двигаться по циклу . Прохождение каждой вершины увеличивает степень каждой вершины на 2, и поскольку каждое ребро входит в ровно п раз, то любая вершина имеет парную степень.
Поскольку - связный граф, степень каждой вершины равна по крайней мере 2, ибо в силу леммы 2.1 содержит простой цикл С. Исключим ребра цикла, получим остовной подграф, в котором каждая вершина имеет чётную степень. Если у нет ребер, то (3) доказано. В противном случае применим проведенные выше рассуждения к , получим граф , в котором степени всех вершин являются чётными и так далее. Одновременно с пустым графом , получим разбиение множества ребер на циклов
Пусть множественное число ребер можно разбить на простые циклы. Пусть - один из простых циклов. Если состоит только из этого цикла, то -эйлеровский граф. В противоположном случае существует другой простой цикл, который имеет вершину , общую из . Цепь, которая начинается с и состоит из цикла и следующего за ним цикла , является замкнутой цепью, которая содержит все ребра графа , каждое один раз . Следовательно, - эйлеровский граф.
Из теоремы 2.1 следует следующая теорема.
Теорема 2.2. Связный граф есть эйлеровым тогда и только тогда, когда каждая его вершина имеет чётную степень.
.
Рис.2.6 Пример эйлерового графа в теореме 2.2
Доказательство. Граф изображеный на рисунке 2.6. является эйлеровим, поскольку:
1. Степень вершин А, F, D, C, Q = 4 (чёрные).
2. Степень вершин B, E = 2 (чёрные)
3. Множество ребер этого графа является объединение двух простых циклов и .
Теорема 2.3. Связный граф является полуэйлеровим тогда и только тогда, когда в нем не более двух вершин нечетной степени..
Рис. 2.7 Пример полуэйлерового графа к теореме 2.3
Доказательство. Граф изображен на рисунке 2.7. является полуэйлеровим, поскольку:
1. Степень вершин А, F, C = 4 (чётные);
2. Степень вершин B = 2 (чётные);
3. Степень вершин E, D = 3 (нечетные);
4. Вот один из возможных вариантов обхода . Начальной точкой маршрута является точка , а конечной является точка .
Если граф имеет две вершины с нечетными степенями (см. рис. 2.7), то для любой полуэйлеровой цепи одна из этих вершин будет начальной, а другая конечной. Для доказательства достаточно совместить отрезком вершины с нечетными степенями.
Заметим, что согласно «лемме о рукопожатии» - число вершин нечетной степени является четным.
Попробуем для произвольного графа указать наименьшее число цепей таких, что: никакие два не имеют общих ребер и все они полностью накрывают разом весь граф. Очевидно, если на графе есть такое семейство цепей, то каждая вершина нечетной степени должна быть либо начальной или конечной вершиной какой-то цепи. Общее число вершин с нечетной степенью согласно лемме о рукопожатие является четным, скажем равным .
Таким образом, каждое семейство цепей, накрывающих граф, должно содержать по крайней мере цепей.
Докажем, что существование вершин с нечетным степенью является и достаточным условием существования цепей накрывают граф.
Теорема 2.4. На любом связном графе с вершинами нечётной степени существует семейство цепей, которые в совокупности содержат все ребра графа в точности один раз каждое.
Доказательство. Обозначим вершины с нечётными степенями
Если мы прибавим к нашему графу ребра
то все вершины полученного графа будут чётными и на нем найдется эйлеров цикл . При отбрасывании прибавленных ребер цикл распадется на отдельных цепей, которые содержат все ребра графа.
Граф, изображенный на рисунку 2.8 имеет четыре вершины с нечётными степенями и накрывается двумя цепями и .
Рис.2.8 Граф с нечётной степенью вершин к теореме 2.4
В развлекательной математике вот уже на протяжении нескольких веков рассмотриваются задачи, которые можно сформулировать как задачу поиска определенных маршрутов в графах, в частности, поиска эйлеровых циклов.
Так, граф на рисунке 2.9. называется «саблей Магомета», а эйлеровый цикл необходимо построить по маршруту, не отрывая пера ручки от рисунка за один раз (т.е. росчерком), представленную на рис.2.9.
Рис. 2.9 Эйлеровый цикл в графе - «Сабля Магомета»
Большинство сборников математических задач с развлекательной математики содержат задачи о лабиринтах. Лабиринт состоит из коридоров и их перекрёстков. Следовательно, он может быть изображен графом, в котором ребра соответствуют коридорам, а вершины - перекрёсткам.
Эйлеровим графом должен быть и план осмотра любой выставки, где вдоль помещений выставки нужно расставить указатели обхода таким путем, чтобы каждый экспонат был осмотрен ровно один раз.
Рис.2.10 Применение аппарата эйлерових циклов при решении задач “маршрут выставки»
Предположим, что экспонаты расположены с обеих сторон пути, проходящий по территории выставки. Оказывается, что тогда, каким бы ни был соответствующий граф (был бы он только связанным), можно провести посетителя так, чтобы каждый путь был пройден дважды - по одному разу в каждом направлении (см.рис.2.10).
Теорема 2.5. В связном графе существует ориентированный цикл, который проходит через ребро по одному разу в каждом из двух направлений.
Доказательство. Сформулируем общее правило построения цепи, которое проходит вдоль всех ребер графа в точности по одному разу в каждом направлении. Начнём с произвольной вершины и пройдем вдоль , отметив это ребро маленькой стрелкой в точке , которая показывает выбранное направление. Затем переходим последовательно к другим вершинам. Одну и ту же вершину можно посещать несколько раз. Каждый раз, попав в какую-то вершину, мы будем ставить на соответствующем ребре стрелку указывает направление прибытия. Кроме того, попадая в какую-то вершину впервые, мы отметим входящее ребро, чтобы потом его можно было отличить от других.
Рис.2.11. Граф к теореме 2.5.
Исходя из вершины, мы всегда будем выбирать еще неиспользованное направление: или ребро, по которому мы совсем не проходили, или ребро помечено стрелкой, которая указывает на то, что мы на нём уже были. Договоримся также, что только тогда, когда у нас нет выбора, мы используем для выхода ребро, которое впервые посетили.
Будем продолжать путь до тех пор, когда это вообще возможно. В каждой вершине есть одинаковое число возможностей для входа и для выхода. Поэтому движение может закончиться только в точке . Остается проверить, что во всех вершинах все ребра будут пройдены в обоих направлениях.
Для точки ясно- все ребра, исходящие, будут использованы, поскольку в противном случае мы могли бы двигаться дальше; все ребра, входящие, также будут использованы, потому что их число равно числу ребер, которые исходят. В частности, ребро будет пройдено в обоих направлениях. Но это означает, что все ребра, которые инцидентны , также будут пройдены в обоих направлениях. Прежнее ребро , которое входит в , должно использоваться для выхода только в последнюю очередь. Тоже самое рассуждение можно примененить к следующему ребру и следующей вершине и так далее.
Итак, во всех вершинах, которые будут достигнуты, все ребра окажутся пройденными в обоих направлениях. Поскольку наш граф является связным, это означает, что он будет полностью пройденным.
Заметим, что описанный метод обхода графа может быть использован для решения задач, связанных с поисками маршрутов выхода из лабиринтов.
2.3 Примеры Эйлерових графов
Пример 2.1.Задача о назначении на должность.
Пусть имеется несколько различных вакантных должностей и группа людей, желающих их занять, причем каждый из претендентов достаточно квалифицированный для нескольких, но не для всех имеющихся должностей.
Можно ли каждому из этих людей предоставить одну из тех должностей, которые ему подходят?
Мы можем снова проиллюстрировать эту задачу с помощью некоторого графа, в данном случае выглядит особенно. Как уже сказано, есть определенная группа людей, которую мы обозначим как М и некоторое множество должностей, Р. Строим граф, проводя ребра (м, р), что соединяют каждого человека м с теми должностями р, которые он может занять. На этом графе не будет ребер, соединяющих между собой две вершины м или р, поэтому такой граф имеет вид, приведенный на рис.2.12:
Рис.2.12 Граф для решения задачи о назначении на должность
Всегда найти подходящее место для каждого претендента мы не можем: для этого необходимо, чтобы должностей было не менее претендентов. Но этого недостаточно.
Пусть, например, группа претендентов состоит из двух столяров и человека, который может работать и столяром и сантехником, и для них четыре должности: одно место столяра и три места сантехника. Тогда, очевидно, столяр останется без работы, хотя в данном случае мест более претендентов, и хотя среди претендентов есть люди которые могут работать на двух должностях.
Предположим, что общее количество претендентов - N. Для выполнения задачи должна выполняться следующее условия:
Какую бы группу из k человек, k = 1,2, ..., N, мы не приняли, должно быть по крайней мере k должностей, каждую из которых может занимать хотя бы один из наших претендентов.
Например, если один из людей является столяром, а второй - одновременно и столяром и сантехником и если есть два места сантехника, то наше условие выполняется при k = 2, но не выполняется при k = 1, поэтому указанные люди не могут одновременно устроиться на работу.
Выделенную условие мы кратко назовем условием разнообразия.
Вывод: вышеприведенная задача может использоваться работниками службы занятости для правильного размещения работников на должности.
Пример 2.2 Другие формулировки.
Эта задача, об установлении на графе некоторого соответствия между его вершинами, может иметь и много других формулировок.
Допустимо, например, что у нас есть группа из к ребят и к девушек. Кое-кто из них уже знакомые между собой, и возникает вопрос: в каком случае можно разбить этих молодых людей не пары для танцев так, чтобы все ребята танцевали с знакомыми девушками?
Можно также изменить эту задачу: в маленьком селе есть одинаковое количество взрослых ребят и девушек; не допускается, чтобы парень женился на близкой родственнице - сестре, названной сестре или двоюродной сестре. При каком условии для парня найдется невеста из этого села? Опять мы можем решить эту задачу с помощью двудольного графа - в этом случае его вершины будут соединены ребрами лишь тогда, когда соответствующие люди не являются родственниками.
Еще один вариант этой задачи. В нашей школе есть несколько кружков: C1,C2.,CN. Каждый из этих кружков должен иметь старосту.
Для того, чтобы исключить перегрузку учеников, было поставлено условие, чтобы ни один ученик не был старостой более, чем одного кружка. При каком условии это возможно?
Понятно, что это возможно не всегда; если количество кружков в сравнительно небольшой школе очень большая, то это невозможно.
Чтобы решить эту задачу, мы опять обратимся к двудольному графу.
В этом случае одно множественное число вершин графа будет состоять из N кружков
А другое множественное число вершин P - это множество всех учеников школы. Мы проводим ребро от кружка С1 к ученику р в том случае, если р является членом С1. При этом условие разнообразия превращается в следующее: каждая группа из к кружков (при к = 1, 2..., N) должна включать по меньшей мере к разных учеников. Согласно выше указанному - это то условие при которой кружки могут иметь разных старост.
Если количество кружков слишком большое, не всегда легко довести справедливость условия разнообразия. Поэтому поставим вопрос: Можно ли указать какое-либо простое правило формирования кружков, которое гарантирует возможность вибора для них разных старост?
Это действительно возможно. Для того, чтобы показать, что мы имеем в виду, допустимо, что каждый кружок состоит по крайней мере из пяти учеников. Тогда на соответствующем графе из каждой вершины множественного числа С будет выходить по крайней мере 5 ребер. Для группы из к кружков будет не меньше 5k ребер, которые выходят из соответствующих вершин С к вершинам из Р (дополнение 2, где к = 4).
Рис.2.13 Граф для решения задачи выбора
Теперь, если нам будет нужно, чтобы каждый ученик принимал участие не больше, чем в пяти кружках, это будет значить, что ребра от к кружков должны идти хотя бы к к вершин из р, и, соответственно, условие разнообразия будет выполнено.
РАЗДЕЛ 3 ГАМИЛЬТОНОВЫ ГРАФЫ
3.1 Сущность гамильтоновых графов
Циклы эйлера характеризуются свойством проходить по одному разу через каждое ребро графа, а гамильтонов цикл - через каждую вершину.
Название гамильтонов граф возникла в связи с тем, что в 1859 году известный ирландский математик Уильям Гамильтон выпустил в продажу своеобразную игрушечную головоломку. Ее основой частью был правильный додекаэдр, сделан из дерева [4] (рис.3.1). Это один из так называемых правильных многогранников: его гранями являются 12 правильных пятиугольников, в каждой из его вершин сходится три ребра.
Каждая из вершин гамильтонова додекаэдра была обозначена названием одного из крупных городов земного шара- Брюссель, Кантон, Дели, Лондон и так далее. Задача состоит в нахождении пути вдоль ребер додекаэдра, который проходит через каждый город в точности один раз. Гамильтонов цикл на додекаэдр не покрывает, конечно, всех ребер додекаэдра, потому что в каждой вершине он проходит в точности по двум ребрам.
Рис.3.1 Гамильтонив цикл в додекаэдре
3.2 Основные понятия и определения
Определение 3.1.
Связный граф называется гамильтоновым графом, если существует замкнутая цепь, которая проходит через каждую вершину графа ровно один раз.
Определение 3.2.
Связный граф называется полугамильтоновим, если существует цепь, проходящая через каждую его вершину ровно один раз.
Несмотря на сходство в определениях эйлерових и гамильтоновых графов, согласно теории для этих классов графы сильно отличаются.
К теории гамильтоновых графов относится и задача о бродячем торговце или задача о коммивояжере. В задаче о бродячем торговце речь идет о некотором районе, и торговце, который должен посетить определенное количество городов этого района. Расстояния между городами известны, и надо найти кратчайший путь, который проходит через все города и заканчивается в начальном пункте.
Города можно изображать вершинами некоторого графа, в котором каждой паре вершин приписана расстояние . Речь идет о поиске гамильтонова цикла , для которого сумма является минимальной.
Поскольку рассматривается конечное число вершин, то задача решается (при небольшом количестве вершин) путем простого перебора. Эффективных алгоритмов для решаемой этой задачи не создано, хотя этой проблеме посвящено много исследований.
Установлено различные достаточные условия гамильтоновости графа. Сформулируем две из них.
Теорема 3.1. (О.Оре, 1960). Если для любой пары и несмежных вершин графа с вершинами имеет место неровно
(3.1)
то граф гамильтоновый.
Напомним, что -степень вершины , т.е. число ребер, исходящих из вершины .
Доказательство. Будем доказывать от противного. Предположим, что существует негамильтоновый граф с вершинами, в котором для любой пары несмежных вершин и выполняется условие (3.1). Добавление к графу новых ребер нарушает условие (3.1). Обозначим через максимальный негамильтовый граф, т.е. такой граф, присоединение к которому нового ребра превращает граф на гамильтоновый. Очевидно, не может быть полным графом. Поэтому в существует пара несмежных вершин и . Присоединение к ребра превращает граф на гамильтонов в силу максимальной негамильтоновости . Таким образом, существует гамильтонова цепь. соединяющая и , и проходящая через все вершины (рис. 3.2)
Рис. 3.2 Гамильтонова цепь (1)
Обведём каждую из , какие смежные с , кружочком, и вершину, которая лежит левее, квадратиком так, как изображено на рисунку:
Рис. 3.3 Гамильтонова цепь (2)
из этих вершин окруженны кружочком;
из этих вершин окружены квардатиком;
- не окруженные квадратиком.
Отметим, что в силу условия теоремы
Отсюда следует, что вершина смежная с некоторой вершиной, которая окружена квадратиком . Таким образом, выходит, что граф имеет гамильтоновый цикл, изображенный на рисунку 3.4
Рис.3.4 Гамильтонив цепь(3)
Следовательно пришли к противоречию . Теорема доказана.
Из теоремы 3.1 следует следующая теорема.
Теорема 3.2 (Г.Дирака, 1952) Если для любой вершины графа с вершинами выполняется неравенство , то граф гамильтоновый.
Доказательство. От противного. Пусть - не гамильтоновый граф. Добавим к минимальное количество новых вершин , … ,, соединяя их со всеми вершинами так, чтобы: := + + … + был гамильтоновый.
Пусть , , , … , - гамильтонов цикл в графе , причем , , . Тогда , {,…,}, иначе вершина была бы не нужна.
Далее, если в цикле , , , … ,,, … , есть вершина, смежная с вершиной w, то вершина v 'несмежная с вершиной v, так как иначе можно было бы построить гамильтоновый цикл ,, … ,,, … , без вершины , взяв последовательность вершин , … ,в обратном порядке. Отсюда следует, что число вершин графа , не смежны с , не менее числа вершин, смежных с . Но для любой вершины графа d () ? p/2+n по построению, в том числе d()p/2 + n. Общее число вершин (смежных и не смежных с ) составляет n + p-1. Таким образом, имеем:
n+ p-1 = d(v)+d(V) ? d(w)+d(v) ? p/2+n+p/2+n = 2n+p.
Следовательно, 0 n+1, что противоречит потому, что n > 0. Теорема доказана.
3.3 Примеры гамильтоновых графов
Пример 3.1. Найти все гамильтовые циклы для графа, приведенного на рис.3. 5 [10]
Рис.3.5 Поиск всех гамильтоновых циклов для ориентированного графа
Таблиця 3.1 Результаты поиска гамильтоновых циклов
Пример 3.2. Найти кратчайшие гамильтоновые циклы в задаче «коммивояжёра» для 6-городов, расположенных по графу на рис.3.6 [10]
Рис.3.6 Графы при решении задачи «коммивояжёра»
Результаты расчетов длины «гамильтоновых циклов» в задаче «коммивояжёра» (рис.3.6) приведены в табл.3.2
Таблиця 3.2 Результаты расчетов длины «гамильтоновых циклов»
Пример 3.3. Покажите, что граф, изображенный на рисунку 3.7, не есть гамильтоновым [11].
Рис. 3.7 Пример не гамильтонового графа
Решение.
Предположим, что в связном графе найдется гамильтоновый цикл. Каждая вершина v включается в гамильтонов цикл С выбором двух инцидентных с ней ребер, а значит, степень каждой вершины в гамильтоновом цикле (после удаления лишних ребер) равна 2. Степень вершин данного графа - 2 или 3. Вершины степени 2 входят в цикл вместе с обоими инцидентными с ними ребрами. Итак, ребра аb, ае, cd, cb, hi, hg и ij в том или ином порядке входят в гамильтонов цикл С (см. рис. 3.8).
Ребро bf не может быть частью цикла С, поскольку каждая вершина такого цикла должна иметь степень 2. Значит, ребра fj и fg обязаны входить в цикл С, чтобы включить в него вершину f. Но тогда ребра je и gd никак могут принадлежать циклу С, поскольку в противном случае в нем появятся вершины степени три. Это заставляет нас включить в цикл ребро ed, что приводит нас к противоречию: ребра, которые мы были вынуждены выбрать, образуют два несвязных цикла, а не один, существование которого мы предполагали. Вывод: граф, изображенный на рисунке 3.8, не является гамильтоновым.
Рис.3.8. К доказательству негамильтоновости графа
Раздел 4. Алгоритмы Дейкстры и Флойда. Задачи нахождения кратчайшего пути.
4.1. Математическая модель решения задач методом Дейкстры
Любая задача, требующая нахождения оптимальных маршрутов может быть выполнена с помощью алгоритма Дейкстры. Это касается и сетей, и транспортных потоков, и обработка графов. Очень часто используется не сам алгоритм в чистом виде, а его модификация.
Постановка задачи на максимум выглядит следующим образом:
Пусть дан граф G=(Х, Г), дугам которого приписаны веса (стоимости длины), задаваемые матрицей С = [cij].
Задача о «кратчайшем пути» состоит в нахождении кратчайшего пути от заданной начальной вершины sx до заданной конечной вершины tx, при условии, что такой путь существует tR(s) (здесь R(s) - множество, достижимое из вершины s) и все циклы в графе имеют неотрицательный суммарный вес. Так как если в графе будет присутствовать цикл с отрицательным суммарным весом и хi - некоторая его вершина, то, двигаясь от s к хi, обходя этот цикл достаточно большое число раз и попадая, наконец в t, получится путь со сколь угодно малым (> ?) весом. Таким образом, в этом случае кратчайшего пути не существует. Так что неориентированные дуги (ребра) графа G не могут иметь отрицательные веса.
4.2 Описание метода решения задач
Процедура находит путь минимального веса в графе G = (V, E) заданном весовой матрицей W у которой элемент равен весу ребра соединяющего i-ую и j-ую вершины. При этом предполагается, что все элементы wij неотрицательны. Путь ищется из вершины номер u1 к вершине номер u2 . Процедура использует алгоритм Дейкстры. Для представления веса, равного бесконечности, используется число GM, передаваемое в алгоритм. Это число можно задавать в зависимости от конкретной задачи.
Алгоритм по которому происходит поиск заключается в следующем:
1. Всем вершинам приписывается вес - вещественное число, d(i) := GM для всех вершин кроме вершины с номером u1, а d(u1 ) := 0.
2. Всем вершинам приписывается метка m(i) := 0.
3. Вершина u1 объявляется текущей: t := u1.
4. Для всех вершин у которых m(i) равно 0, пересчитываем вес по формуле
d(i) := min{d(i), d(t)+W[t,i]}.
5. Среди вершин для которых выполнено m(i) = 0 ищем ту для которой d(i) минимальна, если минимум не найден, т.е. вес всех не "помеченных" вершин равен бесконечности (GM), то путь не существует, покидаем алгоритм.
6. Иначе найденную вершину c минимальным весом полагаем текущей и помечаем (m(t) := 1).
7. Если t = u2 , то найден путь веса d(t), покидаем алгоритм и переходим на следующий шаг.
4.3. Функциональные тесты
Задача 1
Дан граф смежности для нахождения минимального пути от вершины 1 до всех остальных (рис. 4.1.)
Рис. 4.1 Граф к задаче 1
Представим граф, в виде матрица длин дуг
Таблица 1. Представление матрицы к задаче 1
|
X1 |
X2 |
X3 |
X4 |
X5 |
X6 |
||
|
x1 |
? |
10 |
18 |
7 |
? |
? |
|
|
x2 |
10 |
? |
16 |
9 |
9 |
? |
|
|
x3 |
? |
16 |
? |
? |
15 |
? |
|
|
x4 |
7 |
9 |
? |
? |
? |
12 |
|
|
x5 |
? |
? |
? |
? |
? |
23 |
|
|
x6 |
? |
? |
15 |
? |
23 |
? |
Стартовая вершина, от которой строится дерево кратчайших путей - вершина 1.
Задаем стартовые условия: d(1)=0, d(x)=? Окрашиваем вершину 1, y=1.
Находим ближайшую вершину к окрашенной нами, используя формулу:
d(x)=min{d(x);d(y)+a(y,x)}
Минимальную длину имеет путь от вершины 1 до вершины 4 d(4)=7. Включаем вершину №4 в текущее ориентированное дерево, а так же дугу, ведущую в эту вершину. Согласно выражению это дуга (1,4)
Мы получили ориентированное дерево кратчайших путей начинающихся в вершине №1 для исходного графа.
d(1)=1 Длина маршрута L=0;
d(2)=1-4-2 Длина маршрута L=16;
d(3)=1-4-2-5-6-3 Длина маршрута L=63;
d(4)=1-4 Длина маршрута L=7;
d(5)=1-4-2-5 Длина маршрута L=25;
d(6)=1-4-2-5-6 Длина маршрута L=48.
Задача 2
Дан граф смежности для нахождения минимального пути от вершины 1 до всех остальных
Рис. 4.2. Граф к задаче 2
Представим граф, в виде матрица длин дуг
Таблица 2 Представление графа
|
X1 |
X2 |
X3 |
X4 |
X5 |
X6 |
||
|
x1 |
0 |
5 |
3 |
2 |
? |
? |
|
|
x2 |
? |
0 |
1 |
? |
? |
? |
|
|
x3 |
? |
? |
0 |
? |
? |
1 |
|
|
x4 |
? |
? |
? |
0 |
? |
3 |
|
|
x5 |
? |
2 |
? |
? |
0 |
? |
|
|
x6 |
? |
? |
? |
? |
1 |
0 |
Стартовая вершина, от которой строится дерево кратчайших путей - вершина 1.
Задаем стартовые условия: d(1)=0, d(x)=?
Окрашиваем вершину 1, y=1.
Находим ближайшую вершину к окрашенной нами, используя формулу:
d(x)=min{d(x); d(y)+a(y,x)}
d(2)=min{8}
d(3)=min{9}
d(4)=min{2}
d(5)=min{6}
d(6)=min{5}
Минимальную длину имеет путь от вершины 1 до вершины 4 d(4)=2. Включаем вершину №4 в текущее ориентированное дерево, а так же дугу, ведущую в эту вершину. Согласно выражению это дуга (1,4)
Мы получили ориентированное дерево кратчайших путей начинающихся в вершине №1 для исходного графа.
d(1)=1 Длина маршрута L=0;
d(2)=1-4-6-5-2 Длина маршрута L=8;
d(3)=1-4-6-5-2-3 Длина маршрута L=9;
d(4)=1-4 Длина маршрута L=2;
d(5)=1-4-6-5 Длина маршрута L=6;
d(6)=1-4-6 Длина маршрута L=5.
4.3 Построение математической модели алгоритмом Флойда
Цель алгоритма Флойда - определение кратчайшего пути между вершинами взвешенного графа. Этот алгоритм более общий по сравнению с алгоритмом Дейкстры, так как он находит кратчайшие пути между любыми двумя узлами сети. В этом алгоритме сеть представлена в виде квадратной матрицы с n строками и n столбцами. Элемент (i, j) равен расстоянию dij от узла i к узлу j, которое имеет конечное значение, если существует дуга (i, j), и равен бесконечности в противном случае.
Постановка задачи: пусть дан непустой взвешенный граф G=(V, E) с произвольными весами ребер (дуг). Требуется найти длины кратчайших путей между всеми парами вершин графа
Применительно к прикладной задаче целью разработки приложения является - определение наиболее эффективного маршрута пересылки сообщений между любыми двумя районами. Причем алгоритм может решать подобные задачи для разных критериев, например, критерием может быть - поиск наиболее дешевого пути (каждой дуге ставится в соответствие денежный эквивалент, который необходимо затратить при использовании этой дуги); или поиск наиболее быстрого пути (в этом случае каждой дуге присваивается время, которое будет потрачено при ее использовании); можно таким же образом найти самый надежный путь (каждой дуге ставится в соответствие коэффициент риска передачи сообщения по этой дуге/пути).
Подобных задач может возникнуть очень много, а цель этих задач одинакова - нахождение кратчайшего пути из одного состояния в другое (относительно графа - нахождение минимального расстояния между 2-мя вершинами).
4.4 Описание математического метода алгоритма Флойда
Основная идея метода Флойда состоит в следующем: пусть есть три узла i, j и k и заданы расстояния между ними (рис. 4.3.).
Если выполняется неравенство dij + djk < dik, то целесообразно заменить путь i -> k путем i -> j -> k.
Такая замена (условно называемая треугольным оператором) выполняется систематически в процессе выполнения алгоритма Флойда.
Рис. 4.3 Треугольный оператор
Алгоритм Флойда требует выполнения следующих действий (рис. 4.4.).
Шаг 0. Определяем начальную матрицу расстояния D0 и матрицу последовательности узлов S0. Диагональные элементы обеих матриц помечаются знаком "-", показывающим, что эти элементы в вычислениях не участвуют. Полагаем k :=1.
Рис.4.4 Первоначальная ситуация
Основной шаг k. Задаем строку k и столбец k как ведущую строку и ведущий столбец. Рассматриваем возможность применения треугольного оператора ко всем элементам dij матрицы Dk-1. Если выполняется неравенство dik + dkj < dij, (i <> k, j <> k, i <> j), тогда выполняем следующие действия:
· создаем матрицу Dk путем замены в матрице Dk-1 элемента dij на сумму dik + dkj,
· создаем матрицу Sk путем замены в матрице Sk-1 элемента sij на k. Полагаем k = k + 1 и повторяем шаг k.
Поясним действия, выполняемые на k-м шаге алгоритма, представив матрицу Dk-1 так, как она показана на рисунке 4. 5. На этом рисунке строка k и столбец k являются ведущими. Строка i - любая строка с номером от 1 до k - 1, а строка p - произвольная строка с номером от k + 1 до n. Аналогично столбец j представляет любой столбец с номером от 1 до k - 1, столбец q - произвольный столбец с номером от k + 1 до n. Треугольный оператор выполняется следующим образом. Если сумма элементов ведущих строки и столбца (показанных в квадратах) меньше элементов, находящихся в пересечении столбца и строки (показанных в кружках), соответствующих рассматриваемым ведущим элементам, то расстояние (элемент в кружке) заменяется на сумму расстояний, представленных ведущими элементами:
Схема 4.5 Иллюстрация алгоритма Флойда
После реализации n шагов алгоритма определение по матрицам Dn и Sn кратчайшего пути между узлами i и j выполняется по следующим правилам.
Расстояние между узлами i и j равно элементу dij в матрице Dn.
Промежуточные узлы пути от узла i к узлу j определяем по матрице Sn. Пусть sij = k, тогда имеем путь i -> k -> j. Если далее sik = k и skj = j, тогда считаем, что весь путь определен, так как найдены все промежуточные узлы. В противном случае повторяем описанную процедуру для путей от узла i к узлу k и от узла k к узлу j (рис. 4.6).
Рис 4.6 Треугольный оператор
4.5 Расчет математической модели
Составим для поставленной задачи изображенной на рисунке 4.4. матрицу смежности, получим матрицу D0 (рис. 4.7.)
Рис 4.7 Первоначальная матрица
Применим к ней алгоритм Флойда, получим следующую матрицу кратчайших путей и матрицу маршрутов (рис 4.8.) :
Рис. 4.8 Результат работы алгоритма
Таким образом, например, кратчайшее расстояние из первой вершины во вторую равно 4. Из шестой в седьмую равно 9, причем проходим через 5-ю вершину, из пятой в первую расстояние равно 10, и проходим через 7-ю вершину (рис. 4.9.)
Рис. 4.9 Результат работы алгоритма показан на графе
Путь из 6 в 9 равен 2+7=9.Путь из 1 в 2 равен 4
Перенумеруем узлы по другому (рис.4.10)
Рис.4.10. Вторая задача
Составим для поставленной задачи изображенной на рисунке 4.4. матрицу смежности, получим матрицу D0 рис.4.11.
Рис.4.11 Первоначальная матрица к второй задаче
Применим к ней алгоритм Флойда, получим следующую матрицу кратчайших путей и матрицу маршрутов (рис.4.12.):
Рис 4.12 Результат работы алгоритма
Таким образом, например, кратчайшее расстояние из первой вершины в третью равно 7, путь проходит через 2-ю вершину. Из шестой в четвертую равно 7, причем проходим через 7-ю вершину (рис.4.13.).
Рис.4.13. Результат работы алгоритма показан на графе
Перенумеруем узлы по другому (рис.4.14.).
Рис.4.14 Третья задача
Составим для поставленной задачи изображенной на рисунке 13 матрицу смежности, получим матрицу D0 (рис.4.15.).
Рис.4.15 Первоначальная матрица к третьей задаче
Применим к ней алгоритм Флойда, получим следующую матрицу кратчайших путей и матрицу маршрутов (рис.4.16.):
Рис.4.16 Результат работы алгоритма
Таким образом, например, кратчайшее расстояние из третьей вершины в шестую равно 10, путь проходит через 5-ю вершину. Из седьмой во вторую равно 7, причем проходим через 1-ю вершину.
ВЫВОДЫ
С развитием компьютерной техники и компьютеризацией производства и других отраслей человеческой деятельности, непрерывно растет роль дискретной математики как теоретической основы для построения алгоритмов и написания компьютерных программ.
Теория графов - очень важен раздел дискретной математики, особенностью которого является геометрический подход к изучению объектов. Диаграммы графа подобно геометрическим рисунків позволяют получить наглядное представление к разному роду задач.
На сегодняшнее время графы очень удобно использовать для решения задач разных видов. Теория графов является очень актуальной, ее широко применяют не только в самой математике, но и в других естественных науках, в частности, в физике, химии, географии, биологии, картографии, и во многих других науках. Да, например, для построения структурных формул химических элементов, для составления наиболее выгодных транспортных маршрутов, при моделировании сложных технологических процессов, в программировании, в электротехнике - для конструирования печатных схем, а также при изученные последовательного и параллельного соединения проводников.
Граф является математической моделью самых разнообразных объектов, явлений и процессов, которые исследуются и используются в науке, технике и на практике. Графы позволяют строить математическую модель связей между заданными элементами.
Например, в виде графа могут быть изображены электрические, транспортные, информационные и компьютерные и другие сети, карты автомобильных, железнодорожных, воздушных путей, лабиринты, модели кристаллов, структуры молекул химических веществ, и так далее
Подобные документы
Основные понятия теории графов. Содержание метода Дейкстры нахождения расстояния от источника до всех остальных вершин в графе с неотрицательными весами дуг. Программная реализация исследуемого алгоритма. Построение матриц смежности и инцидентности.
курсовая работа [228,5 K], добавлен 30.01.2012Эйлеровы цепи и циклы, теоремы. Алгоритм построения эйлерова цикла. Обоснование алгоритма. Нахождение кратчайших путей в графе. Алгоритм Форда отыскания кратчайшего пути. Задача отыскания кратчайших расстояний между всеми парами вершин. Алгоритм Флойда.
реферат [108,4 K], добавлен 01.12.2008Поиск кратчайших путей для пар вершин взвешенного ориентированного графа с весовой функцией. Включение матрицы в алгоритм Флойда, содержащую вершину, полученную при нахождении кратчайшего пути. Матрица, которая содержит длины путей из вершины в вершину.
презентация [36,1 K], добавлен 16.09.2013Понятия теории графов, их связность и задача о кратчайшей цепи. Программная реализация метода Дейкстры, его сравнение с методом простого перебора. Описание логики программного модуля. Примеры работы программы нахождения кратчайшей цепи в связном графе.
курсовая работа [330,2 K], добавлен 25.11.2011Способы решения задач дискретной математики. Расчет кратчайшего пути между парами всех вершин в ориентированном и неориентированном графах с помощью использования алгоритма Флойда. Анализ задачи и методов ее решения. Разработка и характеристика программы.
курсовая работа [951,4 K], добавлен 22.01.2014Основные понятия теории графов. Маршруты и связность. Задача о кёнигсбергских мостах. Эйлеровы графы. Оценка числа эйлеровых графов. Алгоритм построения эйлеровой цепи в данном эйлеровом графе. Практическое применение теории графов в науке.
курсовая работа [1006,8 K], добавлен 23.12.2007Теория графов как математический аппарат для решения задач. Характеристика теории графов. Критерий существования обхода всех ребер графа без повторений, полученный Л. Эйлером при решении задачи о Кенигсбергских мостах. Алгоритм на графах Дейкстры.
контрольная работа [466,3 K], добавлен 11.03.2011Понятие и содержание теории графов. Правила построения сетевых графиков и требования к ним. Сетевое планирование в условиях неопределенности. Теория принятия решений, используемые алгоритмы и основные принципы. Пример применения алгоритма Дейкстры.
курсовая работа [1,0 M], добавлен 26.09.2013Основные понятия теории графов. Расстояния в графах, диаметр, радиус и центр. Применение графов в практической деятельности человека. Определение кратчайших маршрутов. Эйлеровы и гамильтоновы графы. Элементы теории графов на факультативных занятиях.
дипломная работа [145,5 K], добавлен 19.07.2011Описание заданного графа множествами вершин V и дуг X, списками смежности, матрицей инцидентности и смежности. Матрица весов соответствующего неориентированного графа. Определение дерева кратчайших путей по алгоритму Дейкстры. Поиск деревьев на графе.
курсовая работа [625,4 K], добавлен 30.09.2014
