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

ЛИЧНЫЙ КАБИНЕТ 

 

Здравствуйте гость!

 

Логин:

Пароль:

 

Запомнить

 

 

Забыли пароль? Регистрация

Повышение уникальности

Предлагаем нашим посетителям воспользоваться бесплатным программным обеспечением «StudentHelp», которое позволит вам всего за несколько минут, выполнить повышение уникальности любого файла в формате MS Word. После такого повышения уникальности, ваша работа легко пройдете проверку в системах антиплагиат вуз, antiplagiat.ru, etxt.ru или advego.ru. Программа «StudentHelp» работает по уникальной технологии и при повышении уникальности не вставляет в текст скрытых символов, и даже если препод скопирует текст в блокнот – не увидит ни каких отличий от текста в Word файле.

Результат поиска


Наименование:


Курсовик Основные понятия теории графов. Маршруты и связность. Задача о кёнигсбергских мостах. Эйлеровы графы. Оценка числа эйлеровых графов. Алгоритм построения эйлеровой цепи в данном эйлеровом графе. Практическое применение теории графов в науке.

Информация:

Тип работы: Курсовик. Предмет: Математика. Добавлен: 23.12.2007. Сдан: 2007. Уникальность по antiplagiat.ru: --.

Описание (план):


24

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

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

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

ЭЙЛЕРОВЫ ГРАФЫ
Выполнила студентка 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).
· Направленный граф - это орграф, не имеющий симметричных пар ориентированных рёбер (рис.4).
· Помеченные графы (или перенумерованные), если его вершины отличаются одна от другой какими-либо пометками. В качестве пометок обычно используются буквы или целые числа.[6]
Степенью вершины vi в графе G называется число рёбер, инцидентных vi ,обозначается 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 называется чередующаяся последовательность вершин и рёбер v0,x1,v1,…vn-1,xn,vn; эта последовательность начинается и кончается вершиной, и каждое ребро последовательности инцидентно двум вершинам, одна из которых непосредственно предшествует ему, а другая непосредственно следует за ним. Указанный маршрут соединяет вершины v0 и vn и его можно обозначить v0v1v2vn (наличие рёбер подразумевается). Эта последовательность иногда называется (v0-vn)-маршрутом. Маршрут замкнут, если v0=vn, и открыт в противном случае. Маршрут называется цепью, если все его рёбра различны, и простой цепью, если все вершины (а следовательно, и рёбра ) различны. Замкнутая цепь называется циклом. Замкнутый маршрут называется простым циклом, если все его n вершин различны и n3.
Граф G называется связным, если любая пара его вершин соединена простой цепью.[6]

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

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

Рис.5.

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

Для доказательства того, что задача не имеет решения, Эйлер обозначил каждую часть суши точкой (вершиной), а каждый мост - линией (ребром), соединяющей соответствующие точки. Получился “граф”. Этот граф показан на рисунке 6, где точки отмечены теми же буквами, что и четыре части суши на рисунке 5.
Рис.6.
Утверждение о не существовании “положительного” решения у этой задачи эквивалентно утверждению о невозможности обойти специальным образом граф, представленный на рисунке 6.
Отправляясь от этого частного случая Эйлер обобщил постановку задачи и нашёл критерий существования обхода у данного графа, а именно граф должен быть связным и каждая его вершина должна быть инцидентна чётному числу рёбер.[6]

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

Решение Эйлером задачи о Кёнигсбергских мостах привела к первой опубликованной работе по теории графов. Задачу об обходе мостов можно обобщить и получить следующую задачу теории графов: можно ли найти в данном графе G цикл, содержащий все вершины и все рёбра? Граф, в котором это возможно, называется эйлеровым. Таким образом, эйлеров граф имеет эйлеров цикл - замкнутую цепь, содержащую все вершины и все рёбра. Ясно, что эйлеров граф должен быть связным.[6]
Если снять ограничения на замкнутость цепи, то граф называется полуэйлеровым.
Теорема 1(критерий):
Граф с более чем одной вершиной имеет эйлеров цикл тогда и только тогда, когда он связный и каждая его вершина имеет чётную степень.
Доказательство: Предположим, что граф G имеет эйлеров цикл. Граф является связным, так как каждая вершина принадлежит циклу. Для всякой вершины v графа G каждый раз, когда эйлеров цикл проходит через v, он вносит 2 в степень v. Поэтому степень v чётная.
Обратно, нужно показать, что каждый связный граф, у которого степени вершин чётные, имеет эйлеров цикл. Докажем эту теорему, используя индукцию по числу вершин. Поскольку теорема тривиально справедлива при n3, начнём индукцию с n=3. Предположим, что каждый связный граф, имеющий менее k вершин, и все вершины которого обладают чётной степенью, содержит эйлеров цикл. Пусть G - связный граф, содержащий k вершин, степени которых чётные. Допустим, что v1 и v2 - вершины графа G. Поскольку граф G - связный, существует путь из v1 в v2 .Поскольку степень v2 - чётная, существует неиспользованное ребро, по которому можно продолжить путь. Поскольку граф конечный, то путь, в конце концов, должен вернуться в v1 , и эйлеров цикл С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) обладает эйлеровым циклом. Начнём его из вершины А по ребру (А,В). Заканчивается путь тоже в вершине А. Если удалить теперь из полученного цикла ребро (А,В), то останется эйлеров путь с началом в В и концом в А или началом в А и концом В.
Таким образом, всякую замкнутую фигуру, имеющую в точности две нечётные вершины, можно начертить одним росчерком без повторений, начав в од и т.д.................


Перейти к полному тексту работы



Смотреть похожие работы


* Примечание. Уникальность работы указана на дату публикации, текущее значение может отличаться от указанного.