Лабораторная работа № 5

Эйлеровы графы

Цель работы;

1) Рассмотреть понятия эйлеров путь, эйлеров цикл.

2) Дать определение эйлерова графа.

3) Рассмотреть свойства эйлеровых графов.

Литература:

1) "Графы и их применение", Березина Л.Ю., М.: Просвещение, 1979г.

2) "Теория графов. Алгоритмический подход", Кристофидес Н.

3) "Применение теории графов в программировании", Евстигнеев В.А Наука, 1985г.

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

I Разработать схему алгоритмов основной программы и подпрограмм.

II Написать и отладить программу на языке Turbo Pascal.

Задание:

Заданы графы:

1)

4)

2)

3) 5)

Краткие теоретические сведения:

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

Степенью вершины называется число ребер графа, которым принадлежит эта вершина.

Е

Степ. А=1

Степ. В=2

Степ. С=2

Степ. D=l

Степ. Е=0

Вершина называется нечетной, если её степень - число нечетное. Вершина называется четной, если её степень - число четное.

Степень каждой вершины полного графа на единицу меньше числа его вершин.

Теорема о сумме степеней графа:

В графе Г - сумма степеней всех его вершин, есть число четное, равное удвоенному числу его ребер, т.е.

где р - число ребер графа, п- число вершин.

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

1) Составление алгоритмов.

2) Написание программы на языке Turbo Pascal.

3) Отладка программы.

Контрольные вопросы:

1) Что такое полный граф?

2) Дайте понятие степени вершины графа?

3) Какая вершина графа называется четной?

4) Какая вершина графа называется нечетной?

5) Сформулируйте теорему о сумме степеней вершин графа?