![]() Главная страница Случайная страница КАТЕГОРИИ: АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника |
Лабораторная работа № 5. 1) Рассмотреть понятия эйлеров путь, эйлеров цикл.
Эйлеровы графы Цель работы; 1) Рассмотреть понятия эйлеров путь, эйлеров цикл. 2) Дать определение эйлерова графа. 3) Рассмотреть свойства эйлеровых графов. Литература: 1) " Графы и их применение", Березина Л.Ю., М.: Просвещение, 1979г. 2) " Теория графов. Алгоритмический подход", Кристофидес Н. 3) " Применение теории графов в программировании", Евстигнеев В.А Наука, 1985г. Порядок выполнения работы: I Разработать схему алгоритмов основной программы и подпрограмм. II Написать и отладить программу на языке Turbo Pascal. Задание: Заданы графы: 1)
2)
3) 5)
Краткие теоретические сведения: Граф называется полным, если каждые две его вершины соединены одним и только одним ребром. Степенью вершины называется число ребер графа, которым принадлежит эта вершина.
Степ. А=1 Степ. В=2 Степ. С=2 Степ. D=l Степ. Е=0 Вершина называется нечетной, если её степень - число нечетное. Вершина называется четной, если её степень - число четное. Степень каждой вершины полного графа на единицу меньше числа его вершин. Теорема о сумме степеней графа: В графе Г - сумма степеней всех его вершин, есть число четное, равное удвоенному числу его ребер, т.е.
где р - число ребер графа, п- число вершин.
|