Задача Прима-Краскала о телефонной линии

ФЕДЕРАЛЬНОЕ АГЕНТСТВО  ПО ОБРАЗОВАНИЮ

ФГОУ СПО «Беловский политехнический колледж»

 

 

 

 

 

 

 

Задача Прима-Краскала о телефонной линии

Курсовой проект

КР 230105.00 ММ.00.00 ПЗ

 

 

 

Студент гр.ВТ06-3з 

Е.А.Бирючкова

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

С.В.Белугина

Нормоконтролер

С.В.Белугина

 

 

 

 

 

 

 

Белово 2009

 

СОДЕРЖАНИЕ

 

Введение

1 ТЕОРЕТИЧЕСКАЯ ЧАСТЬ

1.1 Понятие графы

1.2 Представление графов в ЭВМ

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

2 ПРАКТИЧЕСКАЯ ЧАСТЬ

2.1 Решение задачи − теста

2.2 Ручной расчёт задачи

2.3 Машинная реализация метода

2.4 Блок- схема

2.5 Обоснование выбора языка программирования

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

2.7 Анализ полученных результатов

Заключение

Список литературы

 

ВВЕДЕНИЕ

 

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

Математическое программирование − область математики, разрабатывающая теорию и численные методы решения многомерных задач.

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

Впервые понятие «граф» ввёл в 1936 году венгерский математик  Денни Кёниг. Но первая работа по теории графов принадлежала перу великого Леонарда Эйлера и была написана ещё в 1736 году. С помощью графов изображаются схемы различных дорог, линии воздушных сообщений, газопроводов, теплотрасс, электросетей, а также микросхемы, дискретные многошаговые процессы, системы различных бинарных отношений, химические структурные формулы и другие диаграммы и схемы. Применяются графы для решения задач химии, экономики, электротехники и автоматики. Также они широко используются в информатике и строительстве. Без графов сложно анализировать классификации в различных науках.

Теория графов — раздел дискретной математики, особенностью которого является геометрический подход к изучению объектов. Первые задачи теории графов были связаны с решением математических развлекательных задач и головоломок (задача о Кёнингсбергских мостах, задача о расстановке ферзей на шахматной доске, задачи о перевозках, задача о кругосветном путешествии и др.). В общем смысле граф (сеть) G = (V,E) состоит из конечного, непустого множества m вершин ( m≤1) и конечного множества n неупорядоченных пар элементов [u, v] (n≥0), называемых рёбрами графа G. В строгом определении графом называется такая пара множеств G = {R,V}, где V есть подмножество любого счётного множества, а R — подмножество V×V. Теория графов находит применение, например, в геоинформационных системах (ГИС). Существующие или вновь проектируемые дома, сооружения, кварталы и т. п. рассматриваются как вершины, а соединяющие их дороги, инженерные сети, линии электропередач и т. п. — как рёбра. Применение различных вычислений, производимых на таком графе, позволяет, например, найти кратчайший объездной путь или ближайший продуктовый магазин, спланировать оптимальный маршрут.

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

Цель курсовой работы – подобрать  теоретический материал по рассматриваемой теме, решить задачу о жадном «алгоритме», посвященной нахождению минимальной суммы длин между его вершинами методом Прима- Краскала ручным и машинным способом.

 

1 ТЕОРЕТИЧЕСКАЯ ЧАСТЬ

 

1.1 Понятие графа

 

Граф - совокупность точек и линий, в которой каждая линия соединяет две точки. Точки называются вершинами, или узлами, графа, а линии - ребрами графа. Если ребро соединят две вершины, то говорят, что оно им инцидентно; вершины, соединенные ребром называются смежными. Обычно граф изображают диаграммой; вершины- точками (или кружками), рёбра- линиями.

 u₁  u₂

 

 

 u₄   u₃

 Рисунок 1− Диаграмма графа G

 

Если элементами множества Е  являются упорядоченные пары, то граф называется ориентированным (или орграфом). В этом случае элементы множества  V называются узлами, а элементы множества Е- дугами.

  (1)

Если элементом множества Е  может быть пара одинаковых (не различных) элементов V, то такой элемент множества Е называется петлёй, а граф – графом с петлями (или псевдографом).

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

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

Если задана функция F: V→М и/или F: Е→∩М, то множество М называется множеством пометок, а граф называется помеченным (или нагруженным). В качестве множества пометок обычно используются буквы или целые числа.

Существуют изоморфные графы. Понятие изоморфизма (схожести по форме) для графов имеет наглядное  толкование. Представим рёбра графов эластичными нитями, связывающими узлы- вершины. Тогда изоморфизм можно представить как перемещение узлов и растяжение нитей. G₁=(X₁,U₁,Ф₁) и G₂=(X₂,U₂,Ф₂)- изоморфны (G₁ G₂), если:

  ₁→X₂ и : U_1→U₂ (2)

 

 Рисунок 2 − Изоморфные графы

 

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

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

Подграф G₁=(V₁,X₁) называется остовным подграфом, если множество его вершин совпадает с множеством вершин самого графа G=(V,X).

Граф, который может быть изображен на плоскости так, что  его рёбра не будут пересекаться-это  планарный (плоский) граф.

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

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

Мост- ребро,удаление которого из сети делает сеть несвязной.

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

Взвешенная сеть- это такая сеть, рёбрам или дугам которой поставлены в соответствие действительные числа  или величины, принимающие Г₁=(X₁,U₁,Ф₁) и Г₂=(X₂,U₂,Ф₂)- изоморфны (Г₁ Г₂), если:

 

  ₁→X₂ и : U_1→U₂ (3)

 

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

 

 

Рисунок 3 − Взвешенная сеть

 

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

 

 

Рисунок 4 – Дерево

 

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

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

 

 

Рисунок 5 − Неориентированный взвешенный граф

 

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

 

1.2 Представление графов  в ЭВМ

 

Графы являются весьма удобным средством описания и оптимизации алгоритмов вычисления. Известны различные способы представления графов в памяти компьютера, которые различаются объёмом занимаемой памяти и скоростью выполнения операций над графами. Представление выбирается исходя из потребностей конкретной задачи. Рассмотрим три способа:

1. Матрица смежности. Представление графа с помощью квадратной булевой матрицы М: array [1..n,1..n] of 0..1, отражающей смежность вершин, называется матрицей смежности, где 1 – если вершины смежный, 0 – если вершины не смежные.
2. Матрица инцидентности. Представление матрицы с помощью прямоугольной матрицы, отражающей инцидентность вершины и ребра. Для не ориентированного графа:

 1 – если вершина инцидентна ребру, 0 – если не инцидентна. Для ориентированного графа:

1 – если вершина инцидентна ребру, и является его концом,

0 – если вершина и ребро  не инцидентны,

-1 – если вершина инцидентна ребру и является её началом.

3. Матрица весов. Квадратная матрица, содержащая вес ребра между двумя вершинами.

 

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

 

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

Алгоритм строит кратчайший остов:

Вход: граф G(V, Е) , заданный матрицей длин рёбер С.

Выход: кратчайший остов  Т.

 Т:=V

while в Т больше одного элемента do

взять любое поддерево  из Т

найти к нему ближайшее

соединить эти деревья  в Т

end while

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

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

Вход: список Е рёбер  графа G с длинами.

Выход: множество Т  рёбер кратчайшего остова.

Т:=

Упорядочить Е в порядке  возрастания длин

k:= 1 { номер рассматриваемого ребра }

for I from 1 to p – 1 do

while добавление ребра Е (k) образует цикл в Т do

k:=k+1 {пропустить ребро }

end while

Т:= Т Ụ { Е [k] } {добавить это ребро в SST }

end for

Пояснение SST-Shortest Sceleton Tree- стандартное обозначение для кратчайшего остова.

Заметим, что множество  подмножеств множества рёбер, не содержащих циклов, образует матроид. Действительно, если множество рёбер  не содержит цикла, то любое подмножество также не содержит цикла. Пусть теперь Е^´ Е- произвольное множество рёбер, а G´- правильный подграф графа G, определяемый этими рёбрами. Очевидно, что любое максимальное не содержащее циклов подмножество множества Е´ является объединением остовов компонент связности G´и по теореме об основных свойствах деревьев содержит p(G´)- k(G´) элементов. Таким образом, по теореме множество ациклических подмножеств рёбер образует матроид. Далее, рассматриваемый алгоритм, как жадный алгоритм, находит кратчайшее ациклическое подмножество множества рёбер. По построению оно содержит p-1 элемент, а значит, является искомым остовом.

 

2 ПРАКТИЧЕСКАЯ ЧАСТЬ

 

2.1 Решение задачи-теста

 

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

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

 

Рисунок 6 − Карта плоской страны

 

2.2 Ручной расчет задачи

 

Пусть

С_ij - это стоимость телефонной линии от i до j города.

Q_j – минимальная стоимость телефонной линии от 1 города до i, при поиске кротчайшего пути из 1 до 8 города.

Используем формулу Q_j = min(Q_j+ С_ij) для поиска стоимости прокладки телефонного кабеля.

Стоимость телефонной линии от 1 города равна Q₁=0,

Q₂ = Q₁+ С₁₂ = 0+6 = 6

Q₇ = Q₂+ С₂₇ = 6+3 = 9

Q₈ = Q₇+ С₇₈ = 9+16 =25 нашли кратчайший путь, найдем кратчайший путь до оставшихся городов Q₃= Q₂+ С₂₃ = 6+9 =15, Q₄ = Q₃+ С₃₄ = 15+12= 27, Q₆ = Q₂+ С₂₆ = 6+5 =11, Q₅ = Q₁+ С₁₅ = 0+2=2.