2. Гамильтоновы графы.

Гамильтоновы графы можно рассматривать как многоугольники, некоторые вершины которых соединены диагоналями, так, что из любой

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

1) Определить основные понятия теории графов (граф, связность, маршруты, цикл, обхват и т.п.), проиллюстрировать их на примерах и привести образцы задач, сводящихся к выяснению тех или иных свойств графов (/1/, с. 9 – 24; /2/, с. 6 – 16).

2) Дать определение гамильтонова и полугамильтонова графов, привести примеры (/1/, с. 48 – 50; /2/, с. 44 – 48). Решить ряд упражнений из литературы /1/, /2/. 3 Доказать теорему Дирака о достаточных условиях для гамильтоновости графа (/1/, c. 48 – 51).

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