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

ПОМОРСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТим. М.В. Ломоносова

КУРСОВАЯ РАБОТА

                                           ЭЙЛЕРОВЫ   ГРАФЫ

                                                                        Выполнила студентка 4 курса

                                                                         42 группы математического

                                                                        факультета Катышева Н.Г.

                                                                  Научный руководитель:

                                                                            Токаревская С.А.

Архангельск

2004


Оглавление

Введение............................................................................................. 3

Глава 1. Теоретическая часть............................................................ 4

Основные понятия теории графов..................................................... 4

Маршруты и связность...................................................................... 6

Задача  о  кёнигсбергских  мостах.................................................... 7

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

Оценка числа эйлеровых графов.................................................... 13

Алгоритм построения эйлеровой цепи в данном эйлеровом графе. 14

Глава 2. Практическая часть........................................................... 15

Заключение....................................................................................... 24

Литература....................................................................................... 25


Введение

Первая работа по теории графов, принадлежащая известному швейцарскому математику Л.Эйлеру, появилась в 1736г. Вначале теория графов казалась довольно незначительным разделом математики, так как она имела дело в основном с математическими развлечениями и головоломками. Однако дальнейшее развитие математики и особенно её приложений дало сильный толчок развитию теории графов. Уже в XIX столетии графы использовались при построении схем.

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

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


     Глава 1. Теоретическая часть.

Основные понятия теории графов

Граф G – пара (V,X), где V конечное непустое множество,  содержащее  p вершин, а множество Х содержит q неупорядоченных пар различных вершин из V.

Каждую пару X={u,v} вершин в Х называют ребром графа G и говорят, что Х соединяет u и v.Мы будем писать X=uv и говорить, что u и v – смежные вершины. Вершина u и ребро Х инцидентны, так же как v и Х. Если два различных ребра X и Y инцидентны одной и той же вершине, то они называются смежными. Граф с р вершинами и q ребрами называется (p;q)- графом. Граф (1,0)- называется тривиальным.(6)

Если элементом множества V может быть пара одинаковых элементов u, то такой элемент множества V называется петлёй.(3)

Типы графов:

· Мультиграф, в нём не допускаются петли, но пары вершин могут соединяться более чем одним ребром, эти рёбра называются кратными (рис.1).

· Псевдограф, в нём допускаются петли и кратные рёбра (рис.2).


                                              Рис.1                                  Рис.2

· Ориентированный граф, или орграф, состоит из конечного непустого множества V вершин и заданного набора Х упорядоченных пар различных вершин. Элементы из Х называются ориентированными рёбрами, или дугами. Нет петель и кратных дуг (рис. 3).

Рис.3

Подобные работы:

Актуально: