Лабораторная работа № 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. Сформулируйте теорему о сумме степеней вершин графа?

Тема 7.6 Плоские графы.

Граф называется плоским, если никакие два его соседних ребра не имеют других общих точек за исключением их общей вершины.

Рисунок графа называется его плоским представлением, если на нем никакие два ребра не имеют общих точек пересечения, если не считать точкой пересечения их вершину.

Теорема: Для того, чтобы граф являлся плоским необходимо и достаточно ,чтобы существовало его плоское представление.

В качестве характеристики плоского графа вводят понятие грань.

Гранью в плоском представлении графа называется часть плоскости, ограниченная простым циклом и не имеющая внутри себя других циклов.

Грани:

(2,4,5,6,2)

(1,2,3,1)

(1,7,4,1)

(1,4,2,3,1)

Границей грани называется простой цикл, ограничивающий грань.

Две грани называются соседними, если их границы имеют хотя бы одно общее ребро.

Существует так называемая бесконечная грань, т.е. часть плоскости, лежащая вне графа и ограниченная изнутри простым циклом

АВ называют перегородкой, и если у графа есть перегородка, то не существует бесконечной грани.

Теорема: Если в плоском представлении графа без перегородок V – количество вершин, P – количество ребер, G – количество граней (с учетом бесконечной), то V – P + G = 2 (формула Эйлера).

Данная теорема используется в задачах для того, чтобы доказать, что заданный граф не является плоским.