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

ПОМОРСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ

им. М.В. Ломоносова

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

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

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

Рис.4

· Направленный граф – это орграф, не имеющий симметричных пар ориентированных рёбер (рис.4).

· Помеченные графы (или перенумерованные), если его вершины отличаются одна от другой какими-либо пометками. В качестве пометок обычно используются буквы или целые числа.[6]

Степенью вершины v _i в графе G называется число рёбер, инцидентных v _i ,обозначается d_{i .} [6] Для орграфа вводятся понятия степени входа и выхода. Степенью выхода вершины v называется количество рёбер, для которых v является начальной вершиной, обозначается outdeg(v ). Степенью входа вершины v называется количество рёбер , для которых v является конечной вершиной, обозначается indeg(v ). Если indeg(v )=0, то вершина v называется источником. Если outdeg(v )=0, то вершина v называется стоком.[1]

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

Граф G/ (U/ ,V/ ) называется подграфом графа G(U,V), если U/ ÌU и V/ ÌV. Обозначение: G/ ÌG.

Если V/ =V, то G/ называется остовным подграфом G.[3]

Маршрутом в графе G называется чередующаяся последовательность вершин и рёбер v ₀ ,x₁ ,v ₁ ,…v _n-1

Внимание, отключите Adblock

Вы посетили наш сайт со включенным блокировщиком рекламы!
Ссылка для скачивания станет доступной сразу после отключения Adblock!

Скачать