ПОМОРСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ им. М.В. Ломоносова КУРСОВАЯ РАБОТА
ЭЙЛЕРОВЫ ГРАФЫ
Выполнила студентка 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 вершин и заданного набора Х упорядоченных пар различных вершин. ............
