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

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

Цель работы;

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

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

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

Литература:

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

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

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

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

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

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

Задание:

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

1)

4)

2)

3) 5)

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

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

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

Е

Степ. А=1

Степ. В=2

Степ. С=2

Степ. D=l

Степ. Е=0

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

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

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

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

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