Банк рефератов содержит более 364 тысяч рефератов, курсовых и дипломных работ, шпаргалок и докладов по различным дисциплинам: истории, психологии, экономике, менеджменту, философии, праву, экологии. А также изложения, сочинения по литературе, отчеты по практике, топики по английскому.
Полнотекстовый поиск
Всего работ:
364150
Теги названий
Разделы
Авиация и космонавтика (304)
Административное право (123)
Арбитражный процесс (23)
Архитектура (113)
Астрология (4)
Астрономия (4814)
Банковское дело (5227)
Безопасность жизнедеятельности (2616)
Биографии (3423)
Биология (4214)
Биология и химия (1518)
Биржевое дело (68)
Ботаника и сельское хоз-во (2836)
Бухгалтерский учет и аудит (8269)
Валютные отношения (50)
Ветеринария (50)
Военная кафедра (762)
ГДЗ (2)
География (5275)
Геодезия (30)
Геология (1222)
Геополитика (43)
Государство и право (20403)
Гражданское право и процесс (465)
Делопроизводство (19)
Деньги и кредит (108)
ЕГЭ (173)
Естествознание (96)
Журналистика (899)
ЗНО (54)
Зоология (34)
Издательское дело и полиграфия (476)
Инвестиции (106)
Иностранный язык (62792)
Информатика (3562)
Информатика, программирование (6444)
Исторические личности (2165)
История (21320)
История техники (766)
Кибернетика (64)
Коммуникации и связь (3145)
Компьютерные науки (60)
Косметология (17)
Краеведение и этнография (588)
Краткое содержание произведений (1000)
Криминалистика (106)
Криминология (48)
Криптология (3)
Кулинария (1167)
Культура и искусство (8485)
Культурология (537)
Литература : зарубежная (2044)
Литература и русский язык (11657)
Логика (532)
Логистика (21)
Маркетинг (7985)
Математика (3721)
Медицина, здоровье (10549)
Медицинские науки (88)
Международное публичное право (58)
Международное частное право (36)
Международные отношения (2257)
Менеджмент (12491)
Металлургия (91)
Москвоведение (797)
Музыка (1338)
Муниципальное право (24)
Налоги, налогообложение (214)
Наука и техника (1141)
Начертательная геометрия (3)
Оккультизм и уфология (8)
Остальные рефераты (21697)
Педагогика (7850)
Политология (3801)
Право (682)
Право, юриспруденция (2881)
Предпринимательство (475)
Прикладные науки (1)
Промышленность, производство (7100)
Психология (8694)
психология, педагогика (4121)
Радиоэлектроника (443)
Реклама (952)
Религия и мифология (2967)
Риторика (23)
Сексология (748)
Социология (4876)
Статистика (95)
Страхование (107)
Строительные науки (7)
Строительство (2004)
Схемотехника (15)
Таможенная система (663)
Теория государства и права (240)
Теория организации (39)
Теплотехника (25)
Технология (624)
Товароведение (16)
Транспорт (2652)
Трудовое право (136)
Туризм (90)
Уголовное право и процесс (406)
Управление (95)
Управленческие науки (24)
Физика (3463)
Физкультура и спорт (4482)
Философия (7216)
Финансовые науки (4592)
Финансы (5386)
Фотография (3)
Химия (2244)
Хозяйственное право (23)
Цифровые устройства (29)
Экологическое право (35)
Экология (4517)
Экономика (20645)
Экономико-математическое моделирование (666)
Экономическая география (119)
Экономическая теория (2573)
Этика (889)
Юриспруденция (288)
Языковедение (148)
Языкознание, филология (1140)

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

Название: Эйлеровы графы
Раздел: Рефераты по математике
Тип: курсовая работа Добавлен 00:00:09 22 декабря 2007 Похожие работы
Просмотров: 2245 Комментариев: 2 Оценило: 0 человек Средний балл: 0 Оценка: неизвестно     Скачать

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

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

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

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

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

Граф G называется связным, если любая пара его вершин соединена простой цепью.[6]

Задача о кёнигсбергских мостах.

Отцом теории графов является Эйлер (1707-1782), решивший в 1736г. широко известную в то время задачу, называвшуюся проблемой Кёнигсбергских мостов. В городе Кёнигсберге (ныне Калининград) было два острова, соединенных семью мостами с берегами реки Преголя и друг с другом так, как показано на рисунке 5. Задача состояла в следующем: найти маршрут прохождения всех четырёх частей суши, который начинался бы с любой из них, кончался бы на этой же части и ровно один раз проходил по каждому мосту.




Рис.5.

Легко, конечно попытаться решить эту задачу эмпирически, производя перебор всех маршрутов, но все попытки окончатся неудачей. Исключительный вклад Эйлера в решение этой задачи заключается в том, что он доказал невозможность такого маршрута.

Для доказательства того, что задача не имеет решения, Эйлер обозначил каждую часть суши точкой (вершиной), а каждый мост – линией (ребром), соединяющей соответствующие точки. Получился “граф”. Этот граф показан на рисунке 6, где точки отмечены теми же буквами, что и четыре части суши на рисунке 5.


Рис.6.

Утверждение о не существовании “положительного” решения у этой задачи эквивалентно утверждению о невозможности обойти специальным образом граф, представленный на рисунке 6.

Отправляясь от этого частного случая Эйлер обобщил постановку задачи и нашёл критерий существования обхода у данного графа, а именно граф должен быть связным и каждая его вершина должна быть инцидентна чётному числу рёбер.[6]

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

Решение Эйлером задачи о Кёнигсбергских мостах привела к первой опубликованной работе по теории графов. Задачу об обходе мостов можно обобщить и получить следующую задачу теории графов: можно ли найти в данном графе G цикл, содержащий все вершины и все рёбра? Граф, в котором это возможно, называется эйлеровым. Таким образом, эйлеров граф имеет эйлеров цикл – замкнутую цепь, содержащую все вершины и все рёбра. Ясно, что эйлеров граф должен быть связным.[6]

Если снять ограничения на замкнутость цепи, то граф называется полуэйлеровым.

Теорема 1(критерий):

Граф с более чем одной вершиной имеет эйлеров цикл тогда и только тогда, когда он связный и каждая его вершина имеет чётную степень.

Доказательство: Предположим, что граф G имеет эйлеров цикл. Граф является связным, так как каждая вершина принадлежит циклу. Для всякой вершины v графа G каждый раз, когда эйлеров цикл проходит через v , он вносит 2 в степень v . Поэтому степень v чётная.

Обратно, нужно показать, что каждый связный граф, у которого степени вершин чётные, имеет эйлеров цикл. Докажем эту теорему, используя индукцию по числу вершин. Поскольку теорема тривиально справедлива при n£3, начнём индукцию с n=3. Предположим, что каждый связный граф, имеющий менее k вершин, и все вершины которого обладают чётной степенью, содержит эйлеров цикл. Пусть G – связный граф, содержащий k вершин, степени которых чётные. Допустим, что v 1 и v 2 - вершины графа G. Поскольку граф G – связный, существует путь из v 1 в v 2 .Поскольку степень v 2 – чётная, существует неиспользованное ребро, по которому можно продолжить путь. Поскольку граф конечный, то путь, в конце концов, должен вернуться в v 1 , и эйлеров цикл С1 можно считать построенным. Если С1 является эйлеровым циклом для G, тогда доказательство закончено. Если нет, то пусть G/ - подграф графа G, полученный удалением всех рёбер, принадлежащих С1 . Поскольку С1 содержит чётное число рёбер, инцидентных каждой вершине, каждая вершина подграфа G/ имеет чётную степень.

Пусть e – ребро графа G/ , пусть Ge – компонента графа G/ , содержащая е. Поскольку G/ имеет менее, чем k, вершин, и у каждой вершины графа G/ чётная степень, граф G/ имеет эйлеров цикл. Пусть С2 . Далее у С1 и С2 имеется общая вершина, допустим, а. Теперь можно продолжить эйлеров цикл, начиная его в а, пройти С1 , вернуться в а, затем пройти С2 и вернуться в а. Если новый эйлеров цикл не является эйлеровым циклом для G , продолжаем использовать этот процесс, расширяя наш эйлеров цикл, пока, к конце концов, не получим эйлеров цикл для G .[1]

Из теоремы 1 следует, что если в связном графе G нет вершин с нечётными степенями, то в G есть замкнутая цепь, содержащая все вершины и все рёбра графа G. Аналогичный результат справедлив для связных графов, имеющих некоторое число вершин с нечётными степенями.

Следствие 1(а): Пусть G- связный граф, в котором 2n вершин имеют нечётные степени, n>1. Тогда множество рёбер графа G можно разбить на n открытых цепей.

Следствие 1(б): Пусть G- связный граф, в котором две вершины имеют нечётные степени. Тогда в G есть открытая цепь, содержащая все вершины и все рёбра графа G (и начинающаяся в одной из вершин с нечётной степенью, а кончающаяся в другой).[6]

Эйлеровым путём в графе называется путь, содержащий все рёбра графа. Эйлеров путь называется собственным, если он не является эйлеровым циклом.[1]

Теорема 2: Если граф G обладает эйлеровым путём с концами А и В (А не совпадает с В), то граф G связный и А и В – единственные нечётные его вершины.

Доказательство: Связность графа следует из определения эйлерова пути. Если путь начинается в А, а заканчивается в другой вершине, то и А и В – нечётные даже если путь неоднократно проходил через А и В. В любую другую вершину графа путь должен был привести и вывести из неё, то есть все остальные вершины должны быть чётными.

Теорема 3 : (обратная) Если граф G связный и А и В единственные нечётные вершины его, то граф G обладает эйлеровым путём с концами А и В.

Доказательство: Вершины А и В могут быть соединены ребром в графе, а могут быть соединены.

Если А и В соединены ребром, то удалим его; тогда все вершины станут чётными. Новый граф (по теореме 1) обладает эйлеровым циклом, началом и концом которого может служить любая вершина. Начнём эйлеров путь в вершине А и кончим его в вершине А. Добавим ребро (А,В) и получим эйлеров путь с началом в А и концом в В.

Если А и В не соединены ребром, то к графу добавим новое ребро (А,В), тогда все вершины его станут чётными. Новый граф (по теореме 1) обладает эйлеровым циклом. Начнём его из вершины А по ребру (А,В). Заканчивается путь тоже в вершине А. Если удалить теперь из полученного цикла ребро (А,В), то останется эйлеров путь с началом в В и концом в А или началом в А и концом В.

Таким образом, всякую замкнутую фигуру, имеющую в точности две нечётные вершины, можно начертить одним росчерком без повторений, начав в одной из нечётных вершин, а кончив в другой.

Теорема 4 : Если связный граф G имеет 2k нечётных вершин, то найдётся семейство из k путей, которые в совокупности содержат все рёбра графа в точности по одному разу.

Доказательство: Половину нечётных вершин обозначим А12 ,…,Аk ,другую половину В12 ,…,Вk (рис.7). Если вершины Аi и Вi (1<i<k) соединены ребром, то удалим из графа G ребро (Аii ). Если вершины А и В не соединены ребром, то добавим к G ребро (Аii ). Все вершины нового графа будут чётными, то есть в новом графе найдётся эйлеров цикл. При восстановлении графа G цикл разобьется на k отдельных путей, содержащих все рёбра графа.[2]


Рис.7

Пусть G=(V,E) – ориентированный граф. Ориентированным циклом называется ориентированный путь ненулевой длины из вершины в ту же вершину без повторения ребер.

Пусть G=(V,E) – ориентированный граф. Ориентированный цикл, который включает все рёбра и вершины графа G, называется эйлеровым циклом. Говорят, что ориентированный граф G имеет эйлеров цикл.

Теорема 5 : Ориентированный граф имеет эйлеров цикл тогда и только тогда, когда он связный и степень входа каждой вершины равна степени выхода.[1]

Оценка числа эйлеровых графов

Лемма : В любом графе число вершин нечётной степени чётно.

Доказательство: По теореме 1 сумма степеней всех вершин число чётное. Сумма степеней вершин чётной степени чётна, значит, сумма степеней вершин нечётной степени также чётна, значит, их чётное число.

Пусть G(p) – множество всех графов с р вершинами, а Е(р) – множество эйлеровых графов с р вершинами.

Теорема 6: Эйлеровых графов почти нет, то есть

lim

Доказательство: Пусть E/ (р) – множество графов с р вершинами и чётными степенями. Тогда по теореме1 Е(р)ÌЕ/ (p) и |Е(р)|£|Е/ (p)|.В любом графе число вершин нечётной степени чётно, следовательно, любой граф из Е/ (p) можно получить из некоторого графа G(p-1), если добавить новую вершину и соединить её со всеми старыми вершинами нечётной степени. Следовательно, |Е/ (p)| £|G(p-1)|. Но |G(p)|=2C( p, 2) . Заметим, что

С(k,2)-C(k-1,2)=

=

Далее имеем:

|Е(р)|£|Е/ (p)| £|G(p-1)| = 2C( p-1,2) =2C( p,2)-( p-1) = |G(p)|2-( p-1)

и

, откуда lim . [3]

Алгоритм построения эйлеровой цепи в данном эйлеровом графе.

Этот метод известен под названием алгоритма Флёри.

Теорема 7: Пусть G – эйлеров граф, тогда следующая процедура всегда возможна и приводит к эйлеровой цепи графа G. Выходя из произвольной вершины и, идём по рёбрам графа произвольным образом, соблюдая лишь следующие правила:

1) стираем рёбра по мере их прохождения и стираем также изолированные вершины, которые при этом образуются;

2) на каждом этапе идём по мосту только тогда, когда нет других возможностей.

Доказательство: Покажем сначала, что указанная процедура может быть выполнена на каждом этапе. Предположим, что мы достигли некоторой вершины V; тогда если V¹U, то оставшийся подграф H связен и содержит ровно две вершины нечётной степени, а именно U и V. Согласно теореме 3 и определению полуэйлерова графа, граф H содержит полуэйлерову цепь P из V в U. Поскольку удаление первого ребра цепи Р не нарушает связности графа Н, то описанное в теореме построение (Т 1б)) возможно на каждом этапе. Если же V=U, то доказательство остаётся тем же самым до тех пор, пока есть ещё рёбра, инцидентные вершине U.

Осталось только показать, что данная процедура всегда приводит к полной эйлеровой цепи. Но это очевидно, так как в G не может быть рёбер, оставшихся не пройденными после использования последнего ребра, инцидентного U. В противном случае удаление некоторого ребра, смежного одному из оставшихся, привело бы к несвязному графу, что противоречит условию 2).[5]

Глава 2. Практическая часть

Задачи:

1. Существует ли эйлеров цикл в графе G. Если существует, найдите его.[2]


Решение:

А) Так как каждая вершина имеет чётную степень, то по критерию в этом графе существует эйлеров цикл: 1,4,6,9,10,8,5,3,2,4,7,10,11,8,6,5,2,1

Б) В этом графе также каждая вершина имеет чётную степень, значит, существует и эйлеров цикл: 1,2,3,4,5,3,1,4,5,2,1

В) Здесь каждая вершина имеет степень 5, то есть нечётную, следовательно, в этом графе (по критерию) нет эйлерова цикла.

2. Где на выставке следовало бы сделать вход и выход (рис.8) , чтобы можно было провести экскурсию по всем залам, побывав в каждом из них в точности один раз?[2]


Рис.8

Решение:

В этом графе вершины А и В имеют степень 3, то есть нечётную, следовательно, в нём существует эйлеров путь с началом в одной из этих вершин и концом в другой. Значит, вход и выход следует установить в вершинах А и В.

3. Среди приведённых ниже графов найдите те, которые имеют эйлеров цикл.[1]

Решение:

а) Т.к. этот граф связный и каждая его вершина имеет чётную степень, то по критерию эйлерова графа, данный граф имеет эйлеров цикл:

a b e j i f c b d h j g f a c d e h g i a

б) Этот граф связный, но т.к. все его вершины имеют нечётную степень, то он не имеет эйлерова цикла.

в) Этот граф связный, но т.к. все его вершины имеют степень 3, то есть нечётную, то он не имеет эйлерова цикла.

г) Данный граф связный, степени вершин а и с имеют нечётную степень, значит, этот граф не имеет эйлерова цикла.

4. Среди приведённых ниже графов найдите те, которые имеют эйлеров цикл.[1]

Решение:

а) Граф не является связным, то есть не выполняется первое условие критерия, значит, он не имеет эйлерова цикла.

б) Этот граф является связным и все его вершины имеют чётную степень, значит, по критерию эйлерова графа, он имеет эйлеров цикл:

a c f h I j k g d c b f I l j g e d a

в) Данный граф связный, но степени вершин а и е нечётные, следовательно по критерию, этот граф не имеет эйлерова цикла.

г) Граф является связным, но так как все его вершины имеют нечётную степень, то граф не имеет эйлерова цикла.

5. Среди приведённых ниже графов найдите те, которые имеют собственный эйлеров путь.[1]

Решение:

а) Граф связный, и только две его вершины (a и f) имеют нечётную степень, следовательно, то по теореме 3, граф имеет собственный эйлеров путь.

б) Граф связный; deg(a)=3, deg(b)=3, deg(c)=3, то есть более двух вершин имеют нечётную степень, значит, не имеет эйлерова пути.

в) Этот граф связный и только две вершины (с и j) имеют нечётную степень, значит, граф имеет собственный эйлеров путь.

г) Граф связный; deg(a)=3, deg(b)=4, deg(c)=1, deg(d)=3, то есть более двух вершин имеют нечётную степень, следовательно, в этом графе нет эйлерова пути.

6. Среди приведённых ниже графов найдите те, которые имеют собственный эйлеров цикл.[1]

Решение:

а) Данный граф связный; deg(a)=3, deg(b)=2, deg(c)=3, deg(d)=2, deg(e)=2. Ровно две вершины имеют нечётную степень, значит, по теореме 3, граф имеет собственный эйлеров путь.

б) Граф является связным и ровно две его вершины (е и f) имеют нечётную степень, значит, данный граф имеет собственный эйлеров путь.

в) Граф связный, найдём степени вершин: deg(d)=5, deg(b)=5, deg(e)=5, нашлись три вершины, степень которых нечётная, значит, граф не имеет эйлерова пути.

г) Данный граф связный и только две его вершины (а и b) имеют нечётную степень, значит, этот граф имеет собственный эйлеров путь.

7. Какие из следующих ориентированных графов имеют эйлеровы циклы? [1]

Решение:

а) Граф связный, найдём степени входа и выхода вершин (по теореме 5 степени входа и выхода каждой вершины должны совпадать):

indeg(a)=2, outdeg(a)=1, то есть нашлась вершина, у которой не совпадают степени входа и выхода, значит, граф не имеет эйлерова цикла.

б) Граф связный, найдём степени вершин:

indeg(a)=2 outdeg(a)=2

indeg(b)=2 outdeg(b)=2

indeg(c)=2 outdeg(c)=2

indeg(d)=2 outdeg(d)=2

indeg(e)=2 outdeg(e)=2

Следовательно, по теореме 5, граф имеет эйлеров цикл.

в) Граф связный, найдём степени вершин:

indeg(a)=2 outdeg(a)=2

indeg(b)=1 outdeg(b)=1

indeg(c)=3 outdeg(c)=1

Условия теоремы 5 не выполняются, значит, граф не имеет эйлерова цикла.

г) ) Граф связный, найдём степени вершин:

indeg(a)=2 outdeg(a)=1

Следовательно, т.к. условия теоремы 5 не выполняются то, граф не имеет эйлерова цикла.

8. Какие из следующих ориентированных графов имеют эйлеровы циклы? [1]

Решение:

а) Граф связный, найдём степени вершин:

indeg(a)=1 outdeg(a)=1

indeg(b)=5 outdeg(b)=1

Т.к. второе условие теоремы 5 не выполняется, значит, граф не имеет эйлерова цикла.

б) Граф не связный, то есть первое условие теоремы 5 не выполняется. Значит, граф не имеет эйлерова цикла.

в) Граф связный, найдём степени вершин:

indeg(a)=2 outdeg(a)=1

Второе условие теоремы 5 не выполняется, значит, граф не имеет эйлерова цикла.

г) Граф связный, найдём степени вершин:

indeg(a)=2 outdeg(a)=2

indeg(b)=3 outdeg(b)=1

Граф не имеет эйлерова цикла, т.к. не выполняется второе условие теоремы 5.

9. На рисунке план подземелья, в одной из комнат которого скрыты богатства рыцаря. После смерти рыцаря его наследники нашли завещание, в котором было сказано, что для отыскания сокровищ достаточно войти в одну из крайних комнат подземелья, пройти через все двери, причём в точности по одному разу через каждую; сокровища скрыты за той дверью, которая будет пройдена последней. В какой комнате были скрыты сокровища?

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

Построим граф, вершинами которого являются комнаты подземелья, а рёбрами – двери. Затем найдём такой путь, чтобы пройти по всем рёбрам (через все двери) в точности по одному разу.


Данный граф имеет эйлеров путь, так как только две вершины имеют нечётную степень, это вершины 6 и 18. Значит, вход и выход могут быть только в вершинах 6 и 18.

Так как комната 6 является крайней, то в ней будет вход, значит, последней комнатой будет 18-ая, следовательно сокровища скрыты в этой комнате.

Заключение

В данной работе были рассмотрены основные понятия теории графов, их виды. Большое внимание уделили вопросу существования в них эйлеровых цепей и циклов, рассмотрели ряд теорем и свойств. Описали алгоритм нахождения эйлерова цикла в произвольном графе, а в практической части показали его применение на конкретных примерах.

Известно, что эйлеровы графы получили широкое распространение и популярность благодаря тому, что многие головоломки и задачи можно решить с использованием знаний теории графов. Частные примеры таких головоломок и сюжетных задач были приведены в практической части. Задачи на отыскание путей через лабиринты, близкие к задачам на эйлеровы графы, находят применение в современной психологии и при конструировании вычислительных машин. Также с практической точки зрения, сейчас графы применяют во многих других областях науки таких как: программирование, физика, химия, биология, экономика и т.д.

Литература

1. Андерсон, Джеймс А. Дискретная математика и комбинаторика: пер. с англ. – М.: Издательский дом «Вильямс», 2003. – 960с.

2. Березина Л. Ю. Графы и их применение. – М.: Просвещение, 1979.

3. Новиков С.А. Дискретная математика для программистов – СПб.: Питер, 2001. – 304с.

4. Оре о. Графы и их применение. – М.: Мир,1973.

5. Уилсон Р. Введение в теорию графов. – М.: Мир, 1977.

6. Харари Ф. Теория графов. – М.: Мир, 1973.

Оценить/Добавить комментарий
Имя
Оценка
Комментарии:
Где скачать еще рефератов? Здесь: letsdoit777.blogspot.com
Евгений07:55:53 19 марта 2016
Кто еще хочет зарабатывать от 9000 рублей в день "Чистых Денег"? Узнайте как: business1777.blogspot.com ! Cпециально для студентов!
08:20:04 29 ноября 2015

Работы, похожие на Курсовая работа: Эйлеровы графы
Эйлеровы и гамильтоновы графы
Министерство народного образования Республики Дагестан Дагестанский Государственный Университет Курсовая работа Программирование задач на графах ...
Теорема 1. Чтобы в связанном неориентированном графе G существовал эйлеров цикл, необходимо и достаточно, чтобы число вершин нечетной степени было четным.
Пусть мы достигли некоторой вершины v, начав с вершины u, v = u. Удалив ребра пути из v в u, видим, что оставшийся граф G1 связен и содержит ровно две нечетных вершины v и u ...
Раздел: Рефераты по информатике, программированию
Тип: реферат Просмотров: 6748 Комментариев: 3 Похожие работы
Оценило: 1 человек Средний балл: 2 Оценка: неизвестно     Скачать
Нестандартные задачи по математике
Курсовая работа по математике Нестандартные задачи по математике Студент: Игнатьева Ольга Михайловна физико - математический факультет 4 курс Научный ...
Поскольку число нечетных вершин в графе четно, в нем есть еще одна нечетная вершина.
Тогда из вершин А и С должно выходить уже нечетное число ребер, а из промежуточных вершин В и К - по-прежнему четное число.
Раздел: Рефераты по математике
Тип: курсовая работа Просмотров: 1335 Комментариев: 2 Похожие работы
Оценило: 0 человек Средний балл: 0 Оценка: неизвестно     Скачать
Орграфы, теория и применение
Федеральное агентство по образованию РФ Государственное образовательное учреждение высшего профессионального образования "Санкт-Петербургский ...
Мультиграф обладает эйлеровой цепью тогда и только тогда, когда он связен и число вершин нечетной степени равно 0 или 2. Гамильтонов цикл - простой цикл, проходящий через все ...
Если D - орграф с линейными подграфами DI, " = 1, 2,. Любому графу G поставим в соответствие орграф D, в котором вершины vt и V) соединены дугами vtVj и VjVt только в том случае ...
Раздел: Рефераты по математике
Тип: реферат Просмотров: 1147 Комментариев: 2 Похожие работы
Оценило: 0 человек Средний балл: 0 Оценка: неизвестно     Скачать
Графы. Решение практических задач с использованием графов (С++
Курсовая работа Выполнил: студент 1-го курса факультета КНиИТ, группа № 121, Жучков Андрей Сергеевич Саратовский государственный университет им. Н.Г ...
Теорема 6. Для того, чтобы граф был эйлеровым, необходимо и достаточно, чтобы он был связным и все его вершины имели четную степень.
Теорема 7. Для того чтобы на связном графе можно было бы проложить цепь АВ, содержащую все его ребра в точности по одному разу, необходимо и достаточно, чтобы А и В были ...
Раздел: Рефераты по математике
Тип: реферат Просмотров: 6617 Комментариев: 6 Похожие работы
Оценило: 5 человек Средний балл: 3.6 Оценка: неизвестно     Скачать
Основы дискретной математики
Федеральное агентство по образованию Новомосковский институт (филиал) Государственного образовательного учреждения высшего профессионального ...
Цикл, в котором каждое ребро графа G участвует всего один раз, называется эйлеровым циклом.
Любой из вариантов 1-4 содержит каждое ребро графа, следовательно, длина одинакова для всех циклов 1-4. Длина эйлерова цикла не зависит от того, какая вершина будет выбрана за ...
Раздел: Рефераты по информатике, программированию
Тип: учебное пособие Просмотров: 4172 Комментариев: 2 Похожие работы
Оценило: 0 человек Средний балл: 0 Оценка: неизвестно     Скачать
Задача остовных деревьев в k-связном графе
... Молдавский Государственный Университет Кафедра Информатики и Дискретной Оптимизации Дипломная работа: "Задача остовных деревьев в k-связном графе"
Из классического результата теории графов - теоремы Менгераизвестно, что для любых двух вершин x и y графа G локальная реберная связность (x, y, G) равняется наибольшему количеству ...
Предположим, что теорема доказана для любого 2k- реберно связного мультиграфа, у которого меньше вершин, чем у G. По теореме 7.2, у графа G(V, E) существует остовный подграф G0(V ...
Раздел: Рефераты по математике
Тип: реферат Просмотров: 1728 Комментариев: 2 Похожие работы
Оценило: 0 человек Средний балл: 0 Оценка: неизвестно     Скачать
AGraph: библиотека классов для работы с помеченными графами
1. Актуальность разработки библиотек для работы с графами К настоящему времени накоплен большой опыт решения теоретико-графовых задач на ЭВМ ...
Вершины могут либо храниться в отдельном списке, либо только в составе инцидентных им ребер (в случае связных графов).
/ присваивание значений атрибутам вершины v и ребра e графа G
Раздел: Рефераты по информатике, программированию
Тип: курсовая работа Просмотров: 1852 Комментариев: 2 Похожие работы
Оценило: 0 человек Средний балл: 0 Оценка: неизвестно     Скачать
Шпаргалки по геометрии, алгебре, педагогике, методике математики (ИГПИ ...
Кольцом называется числ. множ. На котором выполняются три опер-ии: слож, умнож, вычит. Полем наз. Числ множ. На котором выполняются 4 операции: слож ...
Формула Эйлера: e-число вершин m-число ребер одной грани
Последнее находится в отношении соподчинения; отношения противоречия - понятия отрицают друг друга (четные и нечетные и т.д.); отношения противоположности - в этом отношении ...
Раздел: Рефераты по математике
Тип: реферат Просмотров: 3490 Комментариев: 3 Похожие работы
Оценило: 3 человек Средний балл: 3 Оценка: неизвестно     Скачать
Алгоритмический язык Паскаль
МИНИСТЕРСТВО ОБРАЗОВАНИЯ РОССИЙСКОЙ ФЕДЕРАЦИИ ЧЕРЕПОВЕЦКИЙ ГОСУДАРСТВЕННЫЙ ПЕДАГОГИЧЕСКИЙ ИНСТИТУТ им. А.В. ЛУНАЧАРСКОГО КАФЕДРА ИНФОРМАТИКИ Дипломная ...
3) если вершина В находится на графе ниже А, то В называется ПОТОМКОМ, а А - ПРЕДКОМ В;
Выделяют из всех деревьев так называемые УПОРЯДОЧЕННЫЕ деревья - такие, у которых ребра (т.е. соответствующие им элементы), выходящие из каждой вершины, упорядочены по какому-либо ...
Раздел: Рефераты по информатике, программированию
Тип: дипломная работа Просмотров: 2870 Комментариев: 2 Похожие работы
Оценило: 1 человек Средний балл: 4 Оценка: неизвестно     Скачать

Все работы, похожие на Курсовая работа: Эйлеровы графы (3585)

Назад
Меню
Главная
Рефераты
Благодарности
Опрос
Станете ли вы заказывать работу за деньги, если не найдете ее в Интернете?

Да, в любом случае.
Да, но только в случае крайней необходимости.
Возможно, в зависимости от цены.
Нет, напишу его сам.
Нет, забью.



Результаты(150314)
Комментарии (1830)
Copyright © 2005-2016 BestReferat.ru bestreferat@mail.ru       реклама на сайте

Рейтинг@Mail.ru