43496

Исследование и программная реализация методов алгоритмов теории графов

Курсовая

Информатика, кибернетика и программирование

Реализовать выбранный алгоритм на языке Pscl желательно использовать представление графа списками. Пояснительная записка включает в себя 23 страницы текста рисунок исходного графа рисунок МОД схему алгоритма 2 использованных источника. Данная программа позволяет: Ввести граф используя матрицу длин дуг; Получить матрицу задающую минимальное остовное дерево; Провести тестирование алгоритма; Введение Во многих прикладных задачах теории графов важно иметь возможность сопоставить ребрам графа определенные числа которые соответствуют...

Русский

2013-11-06

115 KB

23 чел.

10

PAGE  17

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

ГОУВПО «Сибирский государственный технологический университет»

Кафедра: системотехники

ДИСКРЕТНАЯ МАТЕМАТИКА

ИСЛЕДОВАНИЕ

МЕТОДОВ И АЛГОРИТМОВ ТЕОРИИ ГРАФОВ

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

Пояснительная записка

(ИТ. 000000.000 КР)

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

                                        Иванилова Т.Н.

                                                                                                                ______________________________

                                                                                                                     дата                      оценка                 роспись

                             Выполнил:

                                               Студент группы 21-6

                                       Идельсон  С.Е.                                                                                                                                                        

                                                                                                              ______________________________   

                                                                                                                     дата сдачи                                   роспись

Сибирский государственный технологический университет

Кафедра: системотехники

ЗАДАНИЕ

НА КУРСОВУЮ РАБОТУ ПО ДИСКРЕТНОЙ МАТЕМАТИКЕ

Студент       Идельсон Сергей Евгеньевич

Факультет  ФАИТ Группа 21-6

Тема:  Исследование и программная реализация методов алгоритмов теории графов.

Вариант 6   

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

Предложенную задачу сформулировать в терминах теории графов и подобрать соответствующий алгоритм.

Реализовать выбранный алгоритм на языке Pascal, желательно использовать представление графа списками. Предусмотреть возможность ввода разнообразных входных данных.

Окончательный вариант программы должен отображать смысловую постановку задачи.

Приложить распечатки экранов.

Содержание

Реферат

Введение

1 Деревья в теории графов. Минимальное остовное дерево

2 Решение задачи

2.1 Входная и выходная информация

2.2 Схема алгоритма

2.3 Текст программы

2.4 Протокол контрольного расчета

3 Инструкция по работе с программой

Заключение

Список использованных источников

Реферат

Расчетно-графическая работа представляет собой решение задачи по расчету минимального остовного дерева. Расчет выполнен с помощью языка программирования  Turbo Pascal 7.0 на ПК AMD Athlon XP 1900+.

Пояснительная записка включает в себя 23 страницы текста, рисунок исходного графа, рисунок МОД, схему алгоритма, 2 использованных источника.

Ключевые слова: граф, дерево, минимальное остовное дерево.

Цель работы: овладеть навыками работы  с алгоритмом построения минимального остовного дерева.

Метод исследования – теория графов, алгоритмизация, язык программирования Pascal.

Данная программа позволяет:

  1.  Ввести граф, используя матрицу длин дуг;
  2.  Получить матрицу, задающую  минимальное остовное дерево;
  3.  Провести тестирование алгоритма;

Введение

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

1 Деревья в теории графов. Минимальное остовное дерево

Дерево – это связный графа, который не содержит циклов.

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

Остовное дерево (ОД) – любой связный подграф связного графа , содержащий все вершины и являющийся деревом.

Минимальное остовное дерево (МОД) – остовное дерево нагруженного графа с минимальной суммой длин дуг содержащихся в нем.

Для нахождения МОД в программе был использован алгоритм Крускала:

1. Сортируем ребра графа по возрастанию весов.
2. Полагаем, что каждая вершина относится к своей компоненте связности.
3. Проходим ребра в "отсортированном" порядке. Для каждого ребра выполняем:

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

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

2 Решение задачи

2.1. Входная и выходная информация

Для задания нагруженного графа используется матрица длин дуг графа. Размер матрицы задается автоматически при указании количества вершин.  Максимальное количество вершин восемь. Выходная информация это матрица МОД. Она представляет собой квадратную матрицу N x N (где N количество вершин). На пересечении строк и столбцов стоит ноль если вершина не достижима в МОД из вершины определяемой строкой и вес ребра если достижима.

2.3 Текст программы

…………………………………

2.4 Протокол контрольного расчета

Возьмем 7 городов, а длинны дорого зададим матрицей длин дуг. 

0

120

30

25

190

0

170

120

0

0

80

0

0

200

30

0

0

0

180

65

0

25

80

0

0

0

0

80

190

0

180

0

0

75

100

0

0

65

0

75

0

0

170

200

0

80

100

0

0

В результате получим следующий граф

в результате получили матрицу задающую МОД

0

0

0

0

0

0

0

0

0

0

0

0

0

0

30

0

0

0

0

65

0

25

80

0

0

0

0

80

0

0

0

0

0

0

0

0

0

0

0

75

0

0

0

0

0

0

0

0

0

МОД:

3 Инструкция по работе с программой

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

Работа с алгоритмом:

  1.  Ввести количество городов.
  2.  Заполнить последовательно матрицу длин дуг, обращая внимание на номер ячейки, т.к. матрица автоматически вводиться симметрично.
  3.   После появления экрана с графом нажимаем Enter.
  4.  После просмотра матрицы задающей МОД нажимаем Enter.
  5.  Просмотр МОД.
  6.  После нажатия Enter’а выход из программы.

Необходимое программное обеспечение для работы программы:

MS-DOS, MS Windows95/98/Me/2000/XP

Заключение

Программа работает достаточно быстро. Приведенный алгоритм решения поставленной задачи иногда в результате работы программы не всегда дает полностью оптимальное МОД.

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

Список использованных источников

  1.  Иванилова Т.Н. Дискретная математика: Сборник заданий для курсовых работ с примерами выполнения. – Красноярск: СибГТУ, 2004.
  2.  Логинов Б.М. Введение в дискретную математику. – Калуга 1998.


Начало
Zmat

i:=1 ton

j:=1 ton

m[i,j]:=0;

Конец Zmat

Начало Readmat

i:=1 ton

Конец Readmat

:=1

j<=n

да

j=i

inc(j)

m[i,j]

m[j,i]:=m[i,j];              inc(j);

да

Начало Pmat

flag and i<=n-1

Sum:=0

j:=1 to n-1

sum:=sum+m[i,j];

flag:=(sum<>0); inc(i);

да

Конец Pmat

Начало процедуры minot

m:=1; i:=1

i<=n

j:=1

да

j<=n

да

m[i,j]<>gm

inc(w);    E[w,1]:=i;          E[w,2]:=j;

ew[w]:=m[i,j];

mot[i,j]:=gm;   inc(j);

inc(i);

i:=1;

i<m

j:=1

да

j<=m-1

да

ew[j]>=ew[j+1]

t:=ew[j];   ew[j]:=ew[j+1];   ew[j+1]:=t;          k:=e[j,1]; e[j,1]:=e[j+1,1];    e[j+1,1]:=k;          k:=e[j,2]; e[j,2]:=e[j+1,2];    e[j+1,2]:=k;

inc(j);

inc(i);

да

i:=1;

i<=n

q:=n-1;   i:=1;

да

v[i]:=i;  inc(i);

i<=w and q<>0

v[e[i,1]]<>v[e[i,2]]

да

да

t:=v[e[i,2]];  mot[e[i,1],e[i,2]]:=ew[i];   j:=1;             

j<=n

да

v[j]=t

v[j]:=v[e[i,1]];

inc(j);

q:=q-1;

inc(i);

Конец процедуры minot

Начало

N

n>=2 and n<=8

да

Zmat (n,m);

ReadMat (n,m);

Pmat(n,m,f);

not(f)

да

i:=1 ton

j:=1 ton

minot (n,m,mot)

mot[i,j],'  '

WriteLn

DrawGraph(n,mot);

Конец

DrawGraph(n,m);

1

3

5

6

4

2

7

1

3

5

6

4

2

7


 

А также другие работы, которые могут Вас заинтересовать

20237. Ефект Джоуля-Томсона 88.5 KB
  Ефект ДжоуляТомсона Ефект ДжоуляТомсона – це зміна температури газу в результаті адіабатичного дроселювання€ – постійне протікання газу під дією постійного перепаду тиску газів крізь пористу перегородку яка розміщена на шляху потоку. В дослідах Джоуля і Томсона вимірювалась температура в двох послідовних перерізах неперервного і стаціонарного потоках газу до дроселя та за ним. Дійсно при взаємному притяганні молекул внутрішня енергія газу включає як кінетичну енергію молекул так і потенціальну енергію їх взаємодії. Робота...
20238. Поширення пружних хвиль у рідинах. Залежність швидкості поширення та коефіцієнта поглинання від термодинамічних параметрів 115.5 KB
  Щоб описати розповсюдження хвилі в середовищі необхідно записати хвильове рівняння. Для цього: 1 Записати рівняння руху частинки середовища – макроскопічно малого об’єму середовища лінійні розміри об’ємчику набагато менші довжини хвилі звука; 2 Записати реологічне рівняння для середовища. 3 Підставити реологічне рівняння в рівняння руху → хвильове рівняння для данного середовища. Реологічне рівняння – це рівняння яке пов’язує тензор напруг з тензором деформацій і тензором швидкості деформацій.
20239. Міжмолекулярна взаємодія в газах та рідинах 62.5 KB
  Вона базується на припущеннях: міжмолекулярна взаємодія є слабкою – розміри частинок набагато менше за відстань між ними; адіабатичне наближення – електростатичне поле сусідньої молекули збурює енергетичні стани лише електронів; наближення мультипольного розкладу – електричні заряди в молекулі по об’єму розповсюджені нерівномірно і можуть бути вільні заряди: монополі диполі квадруполі октуполі. Енергія міжмолекулярної взаємодії – це потенціальна енергія однієї молекули в електростатичному полі другої молекули. Маємо дві молекули А і В...
20240. Розсіяння нейтронів як джерело інформації про динаміку молекул 101 KB
  Розсіяння нейтронів як джерело інформації про динаміку молекул Існує загальний метод опису динаміки речовини – просторовочасові корелятивні функції. Одним із шляхів визначення корелятивних функцій є розсіяння нейтронів. Візьмемо двічі диференційний переріз розсіяння нейтронів – кількість нейтронів що вилетять із зразка під певним кутом в елемент тілесного кута і при цьому зміна енергії нейтронів потрапляє в інтервал від до де пр – пружне нп – непружне ког – когерентне нк – некогерентне. Наслідком цього є розбиття перерізу...
20241. Понятие, предмет, задачи дисциплины «охрана труда в отрасли» 108 KB
  Охрана труда как социально-экономический фактор и область науки. Этапы развития охраны труда. Понятие охраны труда в законодательстве Украины. Предмет, содержание и задачи дисциплины охраны труда в отрасли. Взаимодействие охраны труда с другими дисциплинами.
20242. Основи методу Монте-Карло 146.5 KB
  точки та розрахувати в кожному полож. точки її енергію з частинками системи. Будується ланцюг випадкових переміщень однієї точки. точки; 2 обрати модель потенціальної енергії; 3задати температуру та довжину кроку відображ.
20243. Полімерний стат. клубок 46.5 KB
  клубок Полімерні молекули – ланцюги з великої кількості ланок вони можуть відрізнятися сладом однакові ланки або різні степенем гнучкості числом гілок та заряджених груп. Найпростіша полімерна молекула – послідовність великої кількості атомних груп з`єднаних у ланцюг ковалентними хімічними зв`язками. N масі ланцюга. Полімерний ланцюг має N 1 N 102 104 Полімерні молекули поділяються на лінійні та тривимірні.
20244. Спектральний склад розсіяного світла в газах. Ефект Мандельштама-Брілюена 85 KB
  Спектральний склад розсіяного світла в газах. Розсіяння світла – це зміна якоїсь характеристики потоку оптичного випромінювання світла при його взаємодії з речовиною. Цими характеристиками можуть бути просторовий розподіл інтенсивності частотний спектр поляризація світла. Фізична причина розсіяння світла в чистій речовині полягає в тому що в силу статистичної природи теплового руху молекул середовища в ньому виникають флуктуації густини.
20245. Особливості реологічної неньютонівської рідини 90 KB
  Не ньютонівська течіяпри різних швидкостях течії рідина характеризується різними в‘язкостями. Для того щоб визначити поняття не ньютонівської рідини згадаємо що таке ньютонівська рідина. Бінгалівська рідина межа пластичностітобто в системі існує область де напруження не впливає на зсув характерною ознакою є те що течія починається коли дотичне напруження τ перевищує межу пластичності θ. ; немає зсуву шарів рідина рухається як жорсткий стержень.