нахождение кратчайшего пути в графе

  • 15 июня 2017 г.
  • 2370 Слова
 МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ




Федеральное агентство по образованию
Государственное образовательное учреждение
высшего профессионального образования
Иркутский Государственный Университет



Институт математики,
экономики и информатики
Кафедра теории вероятностей и дискретной математики

Комбинаторные алгоритмы расчетаконечных частично неразрешенных графов.

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

Студента группы 02421-ЗБ
010400.62 «Прикладная математика и информатика»
Незамединова Артема И

Научный руководитель:
профессор, доктор физико-математических наук Кузьмин Олег Викторович


ИРКУТСК – 2016
Оглавление
Введение……………………………………………………………………………3
Основные определения…..………………………………………………………..3
Представлениеграфов...………………………………………………..................4
Граф достижимости……...………………………………………………………..6
Алгоритм Флойда-Уоршелла………….………………………………………….7
Постановка задачи………...……………………………………………………….9
Реализация алгоритма…...……………………………………………………….10
Список литературы………………………………………………………………19











Введение
Мы часто сталкиваемся с задачами, в условиях которыхзаданы некоторые объекты и между некоторыми их парами имеются определенные связи. Если объекты изобразить точками (вершинами), а связи - линиями (ребрами), соединяющими соответствующие пары точек, то получится рисунок, называемый графом. Историю теории графов принято исчислять с 1736 г., когда Эйлер исследовал "задачу о кёнигсбергских мостах": построить в графе циклический путь, проходящий поодному разу через каждое ребро. В середине 19-го века Гамильтон заинтересовался задачей построения циклического пути, проходящего по одному разу через каждую вершину графа. К тому же времени относится использование графов для анализа электрических цепей (Кирхгоф) и химических молекул (Кэли). Развитие современной теории графов относится к 30-м годам 20-го столетия. Они нашли многочисленные применения вэлектротехнике, электронике, биологии, экономике, программировании и в других областях. В этой и двух следующих лекциях мы рассмотрим основные понятия теории графов и несколько широко используемых в различных приложениях типовых задач, таких, как представления графов, отношение достижимости и транзитивное замыкание графа, компоненты сильной связности ориентированного графа и его базы, деревья и их обходы,минимальные остовные деревья, поиск в глубину и поиск кратчайших путей. Основное внимание уделено алгоритмическим процедурам, решающим указанные задачи.

1.Основные определения
Определение 1.1. Ориентированный граф - это пара (V, E), где V - конечное множество вершин (узлов, точек) графа, а E - некоторое множество пар вершин. Элементы E называют ребрами (дугами,стрелками, связями). Для ребра e= (u,v) E вершина u называется началом e, а вершина v - концом e, говорят, что ребро e ведет из u в v.
Определение 1.2. Неориентированный граф G=(V, E) - это ориентированный граф, у которого для каждого ребра (u,v) E имеется противоположное ребро (v,u) E. Такая пара (u,v), (v,u)называется неориентированным ребром. Для его задания можно использовать обозначение длямножества концов: {u, v}, но чаще используется указание одной из пар в круглых скобках. Если e= (u,v) E, то вершины u и v называются смежными в G, а ребро e и эти вершины называются инцидентными. Степенью вершины в неориентированном графе называется число смежных с ней вершин. Вершина степени 0 называется изолированной.
Заметим, что в ориентированном графе может быть ребро вида (u,u), называемое петлей, ав неориентированном петель не бывает.
Пример 1.1. На рис.1 приведены примеры ориентированного графа G1=(V1, E1) и не ориентированного графа G2=(V2, E2). Здесь V1={ a,b,c,d}, E1={ (a,b), (a,c), (b,b), (b,d), (d,a)}, V2={ a,b,c,d}, E2={ (a,b), (a,c), (a,d), (b,d)}. В графе G1 ребро (b,b) является петлей, полустепень исхода вершины a равна 2, а полустепень захода...