Вопросы для самоконтроля

1. Какой цикл в графе называется эйлеровым? Что такое полуэйлеров граф?

2. Какие условия существования эйлерова цикла в графе?

3. Что такое гамильтонов цикл в графе?

4. Существуют ли условия, позволяющие однозначно определить наличие гамильтонова цикла в произвольном связном графе?

5. В чем заключается основная идея алгоритма Флери?

6. Что такое граф подразбиений?

7. Какой граф называется тотальным?

8. В каком случае ребра и вершины графа называются соседними?

9. Поясните понятие жордановой кривой?

10. Что такое замкнутая жорданова кривая?

ЗАДАНИЯ ДЛЯ САМОСТОЯТЕЛЬНОЙ РАБОТЫ

1. Для произвольного неориентированного графа определите, можно ли построить в этом графе эйлеров цикл.

2. Для произвольного связного неориентированного графа постройте с помощью алгоритма Флери эйлеров цикл.

3. Постройте структурную схему алгоритма Флери для построения эйлерова цикла.

4. Запишите псевдокод алгоритма Флери.

5. Приведите пример графа подразбиений.

6. Составьте описание алгоритма построения реберных графов.

7. Приведите псевдокод алгоритма построения реберных графов.

8. Приведите пример тотального графа.

9. Приведите пример связи эйлеровых и гамильтоновых графов словесное описание алгебраического метода.

10. Приведите пример построения гамильтонова псевдоцикла.

 

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

Связь между эйлеровыми и гамильтоновыми графами позволяет строить модели и производить преобразования для построения эффективных алгоритмов.