Алгоритм Дейкстра

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

З дисципліни”Основи дискретної математики”

На тему: Алгоритм Дейкстра

Зміст

1. Вступ

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

2. Елементи теорії графів

Основні визначення

Граф (graph) - пари G=(V,E), де V - безліч об'єктів довільної природи, називаних вершинами (vertices, nodes), а E - сімейство пар e_i =(v_i1 , v_i2 ), v_ij V, називаних ребрами (edges). У загальному випадку безліч V і/чи сімейство E можуть містити нескінченне число елементів, але ми будемо розглядати тільки кінцеві графи , тобто графи, у яких як V, так і E кінцеві.

У приведеному визначенні графа E не випадково названо сімейством пар, а не безліччю. Справа в тім, що елементи E можуть бути не унікальні, тобто можливі кратні ребра . Існує інше, більш коректне визначення: граф визначається як трійка G=(V,E,), де V - безліч вершин, E - безліч ребер, а =(v,u,e) - тримісний предикат (булевська функція від трьох перемінних), що повертає True тоді і тільки тоді, коли ребро e інцидентне вершинам v і u. Однак такі "строгості" у нашому викладі є надмірними.

Якщо порядок елементів, що входять у e_i , має значення, то граф називається орієнтованим (directed graph), скорочено - орграф (digraph), інакше - неорієнтованим (undirected graph). Ребра орграфа називаються дугами (arcs). Надалі будемо вважати, що термін "граф", застосовуваний без уточнень "орієнтований" чи "неорієнтований", позначає неорієнтований граф.

Приклад: G=(V,E); V={1,2,3,4}; E=<(1,1), (1,2), (1,3), (2,4), (2,4)>

G
Якщо e=(v,u), те вершини v і u називаються кінцями ребра . При цьому говорять, що ребро e є суміжним (інцидентним ) кожної з вершин v і u. Вершини v і u також називаються суміжними (інцидентними). У загальному випадку, допускаються ребра виду e=(v,v); такі ребра називаються петлями .

Ступінь вершини графа - це число ребер, інцидентних даній вершині, причому петлі враховуються двічі. Оскільки кожне ребро інцидентне двом вершинам, сума ступенів усіх вершин графа дорівнює подвоєній кількості ребер: Sum(deg(v_i ), i=1..|V|)=2|E|.

Граф, що не містить петель і кратних ребер, називається звичайним , чи простим графом (simple graph). У багатьох публікаціях використовується інша термінологія: під графом розуміється простий граф, граф із кратними ребрами називають мультиграфом , з петлями - псевдографом .

Деякі класи графів одержали особливі найменування. Граф з будь-якою кількістю вершин, не утримуючих ребер, називається порожнім . Звичайний граф з n вершинами, будь-яка пара вершин якого з'єднана ребром, називається повним і позначається K_n (очевидно, що в повному графі n(n-1)/2 ребер).

Граф, вершини якого можна розбити на непересічні підмножини V₁ і V₂ так, що ніякі дві вершини, що належать тому самому підмножині, не суміжні, називається двочастковим (чи біхроматичним, чи графом Кенига) і позначається B_mn (m=|V₁ |, n=|V₂ |, m+n=|V|). Повний двочастковий граф - такий двочастковий граф, що кожна вершина безлічі V₁ зв'язана з усіма вершинами безлічі V₂ , і навпаки; позначення - K_mn . Зауваження: повний двочастковий граф B_mn не є повним (за винятком B₁₁ =K₂ ).

B₃₃

Підгра