Алгоритм Дейкстра, Детальна інформація
Алгоритм Дейкстра
Курсова робота
З дисципліни” Основи дискретної математики”
На тему: Алгоритм Дейкстра
Зміст
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. Однак такі "строгості" у нашому викладі є надмірними.
З дисципліни” Основи дискретної математики”
На тему: Алгоритм Дейкстра
Зміст
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. Однак такі "строгості" у нашому викладі є надмірними.
The online video editor trusted by teams to make professional video in
minutes
© Referats, Inc · All rights reserved 2021