МІНІСТЕРСТВО ОСВІТИ
ФГТУ СПО «Беловскій політехнічний коледж»
Завдання Прима-Краскала про телефонної лінії
Курсовий проект
КР 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 1 u 2
u 4 u 3
Рисунок 1 - Діаграма графа G
Якщо елементами безлічі Є є впорядковані пари, то граф називається орієнтованим (або орграфів). У цьому випадку елементи множини V називаються вузлами, а елементи множини Е-дугами.
(1)
Якщо елементом множини Е може бути пара однакових (не різних) елементів V, то такий елемент безлічі Е називається петлею, а граф - графом з завісами (або псевдографом).
Якщо Е є не безліччю, а навпаки, містить кілька однакових елементів, то ці елементи називаються кратними ребрами, а граф називається мультиграфом.
Якщо елементами безлічі Є є не обов'язково двоелементний, а будь-які підмножини множини V, то такі елементи множини Е називаються гіпердугамі, а граф називається гіперграфа.
Якщо задана функція F: V → М і / або F: Е → ∩ М, то безліч М називається безліччю позначок, а граф називається поміченим (або навантаженим). Як безлічі позначок зазвичай використовуються букви або цілі числа.
Існують ізоморфні графи. Поняття ізоморфізму (схожості за формою) для графів має наочне тлумачення. Уявімо ребра графів еластичними нитками, що зв'язують вузли-вершини. Тоді ізоморфізм можна представити як переміщення вузлів і розтягування ниток. G 1 = (X 1, U 1, Ф 1) і G 2 = (X 2, U 2, Ф 2) - ізоморфні (G 1 G 2), якщо:
1 → X 2 і
: U 1 → U 2 (2)
Малюнок 2 - Ізоморфні графи
Якщо в графах ступінь кожної вершини однакова, то їх називають регулярними графами.
Якщо у графа немає ребер він є виродженим.
Підграф G 1 = (V 1, X 1) називається остовних подграфом, якщо множина його вершин збігається з безліччю вершин самого графа G = (V, X).
Граф, який може бути зображений на площині так, що його ребра не будуть перетинатися-це планарний (плоский) граф.
Межею графа, зображеного на деякій поверхні, називається частина поверхні, обмежена рйбрамі графа.
Граф називається зв'язковим, якщо для будь-яких двох вершин існує шлях, що з'єднує ці вершіни.Связний граф без циклів називається дерево.
Міст-ребро, видалення якого з мережі робить мережу незв'язною.
Граф називається максимально плоским або триангульовані, якщо неможливо додати до нього жодного ребра, щоб вони не перетиналися.
Зважена мережа-це така мережа, ребер або дуг якої поставлені у відповідність дійсні числа або величини, які приймають Г 1 = (X 1, U 1, Ф 1) і Г 2 = (X 2, U 2, Ф 2) - ізоморфні ( Г 1 Г 2), якщо:
1 → X 2 і
: U 1 → U 2 (3)
і приймаючі дествітельно значення (малюнок 3). При малюванні мережі ваги або вагові коефіцієнти не обов'язково повинні відповідати масштабу зображення.
Рисунок 3 - Зважена мережу
Слово «дерево» в теорії графів означає граф, в якому в відрізняє від маршрутів, немає циклів, тобто в якому не можна з деякою вершини пройти по декількох різних ребрах і повернутися в ту ж вершину.
Малюнок 4 - Дерево
Маршрут, або шлях - це послідовність ребер в неорієнтованому графі, в якому кінець кожного ребра збігається з початком наступного ребра. Число ребер маршруту називається його довгою.
Граф є деревом тоді і тільки тоді, коли кожна пара різних вершин поєднується однією і тільки одним ланцюгом. Якщо всі вершини графа G належать дереву Е, то вважається, що дерево покриває граф G.
Малюнок 5 - неорієнтовані зважений граф
Графи широко використовуються як в самій математиці, так і в її застосуваннях. Вони застосовуються при побудові різних математичних моделей: ліній електропередачі, мереж автодоріг, ліній повітряних сполучень і пр.
1.2 Представлення графів в ЕОМ
Графи є вельми зручним засобом опису і оптимізації алгоритмів обчислення. Відомі різні способи представлення графів в пам'яті комп'ютера, які різняться обсягом займаної пам'яті та швидкістю виконання операцій над графами. Представлення вибирається виходячи з потреб конкретного завдання. Розглянемо три способи:
Матриця суміжності. Подання графа за допомогою квадратної булевої матриці М: array [1 .. n, 1 .. n] of 0 .. 1, що відбиває суміжність вершин, називається матрицею суміжності, де 1 - якщо вершини суміжний, 0 - якщо вершини не суміжні.
Матриця інцидентності. Представлення матриці за допомогою прямокутної матриці, що відображає инцидентность вершини і ребра. Для не орієнтованого графа:
1 - якщо вершина инцидентна ребру, 0 - якщо не iнцидентна. Для орієнтованого графа:
1 - якщо вершина инцидентна ребру, і є його кінцем,
0 - якщо вершина і ребро не інцидентних,
-1 - Якщо вершина инцидентна ребру і є її початком.
Матриця ваг. Квадратна матриця, що містить вага ребра між двома вершинами.
1.3 Алгоритм Краскала
Завдання відшукання найкоротшого кістяка графа є класичною задачею теорії графів. Методи рішення цієї задачі послужили основою для багатьох інших важливих результатів. Завдання про знаходження найкоротшого кістяка належить до числа небагатьох задач теорії графів, які можна вважати повністю вирішеними. Між тим, якщо змінити умови завдання, на перший погляд навіть незначно, то вона виявляється значно більш важким.
Алгоритм будує найкоротший остов:
Вхід: граф G (V, E), заданий матрицею довжин ребер С.
Вихід: найкоротший остов Т.
Т: = 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 1 = 0,
Q 2 = Q 1 + З 12 = 0 +6 = 6
Q 7 = Q 2 + З 27 = 6 +3 = 9
Q 8 = Q 7 + З 78 = 9 +16 = 25 знайшли найкоротший шлях, знайдемо найкоротший шлях до решти міст Q 3 = Q 2 + З 23 = 6 +9 = 15, Q 4 = Q 3 + З 34 = 15 + 12 = 27, Q 6 = Q 2 + З 26 = 6 +5 = 11, Q 5 = Q 1 + З 15 = 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 містами, де потрібно було знайти оптимальний шлях прокладки телефонного кабелю в кожне місто. Мета курсової роботи - вирішити завдання про жадібний «алгоритмі», присвяченій знаходженню мінімальної суми довжин між його вершинами методом Прима-Краскала ручним і машинним способом.
СПИСОК ЛІТЕРАТУРИ
Вентцель Є.С. Дослідження операцій: завдання, принципи, методологія. / Є.С. Вентцель. - М.: Вища школа, 2001. - 487с.
Гончаров Г.. А., Мочалін А.А. Елементи дискретної математики. / Г.. А. Гончаров - М.: Форум - Инфра-М., 2004. - 128с.
Іванов Б. Н. Дискретна математика. Алгоритми і програми. / Б.М. Іванов - М.: Лабораторія Базових Знань, 2002. - 128с.
Кремер М. Ш. Дослідження операцій в економіці. / Н. Ш. Кремер - М.: ЮНИТИ, 2004. - 407С.
Кузнєцов А.В. та ін Керівництво вирішення завдань з математичного програмування. / О.В. Кузнєцов. - Мінськ: Вища школа, 2001. - 448 с.
Математичне програмування. Збірник завдань і вправ з вищої математики. / Под ред. Кузнєцова А.В., Рутковського Р.А. - Мінськ: Вища школа, 2002. - 447с.
Морозов І.М., Сухарєв Л.Г., Федоров В.В. Дослідження операцій в задачах і вправах. / І.Н Морозов. - М.: Вища школа, 1986.-504с.
Новіков Ф.А. Дискретна математика для програмістів. / Ф.А. Новіков. - С.-Петербург: Питер, 2001. - 304с.
Партика Т.Л. Математичні методи. / Т. Л. Партика, І.І. Попов. – М.: ФОРУМ-ИНФРА-М, 2005. – 464с.
Советов Б.Я., Яковлев С.А. Моделирование систем. / Б.Я. Советов. - М.: Высшая школа, 2001. – 343с.
Чернов В.П., Ивановский В.Б. Теория массового обслуживания./ В.П. Чернов. - М.: Инфра-М, 2000. – 205с.