Динамическое программирование, алгоритмы на графах

Содержание

Введение

1. Алгоритмы, использующие решение дополнительных подзадач

2. Основные определения теории графов

3. Поиск пути между парой вершин невзвешенного графа

4. Пути минимальной длины во взвешенном графе

Заключение

Литература

Введение

Существует целый класс задач по программированию, которые проще решаются, если ученик владеет определенным набором знаний, умений и навыков в области алгоритмов на графах. Это происходит потому, что такие задачи могут быть переформулированы в терминах теории графов.

Теория графов содержит огромное количество определений, теорем и алгоритмов. И поэтому данный материал не может претендовать, и не претендует, на полноту охвата материала. Однако, по мнению автора, предлагаемые сведения являются хорошим компромиссом между объемом материала и его "коэффициентом полезного действия" в практическом программировании и решении олимпиадных задач.

Иногда решение основной задачи приходится формулировать в терминах несколько модифицированных подзадач. Именно такие проблемы рассматриваются в данной работе.

1. Алгоритмы, использующие решение дополнительных подзадач

Задача 9. Требуется подсчитать количество различных разбиений числа N на натуральные слагаемые. Два разложения считаются различными, если одно нельзя получить из другого путем перестановки слагаемых.