Воронезька ІНСТИТУТ ВИСОКИХ ТЕХНОЛОГІЙ
Факультет заочного та післявузівської навчання
1 Курсовий проект
З дисципліни: «Технологія програмування»
Тема: «Визначення найкоротшого шляху в графі"
2
Воронеж 2004
ЗМІСТ
ВСТУП 3 < p> 1. Теорія Графов. 4
1.1. Історична довідка. 4
1.2. Основні терміни та теореми теорії графів. 9
2. Завдання на графах. 15
2.1. Опис різних задач на графах. 15
2.2. Знаходження найкоротших шляхів у графі 16
3. Програма визначення найкоротшого шляху в графі 19
3.1. Мова програмування Delphi. 19
3.2. Програма «Визначення найкоротшого шляху в графі» 20
ВИСНОВОК 25
СПИСОК ЛІТЕРАТУРИ 27
ДОДАТОК 28
Текст програми визначення найкоротшого шляху до графі 28
ВСТУП
Початок теорії графів як математичної дисципліни було покладено
Ейлером в його знаменитому міркування про Кенігсберзький мостах. Однак цястаття Ейлера 1736 була єдиною протягом майже ста років. Інтересдо проблем теорії графів відродився близько середини минулого століття і бувзосереджений головним чином в Англії. Малося багато причин для такогопожвавлення вивчення графів. Природничі науки зробили свій вплив на цезавдяки дослідженням електричних ланцюгів, моделей кристалів і структурмолекул. Розвиток формальної логіки призвело до вивчення бінарних відносин уформі графів. Велика кількість популярних головоломок подавалося формулюваньбезпосередньо в термінах графів, і це призводило до розуміння, що багатозадачі такого роду містять деякий математичне ядро, важливістьякого виходить за рамки конкретного питання. Найбільш знаменита середцих завдань-проблема чотирьох фарб, вперше поставлена перед математиками
Де Морганом близько 1850 року. Жодна проблема не викликала такоїчисленних і дотепних робіт в галузі теорії графів. Завдяки своїйпростий формулюванні і дратівливою невловимості вона до цих пір залишаєтьсяпотужним стимулом досліджень різних властивостей графів.
Справжнє століття було свідком неухильного розвитку теоріїграфів, яка за останні десять - двадцять років вступила в новий періодінтенсивних розробок. У цьому процесі явно помітно вплив запитів новихобластей: теорії ігор і програмування, теорії передачі повідомлень,електричних мереж і контактних ланцюгів, а також проблем психології ібіології.
Внаслідок цього розвитку предмет теорії графів є вжевеликим, що всі його основні напрямки неможливо викласти в одномутомі. У цьому першому томі пропонованого двотомного праці зроблений акцептна основні поняття і на результати, які викликають особливий систематичнийінтерес.
За теорії графів є дуже мало книг; основний була книга Д.
Кеніга (1936), яка для свого часу давала поскільки введення впредмет. Досить дивно, що таких книг на англійській мові до цих пір небуло, не дивлячись на те, що багато найважливіших результати були отриманіамериканськими і англійськими авторами.
1. Теорія Графов.
1
2 1.1. Історична довідка.
Теорія графів - це область дискретної математики, особливістюякої є геометричний підхід до вивчення об'єктів. Теорія графівзнаходиться зараз у самому розквіті. Зазвичай її відносять до топології (томущо в багатьох випадках розглядаються лише топологічні властивості графів),однак вона перетинається з багатьма розділами теорії множин, комбінаторноїматематики, алгебри, геометрії, теорії матриць, теорії ігор, математичноїлогіки і багатьох інших математичних дисциплін. Основний об'єкт теоріїграфів-граф і його узагальнення.
Перші завдання теорії графів були пов'язані з вирішенням математичнихрозважальних завдань і головоломок (задача про Кенігсберзький мостах, завданняпро розстановку ферзів на шаховій дошці, задачі про перевезення, завдання прокругосвітню подорож та інші). Одним з перших результатів в теоріїграфів з'явився критерій існування обходу всіх ребер графа безповторень, отриманий Л. Ейлером при вирішенні задачі про Кенігсберзькиймостах. Ось переказ уривка з листа Ейлера від 13 березня 1736: "Менібула запропонована задача про острові, розташованому в місті Кенігсберг іоточеному річкою, через яку перекинуто 7 мостів. Постає питання, чи можехто-небудь безперервно обійти їх, проходячи тільки одного разу через кожен міст.
І тут же мені було повідомлено, що ніхто ще до сих пір не зміг це зробити,але ніхто і не довів, що це неможливо. Питання це, хоча й банальний,здався мені, проте, гідним уваги тим, що для його вирішеннянедостатні ні геометрія, ні алгебра, ні комбінаторне мистецтво. Післядовгих роздумів я знайшов легке правило, засноване на цілкомпереконливий доказ, за допомогою якого можна у всіх завданняхтакого роду негайно визначити, чи може бути здійснений такий обхід черезяке завгодно число і як завгодно розташованих мостів або не може ".
Кенігсберзький мости схематично можна зобразити так:
Правило Ейлера:
1. У графі, що не має вершин непарних ступенів, існує обхід всіх ребер (причому кожне ребро проходиться в точності один раз) з початком в будь-якій вершині графа.
2. У графі, що має дві і тільки дві вершини з непарними ступенями, існує обхід з початком в одній вершині з непарної ступенем і кінцем в іншій.
3. У графі, що мають більше двох вершин з непарної ступенем, такого обходу не існує.
Існує ще один вид задач, пов'язаних з подорожами уздовжграфів. Мова йде про завдання, в яких потрібно відшукати шлях, що проходитьчерез всі вершини, причому не більше одного разу через кожну. Цикл,що проходить через кожну вершину один і лише один раз, носить назвуГамільтона лінії (на честь Вільяма Роуена Гамільтона, знаменитогоірландського математика минулого століття, який першим почав вивчати такілінії). На жаль, поки що не знайдена спільна критерій, за допомогою якогоможна було б вирішити, чи є даний граф Гамільтона, і якщо так, тознайти на ньому все Гамільтона лінії.
Сформульована в середині 19 ст. проблема чотирьох фарб такожвиглядає як розважальна завдання, проте спроби її рішення призвели допояви деяких досліджень графів, що мають теоретичне іприкладне значення. Проблема чотирьох фарб формулюється так: "Чи можнаобласть будь-якої плоскої карти розфарбувати чотирма кольорами так, щоб будь-якідві сусідні області були розфарбовані в різні кольори? ". Гіпотеза про те,що відповідь позитивну, була сформульована в середині 19ст. У 1890 роцібуло доведено більш слабке твердження, а саме, що будь-яка плоска картарозфарбовується в п'ять кольорів. Зіставляючи будь-якій плоскій карті двоїстийїй плоский граф, отримують еквівалентну формулювання задачі в термінахграфів: Чи правда, що хроматичної число будь-якого плоского графа менше абоодно чотирьох? Численні спроби вирішення завдання вплинули нарозвиток ряду напрямків теорії графів. У 1976 році анонсованопозитивне рішення задачі з використанням ЕОМ.
Інша стара топологічна завдання, яке особливо довго непіддавалася рішенням і розбурхувала розуми любителів головоломок, відома як
"Задача про електро -, газо - і водопостачання". У 1917 році Генрі Е. Дьюденідав їй таке формулювання. У кожний з трьох будинків, зображених на малюнку,необхідно провести газ, світло і воду.
Світло вода газ
Чи можна так прокласти комунікації, щоб вони, ніде не перетинаючисьодин з одним, з'єднували кожен будинок з джерелами електрики, газу іводи? Інакше кажучи, можна побудувати плоский граф з вершинами в шестизазначених точках? Виявляється, такий граф побудувати не можна. Про цейдеться в однієї дуже важливої теореми - так званої теореми
Куратовского. Теорема стверджує, що кожен граф, який не є плоским,містить як подграфа один з двох найпростіших просторовихграфів:
У середині 19 ст. з'явилися роботи, в яких при вирішенніпрактичних завдань були отримані результати, пов'язані з теорії графів.
Так, наприклад, Г. Кирхгоф при складанні повної системи рівнянь дляструмів і напруги в електричній схемі запропонував по суті представлятитаку схему графом і знаходити в цьому графі остовне дерева, за допомогоюяких виділяються лінійно незалежні системи контурів. А. Келі, виходячиіз завдань підрахунку числа ізомерів граничних вуглеводнів, прийшов до завданьперерахування та описи дерев, що володіють заданими властивостями, і вирішивдеякі з них.
У 20 ст. завдання, пов'язані з графами, почали виникати не тільки вфізики, хімії, електротехніки біології, економіки, соціології і т.д., але йвсередині математики, в таких розділах, як топологія, алгебра, теоріяймовірностей, теорія чисел. На початку 20 ст. графи стали використовуватися дляпредставлення деяких математичних об'єктів і формальної постановкирізних дискретних завдань; при цьому поряд з терміном «граф» вживалисята інші терміни, наприклад, карта, комплекс, діаграма, мережа, лабіринт.
Після виходу в світ в 1936 році монографії Д. Кеніга термін «граф» ставбільш вживаною, ніж інші. У цій роботі були систематизованівідомі на той час факти. У 1936 році вийшла невеличка брошура Ойстена
Оре, що містить блискуче елементарне введення в теорію графів. У 1962році в Англії була видана книга французького математика Клода Берже "Теоріяграфів та її застосування ". Обидві книги, безумовно, становлять інтерес длялюбителів цікавої математики. Сотні відомих головоломок, на першийпогляд не мають нічого спільного один з одним, легко вирішуються за допомогоютеорії графів.
У 20-30-х роках 20 ст. з'явилися перші результати, пов'язані звивченню властивостей зв'язності, планарними, симетрії графів, які призвелидо формування ряду нових напрямків в теорії графів.
Значно розширилися дослідження з теорії графів в кінці 40-х
- На початку 50-х років, перш за все в силу розвитку кібернетики таобчислювальної техніки. Завдяки розвитку обчислювальної техніки, вивченняскладних кібернетичних систем, інтерес до теорії графів зріс, апроблематика теорії графів істотно збагатилася. Крім того,використання ЕОМ дозволило вирішувати виникаючі на практиці конкретнізавдання, пов'язані з великим об'ємом обчислень, раніше не піддаватисярішенням. Для ряду екстремальних задач теорії графів були розроблені методиїх вирішення, наприклад, один із таких методів дозволяє вирішувати задачі пропобудові максимального потоку через мережу. Для окремих класів графів
(дерева, плоскі графи і т. д.), які вивчалися і раніше, було показано,що рішення деяких завдань для графів з цих класів знаходяться простіше, ніждля довільних графів (знаходження умов існування графів ззаданими властивостями, встановлення ізоморфізму графів та ін.)
Характеризуючи проблематику теорії графів, можна відзначити, щодеякі напрямки носять більш Комбінаторний характер, інші - більшгеометричний. До перших відносяться, наприклад, задачі про підрахунок іперерахування графів з фіксованими властивостями, завдання про побудову графівіз заданими властивостями. Геометричний (топологічний) характер носятьбагато цикли задач теорії графів, наприклад, графів обходи, графів укладання.
Існують напрямки, пов'язані з різними класифікаціями графів,наприклад, за властивостями їх розкладання.
Прикладом результату про існування графів з фіксованимивластивостями може служити критерій реалізованості чисел ступенями вершиндеякого графа: набір цілих чисел, сума яких парна, можнареалізувати ступенями вершин графа без петель і кратних ребер тоді ітільки тоді, коли для будь-якого r виконується умова
Прикладами задач про підрахунок графів із заданими властивостями єзадачі про знаходження кількостей неізоморфних графів з однаковим числомвершин і (або) ребер. Для числа неізоморфних дерев з n вершинами булаотримана асимптотична формула де C == 0,534948 ..., e == 2,95576 ...
Для числа Gn неізоморфних графів без петель і кратних ребер з nвершинами було показано, що
Поряд з проблемами, що носять загальний характер, в теорії графівє специфічні цикли задач. В одному з них вивчаються різнівластивості зв'язності графів, досліджується будова графів за властивостямизв'язності. При аналізі надійності мереж зв'язку, електронних схем,комунікаційних мереж виникає задача про знаходження кількостейнепересічних ланцюгів, що з'єднують різні вершини графа. Тут отриманийряд результатів. Наприклад, найменше число вершин, що розділяють дванесуміжні вершини графа, так само найбільшому числу непересічних (повершин) простих ланцюгів, що з'єднують цю пару вершин. Знайдено критерії тапобудовані ефективні алгоритми встановлення міри зв'язності графа
(найменшого числа вершин або ребер, видалення яких порушує зв'язністьграфа).
В іншому напрямку досліджень теорії графів вивчаються маршрути,що містять всі вершини або ребра графа. Відомий простий критерійіснування маршруту, що містить усі ребра графа: у зв'язкового графі цикл,що містить всі ребра і проходить по кожному ребру один раз, існуєтоді і тільки тоді, коли всі вершини графа мають парні ступеня. Увипадку обходу безлічі вершин графа є тільки ряд достатніх умовіснування циклу, що проходить по всіх вершин графа по одному разу.
Характерним специфічним напрямом теорії графів є цикл завдань,пов'язаний з розфарбовуваннями графів, в якому вивчаються розбиття множинивершин (ребер), що володіють певними властивостями, наприклад, суміжнівершини (ребра) повинні належати різним множинам (вершини або ребраз одного безлічі фарбують одним кольором). Було доведено, щонайменше число кольорів, достатню для розфарбування ребер будь-якого графа безпетель з максимальним ступенем a, так само Зa/2, а для розфарбування вершин будь-якогографа без петель і кратних ребер досить a 1 квітів.
Існують й інші цикли завдань, деякі з них склалися підвпливом різних розділів математики. Так, під впливом топологіїпроводиться вивчення вкладень графів в різні поверхні. Наприклад,було отримано необхідне і достатня умова вкладення графа в площину
(критерій Понтрягина - Куратовского див. вище): граф є плоским тодіі тільки тоді, коли він не містить подграфов, одержуваних за допомогоюподразбіенія ребер з повного 5-вершинного графа і повного дводольнихграфа з трьома вершинами в кожній частці. Під впливом алгебри стали вивчатисягрупи автоморфізмів графів. Зокрема, було доведено, що кожнакінцева група ізоморфна групі автоморфізмів деякого графа. Впливтеорії ймовірностей позначилося на дослідженні графів випадкових. Багатовластивості були вивчені для «майже всіх» графів; наприклад, було показано, щомайже всі графи з n вершинами пов'язані, мають діаметр 2, володіютьГамільтона циклом (циклом, що проходить через усі вершини графа по одномуразу).
У теорії графів існують специфічні методи вирішенняекстремальних задач. Один з них заснований на теоремі про максимальний потік імінімальному розрізі, яка стверджує, що максимальний потік, який можнапропустити через мережу з вершини U в вершину V, дорівнює мінімальнійпропускної здатності розрізів, що розділяють вершини U і V. Були побудованірізні ефективні алгоритми знаходження максимального потоку.
Велике значення в теорії графів мають алгоритмічні питання. Длякінцевих графів, тобто для графів з кінцевим безліччю вершин і ребер, якправило, проблема існування алгоритму рішення задач, у тому числіекстремальних, вирішується позитивно. Вирішення багатьох завдань, пов'язаних зкінцевими графами, може бути виконано за допомогою повного перебору всіхдопустимих варіантів. Проте у такий спосіб вдається вирішити завдання тількидля графів з невеликим числом вершин і ребер. Тому істотне значеннядля теорії графів має побудова ефективних алгоритмів, що знаходять точнеабо наближений розв'язок. Для деяких завдань такі алгоритми побудовані,наприклад, для встановлення планарними графів, визначення ізоморфізмудерев, знаходження максимального потоку.
Результати та методи теорії графів застосовуються при вирішеннітранспортних задач про перевезення, для знаходження оптимальних рішень задачіпро призначення, для виділення «вузьких місць» при плануванні і управліннірозробок проектів, при складанні оптимальних маршрутів доставки вантажів,а також при моделюванні складних технологія, процесів, в побудовірізних дискретних пристроїв, в программірованіі і т. д.
3 1.2. Основні терміни та теореми теорії графів.
Граф - Пара об'єктів G = (X, Г), де Х - кінцеве безліч, а Г
-Кінцеве підмножина прямого твори Х * Х. При цьому Хназивається безліччю вершин, а Г - безліччю дуг графа G.
Будь-яке кінцеве безліч точок (вершин), деякі з яких попарноз'єднані стрілками, (в теорії графів ці стрілки називаються дугами),можна розглядати як граф.
Якщо в безлічі Г всі пари впорядковані, то такий граф називаютьорієнтованим.
Дуга-ребро орієнтованого графа.
Граф називається виродженим, якщо у нього немає ребер.
Вершина Х називається інцідентной ребру G, якщо ребро з'єднує цювершину з будь-якою іншою вершиною.
Подграфом G (V1, E1) графа G (V, E) називається граф з безліччю вершин V1? Vі безліччю ребер (дуг) E1? E, - такими, що кожне ребро (дуга) з E1інцідентно (інцідентна) тільки вершин з V1. Інакше кажучи, подграфмістить деякі вершини вихідного графа і деякі ребра (тільки ті,обидва кінці яких входять до подграф).
Подграфом, породжених безліччю вершин U називається подграф, безлічвершин якого - U, що містить ті і тільки ті ребра, обидва кінці якихвходять до U.
Подграф називається остовне подграфом, якщо безліч його вершин збігаєтьсяз безліччю вершин самого графа.
Вершини називаються суміжними, якщо існує ребро, що з'єднує їх.
Два ребра G1 і G2 називаються суміжними, якщо існує вершина, інцідентнаяодночасно G1 і G2.
Кожен граф можна представити у просторі безліччю точок,відповідних вершин, які з'єднані лініями, відповіднимиребер (чи дуг - в останньому випадку напрямок зазвичай вказуєтьсястрілками). - Таке подання називається укладанням графа.
Доведено, що в 3-мірному просторі будь-який граф можна представити у виглядіукладання таким чином, що лінії, що відповідають ребер (дуг) не будутьперетинатися у внутрішніх точках. Для 2-мірного простору це, взагалікажучи, неправильно. Що допускають представлення у вигляді укладання в 2-мірномупросторі графи називають плоскими (планарним).
Іншими словами, планарним називається граф, який може бути зображенийна площині так, що його ребра не будуть перетинатися.
Гранню графа, зображеного на деякій поверхні, називається частинаповерхні, обмежена ребрами графа.
Дане поняття межі, по - суті, збігається з поняттям межібагатогранника. В якості поверхні в цьому випадку виступає поверхнюбагатогранника. Якщо багатогранник опуклий, його можна зобразити наплощині, зберігши всі межі. Це можна наочно представити такимчином: одну з граней багатогранника розтягуємо, а сам багатогранник
«Розплющувати» так, щоб він весь помістився всередині цієї грані. Урезультаті отримаємо плоский граф. Грань, яку ми розтягували «зникне»,але їй буде відповідати грань, що складається з частини площини,обмежує граф.
Таким чином, можна говорити про вершини, ребрах і граняхбагатогранника, а оперувати відповідними поняттями для плоского графа.
Порожнім називається граф без ребер. Повним називається граф, в якому кожнідві вершини суміжні.
Кінцева послідовність необов'язково різних ребер E1, E2, ... Enназивається маршрутом довжини n, якщо існує послідовність V1, V2,
... Vn необов'язково різних вершин, таких, що Ei = (Vi-1, Vi).
Якщо збігаються, то маршрут замкнутий.
Маршрут, в якому всі ребра попарно різні, називається ланцюгом.
Замкнене маршрут, всі ребра якого різні, називається циклом. Якщо всевершини ланцюга або циклу різні, то така ланцюг або цикл називаютьсяпростими.
Маршрут, в якому всі вершини попарно різні, називається простий ланцюгом.
Цикл, в якому всі вершини, окрім першої і останньої, попарно різні,називається простим циклом.
Граф називається зв'язковим, якщо для будь-яких двох вершин існує шлях,з'єднує ці вершини.
Будь-який максимальний зв'язний подграф (тобто, не міститься в іншихзв'язкових подграфах) графа G називається компонентою зв'язності. Незв'язних графмає, принаймні, два компоненти зв'язності.
Граф називається k - зв'язковим (k - реберно - зв'язковим), якщо видалення не меншеk вершин (ребер) призводить до втрати властивості зв'язності.
Маршрут, що містить всі вершини або ребра графа і що володіє певнимивластивостями, називається обходом графа.
Довжина маршруту (ланцюги, простий ланцюга) дорівнює кількості ребер а порядок їхпроходження. Довжина найкоротшою простий ланцюга, що з'єднує вершини vi і vj вграфі G, називається відстанню d (vi, vj) між vi і vj.
Ступінь вершини - число ребер, яким інцідентна вершина V, позначається
D (V).
За допомогою різних операцій можна будувати графи з більш простих,переходити від графа до простішої, розбивати графи на більш прості іт.д.
Серед одномісних операцій найбільш споживані: видалення ідодавання ребра або вершини, стягання ребра (ототожнення пари суміжнихвершин), подразбіеніе ребра (тобто заміна ребра (u, v) на пару (u, w), (w,v), де w - нова вершина) і ін
Відомі двомісні операції: з'єднання, складання, різні видимножень графів та ін Такі операції використовуються для аналізу та синтезуграфів із заданими властивостями.
Два графа G1 = (V1, E1), G2 = (V2, E2), називаються ізоморфні, якщо існуєвзаімнооднозначное відповідність між множинами вершин V1 і V2 і міжмножинами ребер Е1 і Е2, таке, щоб зберігалося ставленняінцідентності.
Поняття ізоморфізму для графів має наочне тлумачення.
Уявімо ребра графів еластичними нитками, що зв'язують вузли - вершини.
Тоді, ізоморфізм можна представити як переміщення вузлів і розтягуванняниток.
Теорема 1.
Нехай задано граф G = (V; E), де V - безліч вершин, E - безлічребер, тоді 2 [E] =? (V), тобто подвійну кількість ребер дорівнює суміступенів вершин.
Теорема 2. (Лемма про рукостискання)
У кінцевому графі число вершин непарного ступеня парне.
Теорема 3.
Граф зв'язок тоді і тільки тоді, коли безліч його вершин не можнарозбити на дві непустих підмножини так, щоб обидві граничні точки кожногоребра знаходилися в одному і тому ж множині.
Відстань між двома вершинами зв'язного графа називаєтьсядовжина найкоротшої ланцюга, що зв'язує ці вершини (в кількості ребер).
Властивості зв'язкових графів.
1. Зв'язний граф залишається зв'язковим після видалення ребра тоді і тільки тоді, коли це ребро міститься в циклі.
2. Зв'язний граф, що має До вершин, містить принаймні К-1 ребро.
3. У зв'язкового графі будь-які дві прості ланцюги максимальної довжини має принаймні одну спільну вершину.
4. У графі з N вершинами і К компонентами зв'язності число ребер не перевищує 1/2 (NK) (N-K +1).
5. Нехай у графа G є N вершин. Нехай D (G) - мінімальна зі ступенів вершин цього графа. Тоді D (G)> 1/2 (N-1).
Зв'язковий граф без циклів називається деревом.
Дерева особливо часто виникають на практиці при зображеннірізних ієрархій. Наприклад, популярні генеалогічні дерева.
Приклад (генеалогічне дерево): На малюнку показано біблійнегенеалогічне дерево.
Еквівалентні визначення дерева.
1. Зв'язний граф називається деревом, якщо він не має циклів.
2. Містить N-1 ребро і не має циклів.
3. Зв'язний і містить N-1 ребро.
4. Зв'язний і видалення одного будь-якого ребра робить його незв'язних.
5. Будь-яка пара вершин сполучається єдиною ланцюгом.
6. Не має циклів і додавання одного ребра між будь-якими двома вершинами призводить до появи одного і тільки одного циклу.
1
Розфарбування графів
розфарбуванням графа G = (V , E) називається відображення D: V (N. Розмальовканазивається правильною, якщо образи будь-яких двох суміжних вершин різні: D
(U)? D (V), якщо (U, V) (I. хроматичним числом графа називаєтьсямінімальна кількість фарб, необхідне для правильної розфарбування графа.
Теорема 5.
Граф є планарним тоді і тільки тоді, коли він не міститьподграфа, ізоморфно одному з наступних (графи Понтрягина -
Куратовского).
Граф К33
Граф К5
Властивість: У будь-якому планарним графі існує вершина, ступінькоторойявляетсяорієнтованим графом, | V | = n, | E | = m. З метою спрощення викладу іуникнення вироджених випадків при оцінці складності алгоритмів будемовиключати ситуації, за яких «більшість» вершин ізольовані.
Будемо також припускати, що ваги дуг запам'ятовуються в масиві A [u,v], u, v? V (A [u, v] містить вага a (u, v )).
Найкоротші шляхи від фіксованої вершини
Більшість відомих алгоритмів знаходження відстані між двомафіксованими вершинами s і t спирається на дії, які в загальнихрисах можна представити в такий спосіб: при даній матриці ваг дуг
A [u, v], u, v? V, обчислюються деякі верхні обмеження D [v] навідстані від s до всіх вершин v? V. Кожного разу, коли ми встановлюємо,що
D [u] + A [u, v] Процес переривається, коли подальше поліпшення жодного зобмежень неможливо.
Легко можна показати, що значення кожної з змінних D [v] однотоді d (s, v) - відстані від s до v.
Зауважимо, що для того щоб визначити відстань від s до t, миобчислюємо тут відстані від s до всіх вершин графа.
Не відомий жоден алгоритм знаходження відстані між двомафіксованими вершинами, який був би істотно більшеефективним, ніж відомі алгоритми визначення відстані відфіксованої вершини до всіх інших.
Описана загальна схема є неповною, оскільки вона не визначаєчерговості, в якій вибираються вершини u і v для перевірки умовимінімальності відстані. Ця черговості, як буде показано нижче, дужесильно впливає на ефективність алгоритму. Опишемо тепер більш детальнометоди знаходження відстані від фіксованої вершини, званоїджерелом, його завжди будемо позначати через s, до всіх інших вершинграфа.
Спочатку наведемо алгоритм для загального випадку, в якомупередбачається тільки відсутність контурів з негативною завдовжки. З ціалгоритмом звичайно пов'язані імена Л.Р. Форда і Р.Е. Беллмана.
3. Програма визначення найкоротшого шляху в графі
1 3.1. Мова програмування Delphi.
Delphi - мова і середовище програмування, що відноситься до класу RAD-
(Rapid Application Development - «Засіб швидкої розробки додатків»)коштів CASE - технології. Delphi зробила розробку потужних додатків
Windows швидким процесом, що приносять вам задоволення. Програми
Windows, для створення яких потрібно було багато людськихзусиль наприклад в С + +, тепер можуть бути написані однією людиною,використовують Delphi.
Інтерфейс Windows забезпечує повне перенесення CASE-технологій уінтегровану систему підтримки робіт зі створення прикладної системи навсіх фазах життєвого циклу роботи та проектування системи.
Delphi має широкий набір можливостей, починаючи відпроектувальника форм і закінчуючи підтримкою всіх форматів популярних базданих. Середа усуває необхідність програмувати такі компоненти
Windows загального призначення, як мітки, піктограми і навіть діалогові панелі.
Працюючи в Windows, ви неодноразово бачили однакові «об'єкти» у багатьохрізноманітних програмах. Діалогові панелі (наприклад Choose File і Save
File) є прикладами багаторазово використовуваних компонентів, вбудованихбезпосередньо в Delphi, що дозволяє пристосувати ці компоненти донаявний завдання, щоб вони працювали саме так, як потрібно створюваномудодатком. Також тут є заздалегідь певні візуальні і невізуальні об'єкти, включаючи кнопки, об'єкти з даними, меню і вжепобудовані діалогові панелі. За допомогою цих об'єктів можна, наприклад,забезпечити введення даних просто кількома натисканням кнопок миші, невдаючись до програмування. Це наочна реалізація застосувань CASE -технологій в сучасному програмуванні додатків. Та частина, якабезпосередньо пов'язана з програмуванням інтерфейсу користувачасистемою отримала назву візуальне програмування
Візуальне програмування як би додає новий вимір пристворення створення додатків, даючи можливість зображати ці об'єкти наекрані монітора до виконання самої програми. Без візуальногопрограмування процес відображення вимагає написання фрагменту коду,що створює і настав об'єкт «за місцем». Побачити закодовані об'єктибуло можливо тільки в ході виконання програми. При такому підходідосягнення того, щоб об'єкти виглядали і поводилися заданим чином,стає втомливим процесом, який вимагає неодноразовихвиправлень програмного коду з наступною прогонкою програми іспостереження за тим, що в підсумку вийшло.
Завдяки засобам візуальної розробки можна працювати з об'єктами,тримаючи їх перед очима й одержуючи результати практично відразу. Здатністьбачити об'єкти такими, якими вони з'являються в ході виконання програми,знімає необхідність проведення безлічі операцій вручну, що характернодля роботи в середовищі не володіє візуальними засобами - незалежновід того, є вона об'єктно-орієнтованої чи ні. Після того, якоб'єкт поміщений у форму середовища візуального програмування, всі його атрибутивідразу відображаються у вигляді коду, який відповідає об'єкту як одиниці,що виконується під час роботи програми.
Розміщення об'єктів у Delphi пов'язано з більш тісними стосункамиміж об'єктами та реальним програмним кодом. Об'єкти поміщаються у вашуформу, при цьому код, який відповідає об'єктам, автоматично записується ввихідний файл. Цей код компілюється, забезпечуючи істотно більшевисоку продуктивність, ніж візуальне середовище, яка інтерпретуєінформацію лише в ході виконання програми.
1 3.2. Програма «Визначення найкоротшого шляху в графі"
Програма «Визначення найкоротшого шляху в графі" розроблена в середовищі
«Delphi», працює під ОС «Windows» -95,98,2000, NT.
Програма дозволяє вводити, редагувати, зберігати графи в файл,завантажувати з файлу. Також реалізований алгоритм знаходження найкоротшого шляху.
Інтерфейс програми має такий вигляд:
Верхня панель кнопок призначена для редагування графа.
Кнопка «Завантажити» призначена для завантаження ранішезбереженого графа з файлу.
Кнопка «Зберегти» призначена для збереження графа в файл.
Кнопка «Перемістити» призначена для переміщення вершинграфа.
Кнопка «Видалити» призначена для видалення вершин графа.
При натисканні на кнопку «Новий» робоче поле програми будеочищено і з'явиться можливість введення нового графа.
Кнопка «Допомога» викликає допомогу програми.
Для очищення результатів роботи алгоритму визначення найкоротшого шляхуу графі необхідно натиснути кнопку «Оновити».
При натисканні на кнопку «Налаштування» на екрані з'явиться вікно, вякому можна налаштувати параметри сітки робочого поля програми і кольорувводиться графа.
Вікно налаштувань виглядає наступним чином:
Нижня панель кнопок призначена для установки параметрів введення тазапуску алгоритму визначення найкоротшого шляху в графі. Дана панельскладається з чотирьох кнопок:
Коли кнопці «Показувати сітку» відображається сітка длязручності введення вершин.
Для автоматичного введення довжини ребра графа необхідно натиснути кнопку
.
Коли кнопці «Вирівнювати по сітці» нові вершинибудуть автоматично вирівнюватись по координатної сітки.
Якщо вибрати дві різні вершини (клацанням лівої кнопки миші) і натиснути на кнопку, то програма знайде найкоротший шлях між вершинами.
Алгоритм визначення найкоротшого шляху між вершинами графа описанийнаступним модулем програми:
unit MinLength;
interface
uses
Windows, Messages, SysUtils, Classes, Graphics, Controls, Dialogs ,
StdCtrls, IO, Data, AbstractAlgorithmUnit; type
TMinLength = class (TAbstractAlgorithm) private
StartPoint: integer;
EndPoint : integer;
First: Boolean;
Lymbda: array of integer; function Proverka: Boolean; public procedure Make; end;
var
MyMinLength: TMinLength; implementation
uses MainUnit, Setting; procedure TMinLength.Make; var i, j: integer;
PathPlace, TempPoint: Integer; flag: boolean; begin with MyData do begin
StartPoint: = MyIO.FirstPoint;
EndPoint: = MyIO.LastPoint;
SetLength (Lymbda, Dimension +1);
SetLength (Path, Dimension +1); for i: = 1 to Dimension do
Lymbda [i]: = 100000;
Lymbda [StartPoint]: = 0; repeat for i: = 1 to Dimension do for j: = 1 to Dimension do if Matrix [i, j] = 1 then if ((Lymbda [j]-Lymbda [i])>
MatrixLength [j, i]) then Lymbda [j]: = Lymbda [i] + MatrixLength [j, i]; until Proverka;
Path [1]: = EndPoint; j: = 1;
PathPlace: = 2; repeat
TempPoint: = 1;
Flag: = False; repeat if (Matrix [Path [PathPlace-1], TempPoint] = 1) and (
Lymbda [Path [PathPlace-1]] =
(Lymbda [TempPoint] + MatrixLength [Path [PathPlace-
1], TempPoint])) then Flag: = True else Inc (TempPoint); until Flag;
Path [PathPlace]: = TempPoint; inc (PathPlace);
MyIO. DrawPath (Path [PathPlace-2], Path [PathPlace
-1], True);
// ShowMessage ( 'f'); until (Path [PathPlace - 1] = StartPoint);
// MyIO.DrawPath (Path [ PathPlace-1], Path [PathPlace
], true); end; end; function TMinLength.Proverka: Boolean; var i, j: integer;
Flag: boolean; begin i: = 1;
Flag: = False;
WithMyData do begin repeat j: = 1; repeat if Matrix [i, j] = 1 then if (Lymbda [j]-Lymbda [i])> MatrixLength [j, i] then
Flag: = True; inc (j); until (j> Dimension) or (Flag); inc (i); until (i> Dimension) or (Flag);
Result: = not Flag; end; end;
end.
Робоче поле програми призначено для візуального введення графів.
Робоче поле з введеним графом виглядає наступним чином: < p>
ВИСНОВОК
Теорія графів знаходить широке застосування в різних галузях науки ітехніки:
Графи та інформація
Двійкові дерева відіграють дуже важливу роль в теорії інформації.
Припустимо, що певна кількість повідомлень потрібно закодувати у виглядікінцевих послідовностей різної довжини, що складаються з нулів та одиниць.
Якщо ймовірності кодових слів задані, то найкращим вважається код, в якомусередня довжина слів мінімальна в порівнянні з іншими розподіламиймовірності. Завдання про побудову такого оптимального коду дозволяє вирішитиалгоритм Хаффмана.
Двійкові кодові дерева допускають інтерпретацію в рамках теоріїпошуку. Кожній вершині при цьому зіставляється питання, відповісти на якийможна або "так", або "ні". Ствердно і негативної відповідівідповідають два ребра, що виходять з вершини. "Опитування" завершується, коливдається встановити те, що було потрібно.
Таким чином, якщо комусь знадобиться взяти інтерв'ю в різнихлюдей, і відповідь на чергове запитання буде залежати від заздалегідь невідомоговідповіді на попереднє питання, то план такого інтерв'ю можна представити уяк двійкові дерева.
Графи і хімія
Ще А. Келі розглянув задачу про можливі структурах насичених (абограничних) вуглеводнів, молекули яких задаються формулою:
CnH2n 2
Молекула кожного граничного вуглеводню являє собою дерево.
Якщо видалити всі атоми водню, то що залишилися атоми вуглеводню такожбудуть утворювати дерево, кожна вершина якого має ступінь не вище 4.
Отже, число можливих структур граничних вуглеводнів, тобточисло гомологів даного речовини, що дорівнює числу дерев з вершинами ступеняне більше чотирьох.
Таким чином, підрахунок числа гомологів граничних вуглеводнів такожпризводить до задачі про перерахування дерев певного типу. Це завдання іїї узагальнення розглянув Д. Пойа.
Графи і біологія
Дерева відіграють велику роль у біологічній теорії розгалуженихпроцесів. Для простоти ми розглянемо тільки один різновид розгалуженихпроцесів - розмноження бактерій. Припустимо, що через певнийпроміжок часу кожна бактерія або ділиться на дві нові, абогине. Тоді для потомства однієї бактерії ми отримаємо двійкове дерево.
Нас буде цікавити лише одне питання: у скількох випадках n-епокоління однієї бактерії нараховує рівно k нащадків? Рекурентніспіввідношення, що позначає число необхідних випадків, відоме в біологіїпід назвою процесу Гальтона-Ватсона. Його можна розглядати якокремий випадок багатьох загальних формул.
Графи і фізика
Ще недавно однією з найбільш складних і утомливих завдань длярадіоаматорів було конструювання друкованих схем.
Друкованої схемою наз
