Гамильтонов цикл. Определение. Задача о коммивояжере.

Гамильтонов цикл - цикл который содержит в себе все вершины графа

Пример (путешествие по достопримечательностям в городе)

Условие существование – простой граф, связный граф, отсутствие листьев в графе.

7. Содержание

   • Графы. Основные определения. Соотношения между количеством ребер и количеством вершин.
   • Изоморфизм графов. Примеры.
   • Пути, цепи, циклы.
   • Связность графов.
   • Эйлеров цикл. Определение, условие существования, алгоритм нахождения.
   • Гамильтонов цикл. Определение. Задача о коммивояжере.
   • Деревья.
   • ОстОвное дерево. Алгоритм Крускала.
   • Алгоритм поиска кратчайшего пути в графе.
   • Клики. Алгоритм поиска клик.
   • Раскраска графов. Алгоритмы раскраски.
   • Генерация случайных графов.