найти маршрут, который содержит все вершины или ребра графа
– обход.Часто требуется, чтобы длина этого маршрута была минимальной (для взвешенных графов), или ограничивается число проходов по одному и тому же элементу графа.
- Главная
- Разное
- Бизнес и предпринимательство
- Образование
- Развлечения
- Государство
- Спорт
- Графика
- Культурология
- Еда и кулинария
- Лингвистика
- Религиоведение
- Черчение
- Физкультура
- ИЗО
- Психология
- Социология
- Английский язык
- Астрономия
- Алгебра
- Биология
- География
- Геометрия
- Детские презентации
- Информатика
- История
- Литература
- Маркетинг
- Математика
- Медицина
- Менеджмент
- Музыка
- МХК
- Немецкий язык
- ОБЖ
- Обществознание
- Окружающий мир
- Педагогика
- Русский язык
- Технология
- Физика
- Философия
- Химия
- Шаблоны, картинки для презентаций
- Экология
- Экономика
- Юриспруденция
Что такое findslide.org?
FindSlide.org - это сайт презентаций, докладов, шаблонов в формате PowerPoint.
Обратная связь
Email: Нажмите что бы посмотреть
Презентация на тему Обходы графов
Содержание
- 2. Существует ряд задач на графах, в которых
- 3. 3.1. Эйлеровы цепи и циклы
- 4. Определение. Эйлеровой цепью (циклом) называется цепь (цикл),
- 5. Теорема. Эйлерова цепь (цикл) существует тогда и
- 6.
- 7.
- 8.
- 9. На этом доказательстве основан алгоритм нахождения эйлеровой цепи.
- 10. Алгоритм
- 11.
- 12. 43430012232 Пример
- 13. Задача китайского почтальона В графе с неотрицательными весами
- 14. 3.1. Гамильтоновы цепи и циклы
- 15. Постановка задачи Определение. Гамильтоновой цепью (циклом) графа называется
- 16. Граф ГамильтонаДодекаэдр:12 граней, 20 вершин,30 реберГамильтонов циклВ 1859 г. Гамильтон изобрел голово- ломку обхода вер-шин додекаэдра
- 17. Мы рассмотрим два простейших переборных алгоритма поиска
- 18. Поиск в ширину 2 - бесперспективное (тупиковое ) множество вариантов- множество вариантов стоит исследовать глубжеДерево вариантов
- 19. Поиск в глубину 2 - прямой ход по дереву поиска- обратный ход (back tracking)
- 20. Задача коммивояжера Задача коммивояжера (travelling seller problem, TSP)
- 21.
- 22. Скачать презентацию
- 23. Похожие презентации
Существует ряд задач на графах, в которых требуется найти маршрут, который содержит все вершины или ребра графа – обход. Часто требуется, чтобы длина этого маршрута была минимальной (для взвешенных графов), или ограничивается число проходов по одному
Слайд 2 Существует ряд задач на графах, в которых требуется
Часто требуется, чтобы длина этого маршрута была минимальной (для взвешенных графов), или ограничивается число проходов по одному и тому же элементу графа.
Слайд 4 Определение. Эйлеровой цепью (циклом) называется цепь (цикл), содержащая
(содержащий) все ребра графа. Если в графе существует эйлерова
цепь (цикл), то граф называется эйлеровым.Эйлеров граф можно нарисовать одним росчерком пера.
5
3
3
3
3
3
4
2
Постановка задачи
Кенигсбергские мосты
Слайд 5
Теорема. Эйлерова цепь (цикл) существует тогда и только
тогда, когда число вершин с нечетной валентностью равно 2
(0).Теорема Эйлера (1736 г.)
Слайд 13
Задача китайского почтальона
В графе с неотрицательными весами ребер
найти циклический маршрут наименьшей длины, проходящий через каждое ребро
графа по крайней мере один раз.Почтальон называется китайским потому, что первоначально эту задачу изучал китайский математик Мэй-Ку Куан в 1962 году.
Очевидно, если граф эйлеров, то эйлеров цикл и будет оптимальным. Если граф не эйлеров, то задача становится весьма трудоемкой. Для ее решения имеются специальные алгоритмы, сокращающие число перебираемых вариантов.
Слайд 15
Постановка задачи
Определение. Гамильтоновой цепью (циклом) графа называется простая
цепь (простой цикл), содержащая (содержащий) все вершины графа.
Сэр Уильям
Роуэн Гамильтон
(1805-1865) – самый известный ирландский математик, один из лучших математиков 19 века. Известен фунда-ментальными открытиями в математике , механике , физике (векторный анализ, вариационное исчисление, общий прин-цип наименьшего действия в механике, теория распространения света и др.)
Слайд 16
Граф Гамильтона
Додекаэдр:
12 граней,
20 вершин,
30 ребер
Гамильтонов цикл
В 1859
г. Гамильтон изобрел голово- ломку обхода вер-шин додекаэдра
Слайд 17
Мы рассмотрим два простейших переборных алгоритма поиска гамильтоновой
цепи (цикла), пригодных для графов малой размерности: поиск в
ширину и поиск в глубину.
Слайд 18
Поиск в ширину
2
- бесперспективное (тупиковое ) множество вариантов
-
множество вариантов
стоит исследовать глубже
Дерево вариантов
Слайд 20
Задача коммивояжера
Задача коммивояжера (travelling seller problem, TSP) формулируется
следующим образом: во взвешенном графе (обычно – полном) найти
гамильтонову цепь (цикл) наименьшей длины (с наименьшим суммарным весом ребер). Название задачи происходит от следующей формулировки: имеется n городов и известны расстояния между каждой парой городов; коммивояжер (бродячий торговец), выходящий из какого-либо города, должен посетить n − 1 других городов и вернуться в исходный. В каком порядке ему нужно посещать города, чтобыобщее пройденное расстояние было минимальным?
