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

1 2 3 4 5

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

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

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

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

Выполнила студентка 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,x_n, v _n; эта последовательность начинается и кончается вершиной, и каждое ребро последовательности инцидентно двум вершинам, одна из которых непосредственно предшествует ему, а другая непосредственно следует за ним. Указанный маршрут соединяет вершины v ₀ и v _nи его можно обозначить v ₀ v ₁ v ₂… v _n (наличие рёбер подразумевается). Эта последовательность иногда называется (v ₀- v _n)-маршрутом. Маршрут замкнут, если v ₀= v _n, и открыт в противном случае. Маршрут называется цепью, если все его рёбра различны, и простой цепью, если все вершины (а следовательно, и рёбра) различны. Замкнутая цепь называется циклом. Замкнутый маршрут называется простым циклом, если все его n вершин различны и n³3.