Содержание
- 2. Существует ряд задач на графах, в которых требуется найти маршрут, который содержит все вершины или ребра
- 3. 3.1. Эйлеровы цепи и циклы
- 4. Определение. Эйлеровой цепью (циклом) называется цепь (цикл), содержащая (содержащий) все ребра графа. Если в графе существует
- 5. Теорема. Эйлерова цепь (цикл) существует тогда и только тогда, когда число вершин с нечетной валентностью равно
- 9. На этом доказательстве основан алгоритм нахождения эйлеровой цепи.
- 10. Алгоритм
- 12. 4 3 4 3 0 0 1 2 2 3 2 Пример
- 13. Задача китайского почтальона В графе с неотрицательными весами ребер найти циклический маршрут наименьшей длины, проходящий через
- 14. 3.1. Гамильтоновы цепи и циклы
- 15. Постановка задачи Определение. Гамильтоновой цепью (циклом) графа называется простая цепь (простой цикл), содержащая (содержащий) все вершины
- 16. Граф Гамильтона Додекаэдр: 12 граней, 20 вершин, 30 ребер Гамильтонов цикл В 1859 г. Гамильтон изобрел
- 17. Мы рассмотрим два простейших переборных алгоритма поиска гамильтоновой цепи (цикла), пригодных для графов малой размерности: поиск
- 18. Поиск в ширину 2 - бесперспективное (тупиковое ) множество вариантов - множество вариантов стоит исследовать глубже
- 19. Поиск в глубину 2 - прямой ход по дереву поиска - обратный ход (back tracking)
- 20. Задача коммивояжера Задача коммивояжера (travelling seller problem, TSP) формулируется следующим образом: во взвешенном графе (обычно –
- 23. Скачать презентацию