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

Зміст

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

5. Література ………………………………………………………………………..…….……..19

1. Вступ

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

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

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