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

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

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

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

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

КР 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.

Минимальная прокладка телефонная линия с 1 до 8 города составит 6+3+16=25 по пути (1-2-7-8). Полная стоимость всей телефонной линии 6+3+16+2+5+9+12=53.

Получили схему прокладки телефонной линии (рис. 7).

Рисунок 7 - Схема прокладки телефонной линии

Вывод: получили минимальную стоимость прокладки телефонной линии с 1 до 8 город и составляет 6+3+16=25.

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

Входные данные:

nU ? число ребер в графе

X - список вершин графа

We - веса ребер согласно их сортировки

Выходные данные:

nU ? число ребер в графе

nX ? число вершин в графе

Х ? список вершин графа

(u1,u2) ? сортированный список ребер графа

We ? веса ребер согласно их сортировки

(uo1,uo2) ? ребра оставного дерева

Woe ? веса ребер оставного дерева

Вес ? сумма весов ребер оставного дерева.

2.4 Блок-схема

Рисунок 7 - Блок-схема алгоритма решения задачи

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

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

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

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

Program Hungry_Ostov; {Оставное дерево.Жадный алгоритм.}

uses CRT,DOS;

Const

nVertex=50;{Максимальное количество вершин}

nRib=1000;{Максимальное количество ребер}

Type

TypeVertex=array[1..nVertex] of Integer;

TypeRib=array[1..nRib] of Integer;

Var f:Text;{Текстовый файл}

nX:Integer;{Количество вершин в графе}

nU:Integer;{Количество ребер в графе}

Mark:TypeVertex; {Метки принадлежности вершин}

x:TypeVertex;{Список вершин графа}

U:TypeRib;{Реберный список графа }

nUo:Integer;{Количество ребер в оставном дереве}

Uo:TypeRib;{Ребра оставного дерева}

We:TypeRib;{Веса ребер графа}

Wt:LongInt;{Вес минимального оставного дерева}

Procedure Init;{Переназначение меток вершин}

Var

i,j,m:Integer;

begin

for i:=1 to 2*nU do Uo[i]:=1;

for i:=1 to 2*nU do

for j:=i+1 to 2*nU do if Uo[j]=1 then

if U[j]=U[i] then Uo[j]:=0;

nX:=0;

for i:=1 to 2*nU do

if Uo[i]=1 then begin

nX:=nX+1;

X[nX]:=U[i];

end;

for i:=1 to 2*nU do {Новые метки}

for m:=1 to nX do

if U[i]=X[m] then begin U[i]:=m; break; end;

end;

Procedure Sort; {Сортировка списка ребер по их весам}

Var

i,j,k:Integer;

w:Integer;

begin

for i:=1 to nU do

for j:=1 to nU-i do

if We[j]>We[j+1] then begin

w:=We[j]; We[j]:=We[j+1]; We[j+1]:=w;

w:=U[2*j-1]; U[2*j-1]:=U[2*(j+1)-1];

U[2*(j+1)-1]:=w;

w:=U[2*j]; U[2*j]:=U[2*(j+1)]; U[2*(j+1)]:=w;

end;

end;

Procedure Ostov;{Строим минимальное оставное дерево}

Var

i,x,y,z:Integer;

sU:Integer;

begin

for i:=1 to nX do Mark[i]:=i;

Sort;{Сортировка ребер по весу}

nUo:=0;{Пустое множество Uo}

sU:=1;{Начальное ребро в сортированном U}

while nUo<nX-1 do begin

x:=U[2*sU];{Выбор нового ребра из списка}

y:=U[2*sU-1];

if Mark[x]<>Mark[y] then begin

nUo:=nUo+1;

Uo[nUo]:=sU;{Добавить ребро в оставное дерево}

z:=Mark[y];{Слияние Ux и Uy}

for i:=1 to nX do if Mark[i]=z then

Mark[i]:=Mark[x];

end;

sU:=sU+1{Удалить ребра (x,y) из списка U }

end;

end;

Var{Main}

i,j:Integer;

Begin{Main}

Assign(f,C:hvvod.txt);

Reset(f);{Файл открыт для чтения}

Read(f,nU);{Количество ребер в реберном списке графа }

for i:=1 to nU do Read(f,U[2*i-1]);{Первые вершины ребер}

for i:=1 to nU do Read(f,U[2*i]);{Вторые вершины ребер}

for i:=1 to nU do Read(f,We[i]);{Вес ребер}

Close(f);

Assign(f,C:hvivod.txt);

Rewrite(f); {Файл открыт для чтения}

Init;

Sort;

WriteLn(f,nU=,nU:3);

WriteLn(f,nX=,nX:3);

Write(f,X=); for i:=1 to nX do Write(f,X[i]:3);

WriteLn(f); Write(f,u1=);

for i:=1 to nU do Write(f,X[U[2*i-1]]:3);

WriteLn(f); Write(f,u2=);

for i:=1 to nU do Write(f,X[U[2*i]]:3);

WriteLn(f); Write (f,We=);

for i:=1 to nU do Write(f,We[i]:3);WriteLn(f);

Ostov;

Write(f,uo1=);

for i:=1 to nUo do Write(f,X[U[2*Uo[i]-1]]:3);

WriteLn(f);Write(f,uo2=);

Write(f,uo1=);

for i:=1 to nUo do Write(f,X[U[2*Uo[i]-1]]:3);

WriteLn(f);Write(f,uo2=);

for i:=1 to nUo do Write(f,X[U[2*Uo[i]]]:3);

WriteLn(f); Write(f,Woe=);

for i:=1 to nUo do Write(f,We[Uo[i]]:3);WriteLn(f);

Wt:=0;

for i:=1 to nUo do Wt:=Wt+We[Uo[i]];

Write(f,Bec=,Wt:3);

Close(f);

end.{Main}

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

После запуска программы на экране пользователя получили результаты программных расчетов (рис.8).

ЗАКЛЮЧЕНИЕ

При выполнении курсовой работы по дисциплине «Математические методы», требуется применение знаний полученные при изучении таких дисциплин, как, «Математические методы», «Дискретная математика», «Основы алгоритмизации и программирования».

В данной курсовой работе были рассмотрены понятия:

· алгоритм решения графов

· решение задачи ручным способом

· написание программы для решения задачи

· составление инструкций по использованию программы.

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

СПИСОК ЛИТЕРАТУРЫ

1. Вентцель Е.С. Исследование операций: задачи, принципы, методоло-гия. / Е.С. Вентцель. - М.: Высшая школа, 2001. - 487с.

2. Гончаров Г..А., Мочалин А.А. Элементы дискретной математики. /Г..А. Гончаров - М.: Форум - Инфра-М., 2004. - 128с.

3. Иванов Б.Н. Дискретная математика. Алгоритмы и программы./ Б.Н. Иванов - М.: Лаборатория Базовых Знаний, 2002. - 128с.

4. Кремер Н.Ш. Исследование операций в экономике./Н.Ш.Кремер - М.: ЮНИТИ, 2004. - 407с.

5. Кузнецов А.В. и др. Руководство к решению задач по математическому программированию./ А.В. Кузнецов. - Минск: Высшая школа, 2001. - 448 с.

6. Математическое программирование. Сборник задач и упражнений по высшей математике. / Под ред. Кузнецова А.В., Рутковского Р.А. - Минск: Высшая школа, 2002. - 447с.

7. Морозов И.Н., Сухарев Л.Г., Федоров В.В. Исследование операций в задачах и упражнениях. /И.Н Морозов. - М.: Высшая школа, 1986.-504с.

8. Новиков Ф.А. Дискретная математика для программистов. / Ф.А. Новиков. - С.-Петербург: Питер, 2001. - 304с.

9. Партыка Т.Л. Математические методы./ Т.Л.Партыка, И.И. Попов. - М.: ФОРУМ-ИНФРА-М, 2005. - 464с.

10. Советов Б.Я., Яковлев С.А. Моделирование систем. / Б.Я. Советов. - М.: Высшая школа, 2001. - 343с.

11. Чернов В.П., Ивановский В.Б. Теория массового обслуживания./ В.П. Чернов. - М.: Инфра-М, 2000. - 205с.