| Головна » Статті » Математика | [ Додати статтю ] |
Алгоритм Дейкстра - реферат українською
|
Зміст 1.Вступ…………………………………………………………………………………..…………3 2.Елементи теорії графів: Основні визначення……………………………………………………………..…………..3 Ізоморфізм, гомеоморфізм……………………………………………………….…………4 Шляхи і цикли…………………………………………………………………….…………5 Дерева………………………………………………………………………………………..5 Цикломатичне число і фундаментальні цикли……………….……….…………………..8 Компланарні графи ………………………………………………………………..……….8 Розфарбування графів………………………………………………………………….….10 Графи з атрибутами ……………………………………………………………….………12 Незалежні безлічі і покриття ………………………………………………………..……12 3.Задача знаходження мінімального шляху в графах: Алгоритм Дейкстра…………………………………………………………….….………14 Текст програми написаної на основі алгоритму Дейкстра………………………..…….15 Результат виконання програми…………………………………………………………...17 Графічне зображення початкового графа та дерево мінімальних шляхів після виконання рограми……………………………………………………………….……..…18 4.Висновок………………………..……..……………………………………………………….18 5. Література ………………………………………………………………………..…….……..19 1. Вступ Останнім часом дослідження в областях, що традиційно відносяться до дискретної математики, займають усе більш помітне місце. Поряд з такими класичними розділами математики, як математичний аналіз, диференціальні рівняння, у навчальних планах спеціальності "Прикладна математика" і багатьох інших спеціальностей з'явилися розділи по математичній логіці, алгебрі, комбінаториці і теорії графів. Причини цього неважко зрозуміти, просто розглянувши задачу, розв'язувану пошуку найкоротшого шляху в графі . 2. Елементи теорії графів Основні визначення Граф (graph) - пари G=(V,E), де V - безліч об'єктів довільної природи, називаних вершинами (vertices, nodes), а E - сімейство пар ei=(vi1, vi2), vijV, називаних ребрами (edges). У загальному випадку безліч V і/чи сімейство E можуть містити нескінченне число елементів, але ми будемо розглядати тільки кінцеві графи, тобто графи, у яких як V, так і E кінцеві. У приведеному визначенні графа E не випадково названо сімейством пар, а не безліччю. Справа в тім, що елементи E можуть бути не унікальні, тобто можливі кратні ребра. Існує інше, більш коректне визначення: граф визначається як трійка G=(V,E,), де V - безліч вершин, E - безліч ребер, а =(v,u,e) - тримісний предикат (булевська функція від трьох перемінних), що повертає True тоді і тільки тоді, коли ребро e інцидентне вершинам v і u. Однак такі "строгості" у нашому викладі є надмірними. Якщо порядок елементів, що входять у ei, має значення, то граф називається орієнтованим (directed graph), скорочено - орграф (digraph), інакше - неорієнтованим (undirected graph). Ребра орграфа називаються дугами (arcs). Надалі будемо вважати, що термін "граф", застосовуваний без уточнень "орієнтований" чи "неорієнтований", позначає неорієнтований граф. Приклад: G=(V,E); V={1,2,3,4}; E= G Якщо e=(v,u), те вершини v і u називаються кінцями ребра. При цьому говорять, що ребро e є суміжним (інцидентним) кожної з вершин v і u. Вершини v і u також називаються суміжними (інцидентними). У загальному випадку, допускаються ребра виду e=(v,v); такі ребра називаються петлями. Ступінь вершини графа - це число ребер, інцидентних даній вершині, причому петлі враховуються двічі. Оскільки кожне ребро інцидентне двом вершинам, сума ступенів усіх вершин графа дорівнює подвоєній кількості ребер: Sum(deg(vi), i=1..|V|)=2|E|. Граф, що не містить петель і кратних ребер, називається звичайним, чи простим графом (simple graph). У багатьох публікаціях використовується інша термінологія: під графом розуміється простий граф, граф із кратними ребрами називають мультиграфом, з петлями - псевдографом. Деякі класи графів одержали особливі найменування. Граф з будь-якою кількістю вершин, не утримуючих ребер, називається порожнім. Звичайний граф з n вершинами, будь-яка пара вершин якого з'єднана ребром, називається повним і позначається Kn (очевидно, що в повному графі n(n-1)/2 ребер). Граф, вершини якого можна розбити на непересічні підмножини V1 і V2 так, що ніякі дві вершини, що належать тому самому підмножині, не суміжні, називається двочастковим (чи біхроматичним, чи графом Кенига) і позначається Bmn (m=|V1|, n=|V2|, m+n=|V|). Повний двочастковий граф - такий двочастковий граф, що кожна вершина безлічі V1 зв'язана з усіма вершинами безлічі V2, і навпаки; позначення - Kmn. Зауваження: повний двочастковий граф Bmn не є повним (за винятком B11=K2). B33 Підграфом, чи частиною графа G=(V,E) називається такий граф G'=(V',E'), що V'V і дві несуміжні вершини в G не суміжні в G'. Повним підграфом називається підграф, будь-яка пара вершин якого суміжна. Основним підграфом (суграфом) графа G називається будь-який його підграф, що містить ту ж безліч вершин, що і G. Ізоморфізм, гомеоморфізм | |
| Переглядів: 525 | |
| Всього коментарів: 0 | |