Навигация
2. ТЕОРЕТИЧНА ЧАСТИНА
2.1 Відомості про графи
Граф G (рис.2.1.1) задається множиною точок (вершин) х1, х2,..., хn. (Яке позначається через Х) і безліччю ліній (ребер) а1, а2,...,аm. (Яке позначається символом А), що з'єднують між собою всі або частину цих точок. Таким чином, граф G повністю задається (і позначається) парою (Х, А). Якщо ребра з множини А орієнтовані, що зазвичай показується стрілкою, то вони називаються дугами, і граф з такими ребрами називається орієнтованим графом.
Рис.2.1.1 
Рис.2.1.2
Наприклад, якщо дорога має не двохсторонній, а односторонній рух то напрямок цього руху буде показано стрілкою. Якщо ребра не мають орієнтації, то граф називається неорієнтованим, (двосторонній рух). У орієнтованому графі дуга позначається впорядкованої парою, що складається з початкової та кінцевої вершин, її напрямок передбачається заданим від першої вершини до другої.
Шляхом (або орієнтованим маршрутом) орієнтованого графа називається послідовність дуг, в якій кінцева вершина будь-якої дуги, відмінною від останньої, є початковою вершиною наступної.
Так, на рис. 2.1.2 шляхами є послідовності дуг: а6, а5, а9, а8, а4. (1) а1, а6, а5, а9. (2) а1, а6, а5, а9, а10, а6, а4. (3) Орієнтованої ланцюгом (орцепью) називається такий шлях, в якому кожна дуга використовується не більше одного разу. Простим ланцюгом називається такий шлях, в якому кожна вершина використовується не більше одного разу. Наприклад, шлях (2). Маршрут є неорієнтований "двійник" шляху, і це поняття розглядається в тих випадках, коли можна знехтувати спрямованістю дуг у графі. Таким чином, маршрут є послідовність ребер ä1, ä2 ,..., äq, в якій кожне ребро аi, за винятком першого і останнього ребер, пов'язане з ребрами аi-1 і аi+1 своїми кінцевими вершинами. Послідовності дуг: ä2, ä4, ä8, ä10, (4) ä2, ä7, ä8, ä4, ä3, (5) ä10 , ä7 , ä4 , ä8 , ä7 , ä2. (6) у графі, зображеному на рис. 2.1.2, є маршрутами; дві точки над символом дуги означають, що її орієнтацією нехтують, тобто дуга розглядається як неорієнтовані ребро. Також шлях або маршрут можна зображати послідовністю вершин. Наприклад, шлях (1) буде виглядати наступним чином: х2, х5, х4, х3, х5, х6. Іноді дуг графа приписуються числа, що називаються вагою, вартістю, або довжиною цієї дуги. У цьому випадку граф називається графом із завислими дугами. А якщо вага приписується вершин графа, то тоді виходить граф з зваженими вершинами. Якщо в графі ваги приписані і дуг і вершин, то він називається просто зваженим. При розгляді шляху μ представленого послідовністю дуг (ä1, ä2,..., äq), за його вага приймається число l (μ), яка дорівнює загальній кількості ваг всіх дуг, що входять в μ, тобто
2.2 Алгоритм Дейкстри
Алгоритм Дейкстри будує найкоротші шляхи, що ведуть з вихідної вершини графа до решти вершин цього графа (якщо такі є). У процесі роботи алгоритму послідовно позначаються розглянуті вершини графа. При чому вершина, позначена останньої (на даний момент) розташована ближче до вихідної вершині, ніж всі непозначених, але далі, ніж всі помічені. Спочатку позначається вихідна вершина; наступної, очевидно, буде позначена вершина, найближча до початкової, і суміжна з нею. Нехай на якомусь кроці вже позначені кілька вершин. Відомі найкоротші шляхи, що ведуть з вихідної вершини до поміченої. Для кожної з непозначених вершин проробимо наступне: 1. Розглянемо всі дуги, провідні з помічених вершин в одну непозначених. Кожна така дуга є останньою дугою на шляху з вихідної вершини в цю непозначену. 2. Виберемо з цих шляхів найкоротший. А потім виберемо серед них самий короткий до всіх непозначених вершин, і позначимо вершину, до якої він веде. Алгоритм завершиться, коли будуть помічені всі досяжні вершини. У результаті роботи алгоритму Дейкстри будується Дерево найкоротших шляхів.
3. ОСОБЛИВОСТІ РОБОТИ В СЕРЕДОВИЩІ
При написанні програми використовувалася середу Microsoft Visual C + + 6.0. Дане середовище дозволяє писати програми на мові C + +. У ході написання програми всі оператори і службові слова мови С + + виділяються іншим кольором, щоб відрізняти їх від змінних, заданих програмістом. Середовище Microsoft Visual C + + 6.0 містить вбудований компілятор. Вікно програми розділене на декілька частин. Вгорі знаходиться стандартна панель - Standart, з якою можна зберегти вихідний текст програми на диск, відкрити новий документ, скопіювати або вставити текст, скасувати останню дію, або знайти текст. Зліва знаходяться панелі Object TreeView і Object Inspector, на яких показані об'єкти, які використовуються в даній програмі, та їх властивості. У центрі вікна програми розташований текстовий редактор, в якому слід писати програму. Внизу - панель Output, в якій показується повідомлення, якщо в програмі містяться помилки - компілятор повідомляє вид помилки і рядок, в якій вона допущена, досить зробити подвійний клік лівою клавішею миші на описі помилки в Output, щоб переміститися на рядок, що містить помилки. Програма створена в консольному режимі - в режимі, що не має графічного інтерфейсу.
Похожие работы
... зноманітними типами транспортних засобів з урахуванням обмеження на обсяг робот, що можуть виконати транспортні засоби. РОЗДІЛ 3 МАТЕМАТИЧНА МОДЕЛЬ ТРАНСПОРТНОЇ СИСТЕМИ ПІДПРИЄМСТВА 3.1 Структура моделі У якості структурної моделі транспортної системи підприємства можна запропонувати схему, що складається з трьох рівнів. Необхідно відзначити, що з метою деякого спрощення задачі розгляда ...
... і певну кількість нових машин). Більшість дискретних і комбінаторних задач можна вирішити шляхом перебору. Проте перебірні методи мають експоненційну складність. Проблема: знайти метод вирішення експоненційних задач за поліноміальний час. 3.1 Планування в просторі станів. Основні поняття теорії графів Граф – сукупність вершин і дуг. Для комп’ютерного опису графу використовуються: матриця і ...
... графа рівно один раз. Означення.3.2 . Зв’язний граф називається напівгамільтоновим , якщо існує ланцюг , який проходить через кожну його вершину рівно один раз. Не дивлячись на подібність в означеннях ойлерових та гамільтонових графів, відповідно теорії для цих класів графів сильно відрізняються. До теорії гамільтонових графів відноситься і задача про бродячого тор-говця, або задача про комі ...
... оцінка складності алгоритму - О(n*log(n)). Даний алгоритм має сенс застосування лише на великих обсягах даних від 500-1000 елементів. Тільки в цьому випадку можна побачити виграш алгоритму в ефективності. Для менших обсягів даних він малопридатний. 3 Синтез машини Тьюрінга 3.1 Загальні відомості Машина Тьюрінга - це кінцевий автомат, забезпечений безкінченою стрічкою і читаючою/записуючою голівкою ...
0 комментариев