- Главная
- Разное
- Образование
- Спорт
- Естествознание
- Природоведение
- Религиоведение
- Французский язык
- Черчение
- Английский язык
- Астрономия
- Алгебра
- Биология
- География
- Геометрия
- Детские презентации
- Информатика
- История
- Литература
- Математика
- Музыка
- МХК
- Немецкий язык
- ОБЖ
- Обществознание
- Окружающий мир
- Педагогика
- Русский язык
- Технология
- Физика
- Философия
- Химия
- Шаблоны, фоны, картинки для презентаций
- Экология
- Экономика
Презентация, доклад на тему Классические алгоритмы на графах
Содержание
- 1. Классические алгоритмы на графах
- 2. Граф — абстрактный математический объект, представляющий собой
- 3. Виды графовГрафы, в которых все рёбра являются
- 4. Алгоритм Дейкстры Алгоритм голландского ученого Эдсгера Дейкстры находит
- 5. Алгоритм Дейкстры
- 6. Алгоритм Краскала Алгоритм Краскала — эффективный алгоритм построения
- 7. Алгоритм Краскала
- 8. Алгоритм Прима Алгоритм Прима — это алгоритм поиска
- 9. Алгоритм Прима
- 10. Алгоритм Прима
Граф — абстрактный математический объект, представляющий собой множество вершин графа и набор рёбер( соединений между парами вершин).
Слайд 2 Граф — абстрактный математический объект, представляющий собой множество вершин графа и
набор рёбер( соединений между парами вершин).
Слайд 3Виды графов
Графы, в которых все рёбра являются звеньями (порядок двух концов
ребра графа не существенен), называются неориентированными.
Графы, в которых все рёбра являются дугами (порядок двух концов ребра графа существенен), называются ориентированными графами или орграфами
Графы, в которых все рёбра являются дугами (порядок двух концов ребра графа существенен), называются ориентированными графами или орграфами
Слайд 4Алгоритм Дейкстры
Алгоритм голландского ученого Эдсгера Дейкстры находит все кратчайшие пути из
одной изначально заданной вершины графа до всех остальных.
Минусом данного метода является невозможность обработки графов, в которых имеются ребра с отрицательным весом.
Минусом данного метода является невозможность обработки графов, в которых имеются ребра с отрицательным весом.
Слайд 6Алгоритм Краскала
Алгоритм Краскала — эффективный алгоритм построения минимального остовного дерева взвешенного
связного неориентированного графа. Также алгоритм используется для нахождения некоторых приближений для задачи Штейнера. Алгоритм впервые описан Джозефом Крускалом в 1956 году.
Слайд 8Алгоритм Прима
Алгоритм Прима — это алгоритм поиска минимального остовного дерева в
связном графе. С помощью алгоритма Прима можно выделить только те ребра графа, с помощью которых можно соединить каждую из вершин этого графа и при этом суммарная стоимость этих ребер будет минимальна.
