Студопедия

Главная страница Случайная страница

Разделы сайта

АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника






Лабораторная работа № 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

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

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

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

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

 

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






© 2023 :: MyLektsii.ru :: Мои Лекции
Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав.
Копирование текстов разрешено только с указанием индексируемой ссылки на источник.