Автор: Пользователь скрыл имя, 12 Сентября 2013 в 20:45, курсовая работа
Первая работа по теории графов, принадлежащая известному швейцарскому математику Л.Эйлеру, появилась в 1736г. Вначале теория графов казалась довольно незначительным разделом математики, так как она имела дело в основном с математическими развлечениями и головоломками. Однако дальнейшее развитие математики и особенно её приложений дало сильный толчок развитию теории графов. Уже в XIX столетии графы использовались при построении схем.
В настоящее время эта теория находит многочисленное применение в разнообразных практических вопросах: при установлении разного рода соответствий, при решении транспортных задач, задач о потоках в сети нефтепроводов, в программировании и теории игр, теории передачи сообщений.
Введение……………………………………………………… 3
Основные понятия теории графов………………………….. 4-6
Маршруты и связность……………………………………… 7
Задача о Кениксбергских мостах…………………………… 8-9
Эйлеровы графы……………………………………………... 10-13
Операции на графах…………………………………………. 14-19
Применение теории графов…………………………………. 20
Заключение…………………………………………………… 21
Литература……………………………………………………. 22
Таким образом, всякую замкнутую фигуру, имеющую в точности две нечётные вершины, можно начертить одним росчерком без повторений, начав в одной из нечётных вершин, а кончив в другой.
Теорема 4: Если связный граф G имеет 2k нечётных вершин, то найдётся семейство из k путей, которые в совокупности содержат все рёбра графа в точности по одному разу.
Доказательство: Половину нечётных вершин обозначим А1,А2,…,Аk,другую половину В1,В2,…,Вk(рис.7). Если вершины Аi и Вi (1<i<k) соединены ребром, то удалим из графа G ребро (Аi,Вi). Если вершины А и В не соединены ребром, то добавим к G ребро (Аi,Вi). Все вершины нового графа будут чётными, то есть в новом графе найдётся эйлеров цикл. При восстановлении графа G цикл разобьется на k отдельных путей, содержащих все рёбра графа.
Пусть G=(V,E) – ориентированный граф. Ориентированным циклом называется ориентированный путь ненулевой длины из вершины в ту же вершину без повторения ребер.
Пусть G=(V,E) – ориентированный граф. Ориентированный цикл, который включает все рёбра и вершины графа G, называется эйлеровым циклом. Говорят, что ориентированный граф G имеет эйлеров цикл.
Теорема 5: Ориентированный граф имеет эйлеров цикл тогда и только тогда, когда он связный и степень входа каждой вершины равна степени выхода.
Лемма : В любом графе число вершин нечётной степени чётно.
Доказательство: По теореме 1 сумма степеней всех вершин число чётное. Сумма степеней вершин чётной степени чётна, значит, сумма степеней вершин нечётной степени также чётна, значит, их число чётное.
Операции на графах
Операции на графах позволяют образовывать новые графы из нескольких более простых. В этом параграфе будут рассмотрены операции на графах без параллельных ребер (дуг).
Объединение графов.
Пусть G1(X1,E1) и G2(X2,E2) – произвольные графы. Объединением G1ÈG2 графов G1 и G2 называется граф с множеством вершин X1ÈX2, и с множеством ребер (дуг) E1ÈE2.
Рассмотрим операцию на примере графов G1(X1,E1) и G2(X2,E2), приведенных на рис. 4.1. Множества вершин первого и второго графов соответственно равны X1 = {x1, x2, x3} и X2 = {x2, x3, x4}, а множество вершин результирующего графа определится как X = X1ÈX2 = {x1, x2, x3, x4}. Аналогично определяем множества дуг графа:
E1 = {(x1, x2), (x1, x3), (x2, x1), (x3, x3)}.
E2 = {(x2, x4), (x3, x2), (x4, x2)}.
E = {(x1, x2), (x1, x3), (x2, x1), (x3, x3), (x2, x4), (x3, x2), (x4, x2)}.
Результирующий граф G(X,E) = G1(X1,E1)ÈG2(X2,E2) также приведен на рис. 1.
Операция объединения обладает следующими свойствами, которые следуют из определения операции и свойств операций на множествах:
G1ÈG2 = G2ÈG1 – свойство коммутативности;
G1È(G2ÈG3) = (G1ÈG2)ÈG3 – свойство ассоциативности.
Пересечение графов
Пусть G1(X1,E1) и G2(X2,E2) – произвольные графы. Пересечением G1ÇG2 графов G1 и G2 называется граф с множеством вершин X1ÇX2 с множеством ребер (дуг) E = E1ÇE2
Операция пересечения обладает следующими свойствами, которые следуют из определения операции и свойств операций на множествах:
G1ÇG2 = G2ÇG1– свойство коммутативности;
G1Ç (G2ÇG3) = (G1ÇG2) Ç G3 – свойство ассоциативности.
Для того чтобы операция пересечения была всеобъемлющей, необходимо ввести понятие пустого графа. Граф G(X,E) называется пустым, если множество X вершин графа является пустым (X=Æ). Заметим, что в этом случае и множество E ребер (дуг) графа также пустое множество (E=Æ). Пустой граф обозначается символом Æ. Такой граф может быть получен в результате выполнения операции пересечения графов, у которых X1ÇX2=Æ. В этом случае говорят о непересекающихся графах.
Рассмотрим выполнение операции пересечения графов, изображенных на рис. 2. Для нахождения множества вершин результирующего графа запишем множества вершин исходных графов и выполним над этими множествами операцию пересечения:
X1 = {x1, x2, x3}; X2 = {x1, x2, x3, x4};
X = X1ÇX2 = {x1, x2, x3}.
Аналогично определяем множество E дуг результирующего графа:
E1 = {(x1, x2), (x1, x3), (x2, x1), (x2, x3), (x3, x2)};
E2 = {(x1, x3), (x2, x1), (x2, x3), (x2, x4), (x3, x1)};
E = E1ÇE2 = {(x1, x3), (x2, x1)}.
Графы G1(X1,E1), G2(X2,E2) и их пересечение приведены на рис 4.2.
Операция пересечения графов может быть выполнена в матричной форме.
Операция произведения графов.
Пусть G1(X,E1) и G2(Y,E2) - два графа. Произведением G1×G2 графов G1 и G2 называется граф с множеством вершин X´Y, а дуга из вершины (xi,yj) в вершину (xk,yl) существует тогда и только тогда, когда существуют дуги (xi,xk) Î E1 и (yj,yl) Î E2.
Выполнение операции произведения рассмотрим на примере графов, изображенных на рис. 5. Множество вершин Z результирующего графа определяется как декартово произведение множеств X´Y. Множество Z содержит следующие элементы: z1=(x1y1), z2=(x1y2), z3=(x1y3), z4=(x2y1), z5=(x2y2), z6=(x2y3).
Определим множество дуг результирующего графа. Для удобства рассмотрения составим таблицу, в первом столбце которой указываются дуги графа G1, во втором – дуги графа G2, а в третьем и четвертом – дуги результирующего графа.
G1 |
G2 |
(x1,y1)®(x2,y1) |
(za, zb) |
(x1,x2) |
(y1,y1) (y1,y2) (y2,y3) (y3,y2) |
(x1,y1)®(x2,y1) (x1,y1)®(x2,y2) (x1,y2)®(x2,y3) (x1,y3)®(x2,y2) |
(z1,z4) (z1,z5) (z2,z6) (z3,z5) |
(x2,x1) |
(y1,y1) (y1,y2) (y2,y3) (y3,y2) |
(x2,y1)®(x1,y1) (x2,y1)®(x1,y2) (x2,y2)®(x1,y3) (x2,y3)®(x1,y2) |
(z4,z1) (z4,z2) (z5,z3) (z6,z2) |
Результирующий граф G1×G2 изображен на рис.5.
Операция произведения обладает следующими свойствами.
1. G1×G2 = G2×G1.
2. G1×(G2×G3) = (G1×G2)×G3.
Рассмотрим выполнение операции произведения графов в матричной форме.
Пусть G1(X,E1) и G2(Y,E2) – два графа, имеющие nx и ny вершин соответственно. Результирующий граф G1×G2 имеет nx×ny вершин, а его матрица смежности вершин - квадратная матрица размером (nx×ny)´ (nx ×ny). Обозначим через aab = a(ij)(kl) элемент матрицы смежности вершин, указывающий на наличие дуги (ребра), соединяющей вершину za=(xiyj) c zb=(xkyl). Этот элемент может быть вычислен при помощи матриц смежности вершин исходных графов следующим образом:
aab =a(ij)(kl) = a1,ik Ù a2,jl, (3)
где a1,ik, a1,ik – элементы матрицы смежности вершин графов G1 и G2 соответственно.
Композиция графов
Пусть G1(X,E1) и G2(X,E2) — два графа с одним и тем же множеством вершин X. Композицией G1(G2) графов G1 и G2 называется граф с множеством вершин E, в котором существует дуга (xi,xj) тогда и только тогда, когда существует дуга (xi,xk), принадлежащая множеству E1, и дуга (xk,xj), принадлежащая множеству E2.
Рассмотрим выполнение операции композиции G1(G2) на графах, изображенных на рис.3. Для рассмотрения операции составим таблицу, в первом столбце которой указываются ребра (xi, xk), принадлежащие графу G1, во втором — ребра (xk, xj), принадлежащие графу G3, а в третьем — результирующее ребро (xi, xj) для графа G1(G2).
G1 |
G2 |
G1(G2) |
(x1,x2) |
(x2,x1) (x2,x3) |
(x1,x1) (x1,x3) |
(x1,x3) |
(x3,x3) |
(x1,x3) |
(x2,x1) |
(x1,x1) (x1,x3) |
(x2,x1) (x2,x3) |
Заметим, что дуга (x1,x3) результирующего графа в таблице встречается дважды. Однако, поскольку рассматриваются графы без параллельных ребер (дуг), то в множестве E результирующего графа дуга (x1,x3) учитывается только один раз, т.е. E = {(x1,x1), (x1,x3), (x2,x1), (x2,x3)}
На рис. 3 изображены графы G1 и G2 и их композиции G1(G2). На этом же рисунке изображен граф G2(G1). Рекомендуется самостоятельно построить граф G2(G1) и убедиться, что графы G1(G2) и G2(G1) не изоморфны.
Пусть А1 и A2 – матрицы смежности вершин графов G1(X,E1) и G(X,E2) соответственно. Рассмотрим матрицу A12 элементы aij которой вычисляется так:
n
aij = Úa1ikÙa2kj (1)
k=1
где a1ik и a2kj – элементы матрицы смежности вершин первого и второго графов соответственно. Элемент aij равен 1, если в результирующем графе G1(G2) существует дуга, исходящая из вершины xi и заходящая xj, и нулю – в противном случае.
Применение теории графов
В химии (для описания структур, путей сложных реакций, правило фаз также может быть интерпретировано как задача теории графов); компьютерная химия — сравнительно молодая область химии, основанная на применении теории графов. Теория графов представляет собой математическую основу хемоинформатики. Теория графов позволяет точно определить число теоретически возможных изомеров у углеводородов и других органических соединений.
В информатике и программировании
В коммуникационных и транспортных системах. В частности, для маршрутизации данных в Интернете;
В экономике.