Что такое гамильтонов граф: определение термина
Гамильтонов граф называют так, если в нем существует гамильтонов цикл. Это замкнутый путь, который проходит через каждую вершину графа ровно один раз, а затем возвращается в начальную вершину.
Важно не путать его с эйлеровым циклом: там проходят по ребрам, а здесь главное — вершины. Если такой цикл есть, граф гамильтонов. Если можно пройти по всем вершинам по одному разу, но возвращаться в начало не нужно, это называют гамильтоновым путем.
Зачем нужны гамильтоновы графы
Гамильтоновы графы важны в задачах на маршруты и планирование. Самый известный пример связан с задачей коммивояжера: нужно посетить все пункты по одному разу и вернуться обратно, стараясь сделать путь коротким.
Похожие идеи используют в логистике, составлении расписаний, проектировании маршрутов роботов и в компьютерных сетях. При этом не всегда легко определить, является ли граф гамильтоновым, поэтому в математике изучают признаки, которые помогают это узнать.
