Нахождение кротчайшего остова ориентированного графа, используя алгоритмы Краскала и Прима

Министерство образования и науки Российской Федерации

1. Воронежский Институт Высоких Технологий

1. Факультет Информационных технологий

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

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

По теме: «Нахождение кротчайшего остова ориентированного графа, используя алгоритмы Краскала и Прима”

Выполнил:

Студент группы ИН-044 Рязанцев А.В.

Руководитель:

доцент Белецкая С.Ю.

Воронеж 2007

Содержание

Введение

1. Исторические сведения

Правило Эйлера

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

Свойства связных графов

Эквивалентные определения дерева.

1. Ориентированный граф

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

Начальные понятия

Алгоритм нахождения кратчайшего пути

1. 5. Алгоритмы Краскала и Прима

Алгоритм Краскала

Алгоритм Прима

Задача Прима–Краскала.

6. Листинг программы

Заключение

Литература

Введение

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

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

1. Исторические сведения

ТЕОРИЯ ГРАФОВ - это область дискретной матема­тики, особенностью которой является геометрический подход к изучению объектов. Теория графов находится сейчас в самом расцвете. Обычно её относят к топологии (потому что во многих случаях рассматриваются лишь топологические свойства графов), однако она пересекается со многими разделами теории множеств, комбинаторной математики, алгебры, геометрии, теории матриц, теории игр, математической логики и многих других математических дисциплин. Основной объект теории графов-граф и его обобщения.

Первые задачи теории графов были связаны с решением математических развлекательных задач и головоломок (задача о Кенигсбергских мостах, задача о расстановке ферзей на шахматной доске, задачи о перевозках, задача о кругосветном путешествии и другие). Одним из первых результатов в теории графов явился критерий существования обхода всех ребер графа без повторе­ний, полученный Л. Эйлером при реше­нии задачи о Кенигсбергских мостах. Вот пересказ отрывка из письма Эйлера от 13 марта 1736 году: ” Мне была предложена задача об острове, расположенном в городе Кенигсберге и окруженном рекой, через которую перекинуто 7 мостов. Спрашивается, может ли кто-нибудь непрерывно обойти их, проходя только однажды через каждый мост. И тут же мне было сообщено, что никто еще до сих пор не смог это проделать, но никто и не доказал, что это невозможно. Вопрос этот, хотя и банальный, показался мне, однако, достойным внимания тем, что для его решения недостаточны ни геометрия, ни алгебра, ни комбинаторное искусство. После долгих размышлений я нашел лёгкое правило, основанное на вполне убедительном доказательстве, с помощью которого можно во всех задачах такого рода тотчас же определить, может ли быть совершен такой обход через какое угодно число и как угодно расположенных мостов или не может“. Кенигсбергские мосты схематически можно изобразить так.

Правило Эйлера

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

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

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

Существует еще один вид задач, связанных с путешествиями вдоль графов. Речь идёт о задачах, в которых требуется отыскать путь, проходящий через все вершины, причем не более одного раза через каждую. Цикл, проходящий через каждую вершину один и только один раз, носит название гамильтоновой линии( в честь Уильяма Роуэна Гамильтона, знаменитого ирландского математика прошлого века, который первым начал изучать такие линии). К сожалению, пока еще не найден общий критерий, с помощью которого можно было бы решить, является ли данный граф гамильтоновым, и если да, то найти на нём все гамильтоновы линии.

Другая старая топологическая задача, которая особенно долго не поддавалась решению и будоражила умы любителей головоломок, известна как “задача об электро -, газо - и водоснабжении”. В 1917 году Генри Э.Дьюдени дал ей такую формулировку. В каждый из трёх домов, изображенных на рисунке, необходимо провести газ, свет и воду.

Свет вода газ

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

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

1. 2. Основные термины и теоремы теории графов

1. Граф - Пара объектов G = ( X , Г ) ,где Х - конечное множество ,а Г –конечное подмножество прямого произведения Х*Х . При этом Х называется множеством вершин , а Г - множеством дуг графа G .

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

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

4. Дуга- ребро ориентированного графа.

5. Граф называется вырожденным, если у него нет рёбер.

6. Вершина Х называется инцидентной ребру G , если ребро соединяет эту вершину с какой-либо другой вершиной.

7. Подграфом G(V₁, E₁) графа G(V, E) называется граф с множеством вершин V₁ ?V и множеством ребер (дуг) E₁? E, - такими, что каждое ребро (дуга) из E₁ инцидентно (инцидентна) только вершинам из V₁ . Иначе говоря, подграф содержит некоторые вершины исходного графа и некоторые рёбра (только те, оба конца которых входят в подграф).

8. Подграфом, порождённым множеством вершин U называется подграф, множество вершин которого – U, содержащий те и только те рёбра, оба конца которых входят в U.

9. Подграф называется остовным подграфом, если множество его вершин совпадает с множеством вершин самого графа.

10. Вершины называются смежными , если существует ребро , их соединяющее.

11. Два ребра G₁ и G₂ называются смежными, если существует вершина, инцидентная одновременно G₁ и G₂.

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

13. Пустым называется граф без рёбер. Полным называется граф, в котором каждые две вершины смежные.

14. Конечная последовательность необязательно различных рёбер E₁,E₂,...E_n называется маршрутом длины n, если существует последовательность V₁, V₂, ... V_n необязательно различных вершин, таких, что E_i = (V_i-1,V_i ).

15. Если совпадают, то маршрут замкнутый.

16. Маршрут, в котором все рёбра попарно различны, называется цепью.

17. Замкнутый маршрут, все рёбра которого различны, называется циклом. Если все вершины цепи или цикла различны, то такая цепь или цикл называются простыми.

18. Цикл, в котором все вершины, кроме первой и последней, попарно различны, называется простым циклом.

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

20. Степень вершины - число ребер, которым инцидентна вершина V, обозначается D(V).

Эквивалентные определения дерева

1. Связный граф называется деревом, если он не имеет циклов.

2. Содержит N-1 ребро и не имеет циклов.

3. Связный и содержит N-1 ребро.

4. Связный и удаление одного любого ребра делает его несвязным.

5. Любая пара вершин соединяется единственной цепью.

6. Не имеет циклов и добавление одного ребра между любыми двумя верши-

нами приводит к появлению одного и только одного цикла.

3. Ориентированный граф

Определение. Ориентированным графом (сокращенно: орграфом) называется множество точек и соединяющих эти точки ориентированных непрерывных линий.

Точки будем называть вершинами, ориентированные линии – дугами графа. Орграф часто будем обозначать парой (V,E), где V – множество вершин, Е – множество дуг графа. При изображении орграфа ориентацию будем указывать стрелкой на дуге (см. рис. 6.1). Если дуга е, соединяющая вершины x и y, ориентирована от х и y, то будем говорить, что х – начало дуги и х – конец дуги е, или что дуга е выходит из х и заходит в y. Такую дугу е будем иногда называть (x,y)–дугой. Например, дуга е₂ выходит из вершины а и заходит в вершину b (см. рис. 3.1).

Вершины x и y будем называть смежными, если существует (x,y)–дуга или (y,x)–дуга. Если дуга е соединяет вершины x и y, то будем говорить, что е инцидентна вершинам x и y.



Рис. 3.1

Дугу, выходящую из некоторой вершины и заходящую в ту же вершину, будем называть петлей, а дуги, выходящие из одной и той же вершины и заходящие в одну и ту же вершину, будем называть кратными. Так, дуги е₅ и е₆ являются кратными, а дуга е₁ – петлей (см. рис. 3.1). Вершину, из которой не выходит и в которую не заходит ни одна дуга, будем называть изолированной. Например, i – изолированная вершина.

Обобщим понятие степени вершины для орграфов.

Определение. Пусть G – орграф. Полустепенью исхода r^–(v) вершины v графа G называется число дуг, выходящих из v, полустепенью захода r⁺(v) – число дуг, заходящих в v.

Например, для графа, изображенного на рис. 6.1, имеем, что r^–(b)=2, r⁺(b)=1, r^–(c)=0, r⁺(c)=3.

Следующее утверждение достаточно очевидно.

Предложение. Сумма полустепеней исхода всех вершин графа равна суммe полустепеней захода всех вершин.

Определение. Вершина v ориентированного графа называется источником, если r⁺(v)?0 и r^–(v)?0, и стоком, если r⁺(v)?0 и r^–(v)=0.

Так для графа на рис. 3.1 вершина с является стоком, а источника этот граф не имеет. Ясно, что орграф может иметь несколько источников и стоков.

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

Как и в неориентированном случае, мы будем задавать орграф, изображая на рисунке соответствующую геометрическую фигуру. Однако для решения задач, связанных с графами на компьютере, такое задание графа является неудобным. Для задания графа в этих случаях используются фактически те же способы, что и в неориентированном случае. Пусть n – число вершин, m – число ребер орграфа G=(V,E), V={v₁,v₂,…,v_n} и E={e₁,e₂,…e_m}. Матрица инцидентности графа G – это матрица A=(a_ij) размера n?m такая, что



Матрица смежности графа G – это квадратная матрица B=(b_ij) порядка n такая, что b_ij есть число дуг с началом в вершине v_i и концов в v_j. На рис. 3.2 и 3.3 приведены примеры задания графов соответственно матрицами инцидентности и смежности.



Рис. 3.2



Рис. 3.3

Для задания орграфов используются также списки смежностей и список дуг. В первом случае для каждой вершины v формируется список вершин, в которые заходят дуги, выходящие из v. В списке дуг каждая дуга е представляется парой вершин (x,y), где х – начало, y – конец дуги е.

Введем понятие изоморфизма для орграфов.

Определение. Орграфы G₁=(V₁,E₁) и G₂=(V₂,E₂) изоморфны, если существует биекция j: V₁®V₂ такая, что для любых вершин x,y?V₁ число (x,y)–дуг из Е₁ равно числу (j(x), j(y)) – дуг из Е₂.

Графы G₁ и G₂, изображенные на рис. 3.4, изоморфны; биекция ? определяется нумерацией вершин.

Нам понадобится также понятие подграфа.

Определение. Орграф G?=(V?,E?) называется подграфом орграфа G=(V,E), если V??V, E??E и если дуга e инцидентна вершинам x и y и e?E?, x,y?V?. Если V?=V, то подграф G? называется суграфом.

Примеров приводить не будем, поскольку понятие подграфа в ориентированном случае полностью аналогично такому же понятию в неориентированном случае.



Рис. 3.4

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

(x,y)?R? в графе G существует (x,y)–дуга.

В этом случае граф G мы будем иногда называть графом бинарного отношения R. Например, графу G, изображенному на рис. 3.5,



Рис. 3.5

соответствует отношение R={(a,a), (a,b), (a,c), (a,d), (c,d), (d,a)}, заданное на множестве V={a,b,c,d}.

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

Начальные понятия

Будем рассматривать ориентированные графы G = <V, E>, дугам которых приписаны веса. Это означает, что каждой дуге <u, v> ?E поставлено в соответствие некоторое вещественное число a (u, v), называемое весом данной дуги.

Полагаем, кроме того, a (u, v) = ? , если u -a v.

Нас будет интересовать нахождение кратчайшего пути между фиксированными вершинами s, t ?V. Длину такого кратчайшего пути мы будем обозначать d (s, t) и называть расстоянием от s до t (расстояние, определенное таким образом, может быть отрицательным). Если не существует ни одного пути из s в t, то полагаем d (s, t) = ? . Если каждый контур нашего графа имеет положительную длину, то кратчайший путь будет всегда элементарным путем, т.е. в последовательности v₁,..., v_p не будет повторов.

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

Алгоритм нахождения кратчайшего пути

Данные: Расстояния D[v] от фиксированной вершины s до всех остальных вершин v ? V, фиксированная вершина t, матрица весов ребер, A[u, v], u, v ?V.

Результаты: СТЕК содержит последовательность вершин, определяющую кратчайший путь из s в t.

Пусть <V, E> -ориентированный граф, | V|  = n, | E|  = m. Если выбор вершины u происходит в результате просмотра всех вершин, то сложность нашего алгоритма - O(n²). Если мы просматриваем только список ПРЕДШ[v], содержащий все вершины u, такие что u (r) v, то в этом случае сложность будет O(m).

Отметим, что в случае положительных весов ребер задача о кратчайшем пути в неориентированном графе легко сводится к аналогичной задаче для некоторого ориентированного графа. С этой целью достаточно заменить каждое ребро {u, v}двумя дугами ? u, v? и ?v, u? , каждая с таким же весом, что и {u, v}. Однако в случае неположительных весов это приводит к возникновению контуров с неположительной длиной.

Далее будем всегда предполагать, что G = < V, E> является ориентированным графом, |V|  = n, |E|  = m. В целях упрощения изложения и избежания вырожденных случаев при оценке сложности алгоритмов будем исключать ситуации, при которых «большинство» вершин изолированные.

Будем также предполагать, что веса дуг запоминаются в массиве A[u, v], u, v? V (A[u, v] содержит вес a (u, v)).

5. Алгоритмы Краскала и Прима.

Алгоритм Краскала

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

Существует алгоритм Краскала, позволяющий найти остов минимального веса в любом взвешенном графе. Дадим его описание по шагам.

Шаг 1. Найдем в данном графе ребро минимального веса (если таких несколько, фиксируем любое). Обозначим его через ; кроме того, фиксируем подграф в данном графе , состоящий из концов ребра  и самого этого ребра. Обозначим этот подграф через .

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

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

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

Общий шаг - шаг № k. Фиксируем в графе  ребро – обозначим его через , - имеющее минимальный вес среди ребер, не входящих в  и не составляющих цикла с ребрами из . Подграф, состоящий из ребер , , ,..., , обозначим через .

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

Алгоритм Прима

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

Более формально алгоритм записывается следующим образом. Введем массив used[N], первоначально заполненный нулями. Пусть наш каркас первоначально пуст.

1. Пометим первую вершину как использованную: used[0] = 1.

2. Найдем ребро (i, j), соединяющее использованную вершину (used[i] == 1) с неиспользованной (used[j] == 0). Если таких ребер несколько, выберем ребро с минимальной стоимостью. Если таких ребер нет, закончим выполнение алгоритма.

3. Добавим это ребро к каркасу.

4. Пометим used[j] = 1.

5. Перейдем к шагу 2.

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

Задача Прима–Краскала

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

Или в терминах теории графов:

Дан граф с n вершинами; длины ребер заданы матрицей. Найти остовное дерево минимальной длины.

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

Удивительно, но в задаче Прима–Краскала, которая не кажется особенно простой, жадный алгоритм дает точное оптимальное решение.

Как известно (это легко доказать по индукции), дерево с n вершинами имеет n-1 ребер. Оказывается, каждое ребро нужно выбирать жадно (лишь бы не возникали циклы). То есть n-1 раз выбирать самое короткое ребро из еще не выбранное ребро при условии, что оно не образует цикла с уже выбранными.

А как следить, чтобы новое ребро не образовывало цикла со старыми? Сделать это просто. До построения дерева окрасим каждую вершину i в отличный от других цвет i. При выборе очередного ребра, например (i, j), где i и j имеют разные цвета, вершина j и все, окрашенные в ее цвет (т.е. ранее с ней соединенные) перекрашиваются в цвет i. Таким образом, выбор вершин разного цвета обеспечивает отсутствие циклов. После выбора n-1 ребер все вершины получают один цвет.

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

Если к дереву добавить ребро, то в дереве появится цикл, содержащий это ребро.

Действительно, пусть добавлено ребро (u, v) – “добавлено” означает, что ребро – новое, что раньше его в дереве не было. Поскольку дерево является связанным графом, то существует цепь C(u, …, v) из нескольких ребер, соединяющая вершины u и v. Добавление ребра (u, v) замыкает цепь, превращая ее в цикл.

Теорема. Алгоритм Прима–Краскала получает минимальное остовное дерево.

Доказательство. Результатом работы алгоритма является набор из n-1 ребер. Они не образуют цикла, ибо на каждом из n-1 шагов соединялись вершины разного цвета, т.е. ранее не связанные. Этот граф связный, потому что после проведения 1-го ребра осталось n-1 разных цветов, …, после проведения (n-1)-го ребра остался один цвет, т.е. одна компонента связности. Итак, полученный набор ребер образует связный граф без циклов, содержащий n-1 ребер и n вершин. Следовательно, граф есть остовное дерево. Осталось доказать, что оно имеет минимальную длину. Пусть {, , …, } ребра остовного дерева в том порядке как их выбирал алгоритм, т.е. . Предположим для простоты доказательства, что все ребра сети имеют разную длину, т.е.

<<#img src="data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAAAkAAAAPCAIAAAC5qnJaAAAAbElEQVR4nGP5//8/Aw7AgksCKnfv3j1/f//Lly9jkVNSUuLg4CDdTArc8unTpzt37qioqGBxy82bNymw79SpU+fOnQsLCxMSEkKXMzMzu3XrFg8PDxZ9M2bM4OTk/PbtGxsbG7pcRkYGsW4BAPBQJHx69CZcAAAAAElFTkSuQmCC"><…< (1)

Если полученное дерево не минимально, то существует другое дерево, заданное набором из n-1 ребер {, , …, }, такое что сумма длин меньше суммы длин . С точностью до обозначений

<<#img src="data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAAAsAAAAPCAIAAAC9X6JnAAAAoElEQVR4nGP5//8/A17Agl8aRcWNGzciIyPPnz+PU4WGhgYHBwd2M9avX3/p0iV9ff0fP35gV9HR0XH8+HEmJqbOzk7sKoByjIyM+FyanZ1dWFhoamr65cuXZ8+eSUlJoauIAQMgIzo6GrsZ+AF2FadOnTp37lxYWJiQkBB2FWZmZrdu3eLh4cFpxowZMzg5Ob99+8bGxoZdRUZGBgkuBQAvYTMEuaOVMAAAAABJRU5ErkJggg=="><…< (2)

Может быть =, = и т.д., но так как деревья разные, то в последовательностях (1) и (2) найдется место, где ребра отличаются. Пусть самое левое такое место ­– k, так что . Поскольку выбиралось по алгоритму самым малым из не образующих цикла с ребрами , , …, , то <<#img src="data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAAAsAAAAPCAIAAAC9X6JnAAAAmElEQVR4nGP5//8/A17Agl8aRcWNGzciIyPPnz+PU4WGhgYHBwd2M9avX3/p0iV9ff0fP35gV9HR0XH8+HEmJqbOzk7sKoByjIyM+FyanZ1dWFhoamr65cuXZ8+eSUlJoauIAQMgIzo6GrsZ+AF2FRMmTCgoKMCnAujwNWvW+Pv7s7KyYlfx9u1bYNj8/PkTp4qmpiYSXAoAjTQz0xuva9sAAAAASUVORK5CYII=">. Теперь добавим к дереву (2) ребро ; в нем появится цикл, содержащий ребро и, может быть, какие-то (или все) ребра , , …, , но они сами не образуют цикла, поэтому в цикле будет обязательно ребро d из набора , …, , причем d>. Выбросим из полученного графа с одним циклом ребро d; мы снова получим дерево, но оно будет на d- короче минимального, что невозможно. Полученное противоречие доказывает теорему для сети со всеми разными ребрами.

6. Листинг программы

Описание программы:

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

Для реализации алгоритма понадобятся:

n – количество вершин в графе

a[i, j] – матрица смежности

Программа:

Program Algoritm_Prima;

uses Crt;

const

nm = 20;

var

a: array[1..nm, 1..nm] of Integer;

n, i, j: Integer;

procedure Tree;

var

SM, SP: set of 1..nm;

min, i, j, l, k, t: Integer;

begin

min := maxint;

SM:=[1..N];SP:=[];

for i:=1 to N-1 do

for j:=i+1 to N do

if (A[i,j]0) then

begin

min:=A[i,j];

l:=i;

t:=j;

end;

SP:=[l,t];

SM:=SM-[l,t];

Write('(', l, ', ', t, ') ');

while SM<>[] do

begin

min:=maxint;

l:=0;t:=0;

for i:=1 to N do

if Not(i in SP) then

for j:=1 to N do

if (j in SP) and (A[i,j]0) then

begin

min:=A[j,k];

l:=i;

t:=j;

end;

SP:=SP+[l];

SM:=SM-[l];

Write('(', l, ', ', t, ')');

end;

end;

begin

TextBackground(Blue);

ClrScr;

TextColor(red);

WriteLn('Programma nachozdeniy krotchaichego ostova orientirovannogo grafa po algoritmu');

WriteLn('Prima':40);

Delay(60000);

Delay(60000);

WriteLn;

TextColor(white);

Write(' Vvedite colichestvo verchin v grafe: ');

TextColor(10);

ReadLn(n);

TextColor(white);

WriteLn(' Vvedite matricu cmeznosti opicivaemoy graf:');

WriteLn;

for i := 1 to n do

begin

TextColor(10);

Write(' ');

for j := 1 to n do

Read(a[i, j]);

end;

TextColor(White);

WriteLn;

TextColor(14);

WriteLn(' Loding, plees wait...':50);

Delay(60000);

Delay(60000);

Delay(60000);

Delay(60000);

Delay(60000);

Delay(60000);

TextColor(blink+14);

WriteLn;

WriteLn;

WriteLn('Press Enter':45);

ReadLn;

ReadLn;

WriteLn;

TextColor(white);

Write(' Korkas naimenichego vesa = ');

TextColor(10);

Write(' ');

Tree;

TextColor(blink+14);

WriteLn;

WriteLn;

Delay(60000);

Delay(60000);

Delay(60000);

Delay(60000);

Delay(60000);

Delay(60000);

Delay(60000);

WriteLn;

WriteLn;

WriteLn(' Press Enter for Exit':50);

ReadLn;

end.

Результат работы:

Заключение

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

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

Литература

1. Белов Теория Графов, Москва, «Наука»,1968.

2. Кузнецов О.П., Адельсон-Вельский Г.М. Дискретная математика для инженера. – М.: Энергоатомиздат, 1988.

3. Лекции по теории графов. / Емеличев В.А., Мельников О.И. и др. М.: Наука, 1990.

4. Смольяков Э.Р. Введение в теоpию гpафов. М.: МГТУ, 1992, 32 с.

5. Романовский И.В. Алгоpитмы pешения экстpемальных задач. - М.: Hаука, 1977, 352 с.

6. Hефедов В.H., Осипова В.А. Куpс дискpетной математики. - М.: МАИ, 1992, 264 с.

7. http://www.uvk2.artn.ru/projects/Lopyrev_Anton/algol.html

8. http://www.caravan.ru/~alexch/graphs/graph_alg.htm