Теоретические сведения

Нахождение эйлерова и гамильтонова циклов

ЦЕЛЬ РАБОТЫ

6.1.1 Ознакомиться с теоретическими сведениями по теме «Классификация графов».

6.1.2 Получить практические навыки по нахождению Эйлерова и Гамильтонова циклов.

МЕТОДИЧЕСКИЕ РЕКОМЕНДАЦИИ

6.2.1 Методические указания по выполнению практической работы.

ПОРЯДОК ВЫПОЛНЕНИЯ РАБОТЫ

6.3.1 Изучить методические указания к практической работе.

6.3.2 В соответствии с полученным вариантом распознать следующие графы, определив:

· эйлеровость;

· гамильтоновость;

СОДЕРЖАНИЕ ОТЧЕТА

6.4.1 Цель работы

6.4.2 Методические рекомендации

6.4.3 Порядок выполнения работы

6.4.4 Ответы на контрольные вопросы

6.4.5 Выводы

КОНТРОЛЬНЫЕ ВОПРОСЫ

6.5.1 Что такое граф?

6.5.2 Дайте определение Эйлеровому графу?

6.5.3 Дайте определение Полуэйлеровому графу?

6.5.4 Дайте определение Гамильтонову графу?

6.5.5 Дайте определение Полугамильтонову графу?

ПРИЛОЖЕНИЕ 1

ТЕОРЕТИЧЕСКИЕ СВЕДЕНИЯ

Цепь – последовательность идущих друг за другом ребер.

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

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

 

Если граф имеет простой цикл, содержащий все вершины графа, то такой цикл называется Гамельтоновым.

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

 

Алгоритм Флёра

Для нахождения Эйлерового пути используется следующий алгоритм Флёра:

1. Начав движение из произвольной вершины, стираем ребра по мере их прохождения, а также стираем изолированные вершины, которые при этом образуются.

2. На каждом этапе идем по мосту только в том случае, когда не других возможностей.

 

ОПЕРАЦИИ НАД ГРАФАМИ:

1. Дополнение графа

2. Объединение графов

3. Соединение графов – для того, чтобы соединить 2 графа необходимо каждую вершину графа G1 соединить с каждой вершиной графа G2.

4. Удаление вершины из графа

5. Удаление ребра из графа

6. Добавление вершины в граф

7. Добавление ребра в граф