Федеральное агентство по образованию

Воронежский государственный технический университет

Естественно-гуманитарный факультет

Кафедра систем автоматизированного проектирования и информационных систем

 
 
 
 
 
 
 
 
 
КУРСОВАЯ РАБОТА

по дисциплине      Дискретная математика

Тема Нахождение минимальной стоимости в транспортной сети_______ 

Выполнил студент    ИС-091      Юшин Н.О.

                                Группа      Подпись, дата                 Инициалы, фамилия

Руководитель      д.т.н. профессор Белецкая С.Ю.

         Подпись, дата           Инициалы, фамилия

Защищена     Оценка

                      Дата 
 
 
 
 

Воронеж-2010

 

СОДЕРЖАНИЕ 

Введение

1 Теоретическая  часть

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

2 Транспортная задача

      2.1Основные  понятия.

      2.2Алгоритм поиска в ширину

      2.3 Увеличение потока (или Алгоритм  Форда-Фалкерсона)

      2.4 Алгоритм Беллмана-Форда 

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

Приложение.Текст  задачи

 

      Введение

       В первой части курсовой работы рассматривается  вопрос о связности графов. Понятия вершинной и реберной связности широко применяются в прикладных задачах теории графов. Рассмотрим одну математическую модель, возникающую, в частности, при проектировании и анализе сетей ЭВМ. Имеется сеть, состоящая из центров хранения и переработки информации. Некоторые пары центров соединены каналами. Обмен информацией между любыми двумя центрами осуществляется либо непосредственно по соединяющему их каналу, если он есть, либо через другие каналы и центры. Сеть считается исправной, если каждая пара центров в состоянии обмениваться информацией. Такой сети естественно сопоставить граф: вершины – центры, ребра – каналы сети. Тогда исправной сети будет соответствовать связный граф. Важным понятием является надежность (живучесть) сети, под которой обычно подразумевают способность сети функционировать при выходе из строя одного или нескольких центров или (и) каналов. Ясно, что менее надежной следует считать ту сеть, исправность которой нарушается при повреждении меньшего количества элементов. Оказывается, надежность сети можно измерять на основе вводимых ниже определений.

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

 

1. Теоретическая часть

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

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

       Основы  теории графов как математической науки  заложил в 1736 г. Леонард Эйлер, рассматривая задачу о кенигсбергских мостах. Сегодня  эта задача стала классической. 

 

  

1. Карта кенигсбергских мостов.

2. Граф  Эйлера к задаче о  кенигсбергских мостах.

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

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

       Прежде  чем обосновать невозможность требуемого маршрута, Эйлер рассмотрел и другую, более сложную карту (рис. 3). 

3. Карта кенигсбергских мостов из альбома Эйлера.

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

       1) из любой вершины графа должен  существовать путь по его ребрам  в любую другую вершину (графы,  удовлетворяющие этому требованию, называются связными);

       2) из каждой вершины должно выходить  чётное количество рёбер.

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

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

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

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

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

4. Виды  графов.

       Граф 1, изображенный на рисунке 4, содержит четыре вершины {1, 2, 3, 4} и семь ребер {а, b, с, d, e, f, g}. Ребро а инцидентно вершинам 2 и 4; ребро g инцидентно только вершине 3 и является петлей, вершины 2 и 3 смежны, а вершины 1 и 4 не смежны; ребра d и f - кратные; степень вершины 2 равна 4.

       Ребро, соединяющее две  вершины и имеющее  направление от одной  вершины к другой, называется направленным или ориентированным и изображается стрелкой. Граф, в котором все ребра - ориентированные, называется ориентированным графом (орграфом); ребра орграфа называют дугами. Кратные дуги – дуги, имеющие не только общие вершины, но и совпадающие по направлению. Граф 2, изображенный на рис.4, - ориентированный; дуги d и f – кратные.

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

       Примером  символического представления графов является представление списками вершин и ребер. Вот как рассмотренный  выше граф 1 задается списком вершин {1, 2, 3, 4} и списком ребер, в котором для каждого ребра указана пара инцидентных ему вершин:

а: (1, 2)

b: (1, 3)

с: (2, 3)

d: (2, 4)

е: (3, 4)

f: (2, 4)

g: (4, 4)

       Такой же список ребер имеет и граф 3 (рис. 4); поэтому графы 1 и 3 равны, хотя их рисунки заметно отличаются.

       Для неориентированного ребра порядок, в котором указаны соединяемые  им вершины, не важен. Для ориентированного ребра это важно: первой указывается  вершина, из которой выходит ребро. Например, орграф 2 получен из графа 1 введением ориентации ребер; однако, для того чтобы приведенный выше список ребер описывал граф 2, в нем нужно изменить описание ребер c и d - с: (3,  2) и d: (4, 2). 

5. Изоморфные  графы.

       Свойства  графа не меняются с изменением положения  его вершин, не зависят от того, какими именно линиями вершины соединены. Два графа, изображенные на рисунке 5, в этом смысле одинаковы: у них  одинаковое число вершин, и если две вершины одного графа соединены  ребром, то вершины второго графа, имеющие те же номера, также соединены  ребром. Это замечание более строго формулируется так:  графы, между вершинами которых можно установить взаимно однозначное соответствие, при котором вершинам, соединённым ребром соответствуют вершины, также соединённые ребром называются изоморфными (от греч «изос» — «равный» и «морфе» — «вид», «форма»).

       Плоские графы («укладывающиеся» на плоскость) обладают многими интересными свойствами. Так, Эйлер обнаружил простую  связь между количеством вершин (В), количеством рёбер (Р) и количеством частей (Г), на которые граф разделяет плоскость:

       В – Р + Г = 2.

       Граф, который можно  изобразить на плоскости  так, чтобы его  ребра не пересекались, называется плоским. Но такие графы встречаются не всегда.

       Если  в неориентированном графе с  n вершинами нет кратных ребер и петель, то максимальное число ребер в нем равно n(n-1)/2.  Это соответствует случаю, когда между любыми двумя вершинами есть ребро; такой граф называется полным. Полный граф «не укладывается» на плоскость без пересечения рёбер. Пример такого графа приведен на рис. 6. Это граф с пятью вершинами, каждые две из которых соединены ребром.  

6. Пример  полного графа.

       Граф, не имеющий ребер (состоящий  из изолированных  вершин) называется пустым.

       Маршрут - это последовательность ребер в неориентированном графе, в котором конец каждого ребра совпадает с началом следующего ребра. Число ребер маршрута называется его длиной. Цикл - это замкнутый маршрут, т. е. маршрут, в котором начальная вершина совпадает с конечной. В графе 1 (см. рис. 4) а, с, e - маршрут; a, f, e, b - цикл. В орграфе ориентированный маршрут, т. е. маршрут, в котором все дуги проходятся по их ориентации, называется путем, а путь, являющийся циклом, называется ориентированным циклом. В графе 2 (рис. 4) а, d, e - путь, f, e, с - ориентированный цикл. Иногда в литературе используется и другая терминология: например, замкнутый маршрут именуют контуром, а циклом называют только такой контур, который не пересекает сам себя, т. е. не содержит повторяющихся вершин.

       Неориентированный граф называется связным, если между любыми двумя его вершинами есть маршрут. Орграф считается связным, если он связан без учета ориентации его дуг. Связный граф с n вершинами содержит не менее n - 1 ребер. Орграф называется сильно связным, если из любой вершины в любую другую существует путь. Граф 2 (рис. 4) -  связный, но не сильно связный, так как в вершину 1 нет путей из других вершин. 

7. Пример  неориентированного дерева.

       Дерево - это неориентированный связный граф без циклов. Дерево с n вершинами всегда имеет (n - 1) ребер. Между любыми двумя вершинами дерева существует единственный маршрут (если бы его не было, нарушилась бы связность, а если бы было два маршрута с одинаковыми концами, то получился бы цикл). Поэтому дерево иногда определяется как минимальный связный граф, т. е. граф, в котором удаление любого ребра нарушает связность. Вершина дерева, которая соединена ребром только с одной вершиной, называется висячей вершиной или листом. В любом дереве, содержащем более одной вершины, имеется не менее двух листьев. На рис. 7 граф представляет пример неориентированного дерева. Его листьями являются вершины 1, 6 и 7.