Курсовая работа: Эйлеровы графы

Выполнила студентка 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).

--> ЧИТАТЬ ПОЛНОСТЬЮ <--