1 Уилсон р. Введение в теорию графов. – м.: Мир, 1977.

Одной из первых задач, приведших к возникновению теории графов, является известная «задача о коммивояжере». Решение этой задачи естественно привело к определению важного класса графов, называемых гамильтоновыми. Цель контрольной работы - изучить основные свойства гамильтоновых графов и рассмотреть практические задачи, сводящиеся к задаче о коммивояжере. Рекомендуется следующий план работы:

1) Изучить такие основополагающие понятия теории графов, как граф, маршрут и цепь, контур и цикл (/1/, с. 9-43; /2/, с. 14-18).

2) Рассмотреть понятие гамильтонова цикла, ввести определение гамильтонова графа и доказать теорему Дирака о таких графах (/1/, с. 48-51; /2/, с. 168-173).

3) Разобрать задачу о коммивояжере и примеры конкретных практических задач, приводящих к этой задаче (/2/, с. 179-182).

4) Изучить метод ветвей и границ, разобрать точный алгоритм решения задачи о коммивояжере на стр. 182-197 в /2/.

Литература, рекомендуемая для изучения темы