Алгоритм Дейкстра, Детальна інформація

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

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

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

Зміст

1.Вступ…………………………………………………………………………………..…………3

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

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

Ізоморфізм, гомеоморфізм……………………………………………………….…………4

Шляхи і цикли…………………………………………………………………….…………5

Дерева………………………………………………………………………………………..5

Цикломатичне число і фундаментальні цикли……………….……….…………………..8

Компланарні графи ………………………………………………………………..……….8

Розфарбування графів………………………………………………………………….….10

Графи з атрибутами ……………………………………………………………….………12

Незалежні безлічі і покриття ………………………………………………………..……12

3.Задача знаходження мінімального шляху в графах:

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

Текст програми написаної на основі алгоритму Дейкстра………………………..…….15

Результат виконання програми…………………………………………………………...17

Графічне зображення початкового графа та дерево мінімальних шляхів після виконання рограми……………………………………………………………….……..…18

4.Висновок………………………..……..……………………………………………………….18

5. HYPERLINK "http://www.caravan.ru/~alexch/graphs/" \l "Литература" Література ………………………………………………………………………..…….……..19





1. Вступ

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

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

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

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

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