Практическое занятие № 4 "Нахождение эйлерова цикла"

ИНСТРУКЦИОННАЯ КАРТА

на выполнение практического занятия № 4

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

Тема занятия: Нахождение эйлерова цикла.

Цель проведения занятия: изучить алгоритм поиска эйлерова цикла (пути) в ориентированном и неориентированном графах.

После выполнения работы студент должен

знать: понятия эйлерова графа, цикла, цепи, алгоритм поиска эйлерова пути;

уметь: находить эйлеров путь в графе.

Материально-техническое оснащение рабочего места: инструкционные карты, конспект.

Инструктаж по технике безопасности

Рекомендованная литература:

1. Спирина М.С., Дискретная математика: Учебник для студ. Учреждений сред. проф. образования / М.С.Спирина, П.А.Спирин. –М.: Издательский центр «Академия», 2004. –368 с.

2. Александров А. В. и др. Прикладные алгоритмы на графах. Учебное пособие, ВлГУ, 2005

3. Харари Фрэнк. Теория графов / Харари Фрэнк ; Пер. с англ. В.П.Козырева; Под ред. Г.П.Гаврилова. - 4-е изд. - М. : URSS : Либроком, 2009. - 296 с

4. Битюцкий В. П. Электронный учебник: Дискретная математика / http://ait.ustu.ru/uploaded/materialy-po-disciplinam/discret-mathematics/el_ucheb/index.htm

5. Справочные данные по математике: Элементы теории графов. [Электронный ресурс]. – Режим доступа: http://book.itep.ru/10/grap1021.htm, свободный. – Загл. с экрана.

Содержание и порядок выполнения задания

Задание 1. Существует ли эйлеров цикл в графе G. Если существует, найдите его.

а) б) в)

Задание 2. Какие из следующих ориентированных графов имеют эйлеровы циклы?

Задание 3. Найдите эйлеров цикл в эйлеровом графе

Задание 4. Для графов из практической работы №1, 2 проверить являются ли они эйлеровыми графами. Если нет, то добавить ребра и дуги (оставляя число вершин неизменным) так, чтобы граф стал эйлеровым. Найти эйлеров цикл или цепь в полученных графах.

Проверить решение в программе Grafoanalizator1.3.3 rus.

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

1. Что называется маршрутом, цепью, циклом в графе?

2. Дайте определение эйлерова цикла, цепи.

3. Дайте определение эйлерова графа, орграфа.

4. Сформулируйте алгоритм построения эйлерова цикла.

5. Существует ли эйлеров граф, обладающий висячей вершиной?

Краткие сведения по теоретической части работы

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

Алгоритм поиска эйлерова цикла (пути) в графе.

Методические рекомендации по выполнению и оформлению

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

1. Изучить инструкцию к практической работе.

2. Выполнить задание.

3. Оформить отчет.

Содержание отчета о занятии:

1. Тема.

2. Цель.

4. Практическое задание.

5. Ответ на 1 контрольный вопрос (по указанию преподавателя).

Инструкционная карта составлена преподавателем: Шнаревой Г.В.