МДК.01.02 Математический аппарат для проектирования компьютерных сетей

«Компьютерные сети»

Тема: Нахождение эйлеровых циклов и путей
Цель работы: Приобрести навыки нахождения эйлеровых циклов или путей.
Норма времени: 2 часа.
После выполненных работ студент должен знать: алгоритм Флери нахождения эйлерова цикла или пути.
уметь: находить эйлеровы циклы или пути в графах.

Практическая работа № 2

вершин и ребер, начинающаяся и заканчивающаяся вершиной.
Путь в графе

– это маршрут, в котором все ребра различны.
Путь называется простым, если и все вершины в нем различны.
Циклом называется простая замкнутая цепь.
Цикл длины 1 называется петлей.

Практическая работа № 2

путь, соединяющий эти вершины.
Компонентой связности графа G называется его правильный

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

Практическая работа № 2

степени всех вершин четны.
Если граф G(V,E) обладает эйлеровым циклом,

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

Практическая работа № 2

текущий граф равным G , а текущую вершину —равной произвольной

вершине v ∈V (G). 2. Выбрать произвольное, с учетом ограничения (см. ниже) ребро e текущего графа, инцидентное текущей вершине. 3. Назначить текущей вторую вершину, инцидентную e. 4. Удалить e из текущего графа и внести в список. 5. Если в текущем графе еще остались ребра, вернуться на шаг 2.
Ограничение: если степень текущей вершины в текущем графе больше 1, нельзя выбирать ребро, удаление которого из текущего графа увеличит число компонент связности в нем.

Практическая работа № 2

проверить возможность построения эйлерова цикла или пути.
Если построение невозможно,

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

и гамильтоновых циклов или путей
1. Вариант...
2. Изображение графа; если граф

изменялся – также изображение нового графа с описанием изменения.
3. Граф... (является, не является) эйлеровым.
Построение эйлерова... (цикла, пути): … – … – … .
4. Граф... (является, не является) гамильторовым.
Построение гамильтонова... (цикла, пути): … – … – … .