Теория графов

Размещено на http://www.allbest.ru/

Введение

Первая работа по теории графов, принадлежащая известному швейцарскому математику л. Эйлеру, появилась в 1736г. Вначале теория графов казалась довольно незначительным разделом математики, так как она имела дело в основном с математическими развлечениями и головоломками. Однако дальнейшее развитие математики и особенно ее приложений дало сильный толчок развитию теории графов. Уже в XIX столетии графы использовались при построении схем электрических цепей и молекулярных схем. В настоящее время можно узнать и главы чистой математики, например теория математических отношений, в которых теория графов служит естественным аппаратом; с другой стороны, эта теория находит многочисленные применения в разнообразных практических вопросах: при установлении разного рода соответствий, при решении транспортных задач, задач о потоках в сети нефтепроводов и вообще в так называемом «программировании». Теория графов теперь применяется и в таких областях, как экономика, психология и биология. Математические развлечения и головоломки тоже остаются частью теории графов, особенно если отнести к ним знаменитую проблему четырех красок, интригующую математиков и по сей день.

В математике теория графов рассматривается как одна из ветвей топологии; непосредственное отношение она имеет также к алгебре и к теории чисел.

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

Краткие характеристики ПК

Система: Пользователь:

Microsoft Windows XP User

Professonal Home

Версия 2002 76456-640-8365391-23226

Servise Pask 3

Компьютер: Intel (R) Celeron (R) CPU 2. 80GHz 2.81 Ггц, 256 МБ ОЗУ

Введение

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

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

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

Многие задачи теории графов относятся к возвратным, решение которых основано на свойстве возвратности (или рекуррентности), согласно которому решение всей задачи зависит от решений той же самой задачи меньших размеров. Истоки теории возвратных задач восходят к «нечисловому анализу» алгоритмов вычислений для ЭВМ.

1. Теоретическая часть

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

терия граф эйлеров гамильтонов

Графом G называется пара (V (G), E (G)), где V (G) - непустое конечное множество элементов, называемых вершинами, а E(G) - конечное семейство неупорядоченных пар элементов из V (G) (необязательно различных), называемых ребрами. Употребление слова «семейство» говорит о том, что допускаются кратные ребра. Будем называть V(G) - семейством ребер графа G. О каждом ребре вида ( v,w) говорят, что оно соединяет вершины v и w. Каждая петля (v,v) соединяет вершину v саму с собой.

При изображении графов на рисунках или схемах отрезки могут быть прямолинейными или криволинейными; длины отрезков и расположение точек произвольны.

Орграфом D называется пара (V(D), A(D)), где V(D) - непустое конечное множество элементов, называемых вершинами, а A(D) - конечное семейство упорядоченных пар элементов из V(D), называемых дугами (или ориентированными ребрами). Дуга, у которой вершина v является первым элементом, а вершина w - вторым, называется дугой из v в w (v,w). Заметим, что дуги (v,w) и (w,v) различны. Хотя графы и орграфы - существенно различные объекты, в определенных случаях графы можно рассматривать как орграфы, в которых каждому ребру соответствуют две противоположные ориентированные дуги.

Граф называется полным, если каждые две различные вершины его соединены одним и только одним ребром. В полном графе каждая его вершина принадлежит одному и тому же числу ребер. Для задания полного графа достаточно знать число его вершин. Полный граф с n вершинами обычно обозначается через Kn.

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

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

Является граф полным или нет, это его характеристика в целом.

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

Рассмотрим соревнование, в котором каждая их команд играет с каждой из остальных команд по одному разу. Такое соревнование называют круговым турниром или турниром в один круг.

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

( v, w )

Каждому турниру соответствует полный ориентированный граф, в котором вершины представляют команды, а каждое ориентированное ребро (v,w) выражает отношение «v победила w».

Допустим, что множество вершин графа можно разбить на два непересекающихся подмножества V1 и V2, так, что каждое ребро в G соединяет какую-нибудь вершину из V1 с какой-нибудь вершиной из V2, тогда G называется двудольным графом. Такие графы иногда обозначают G(V1, V2), если хотят выделить два указанных подмножества. Двудольный граф можно определить и по-другому: в терминах раскраски его вершин двумя цветами, красным и синим. При этом граф называется двудольным, если каждую его вершину можно окрасить красным или синим цветом так, чтобы любое ребро имело один конец красный, а другой - синий. Следует подчеркнуть, что в двудольном графе совсем не обязательно каждая вершина из V1 соединена с каждой вершиной из V2; если же это так и если при этом граф G простой, то он называется полным двудольным графом и обычно обозначается Km,n, где m, n - число вершин соответственно в V1 и V2 . Например: K4,3 K1,5 - звездный граф

Размещено на http://www.allbest.ru/

Заметим, что граф Km,n имеет ровно m + n вершин и nm ребер.

Вершины в графе могут отличаться друг от друга тем, скольким ребрам они принадлежат.

Степенью вершины называется число ребер графа, которым принадлежит эта вершина. Вершина называется четной, если ее степень - число четное. Вершина называется нечетной, если ее степень - число нечетное. Две вершины графа называются смежными, если существует соединяющее их ребро, то есть ребро вида (v,w); при этом вершины v и w называются инцидентными этому ребру, а ребро - инцидентным этим вершинам. Аналогично, два различных ребра графа называются смежными, если они имеют, по крайней мере, одну общую вершину. Иначе можно определить степень вершины. Степенью или валентностью вершины v графа G называется число ребер, инцидентных v; степень вершины будем обозначать через p(v). При вычислении степени вершины v будем учитывать петлю в v два раза, а не один. Вершина степени 0 называется изолированной вершиной, вершина степени 1 называется висячей, или концевой, вершиной. Граф, у которого все вершины имеют одну и ту же степень, называется регулярным графом.

Два графа G1 и G2, называются изомофорными, если существует взаимно однозначное соответствие между множествами их вершин, обладающее тем свойством, что число ребер, соединяющих любые две вершины в G1 равно числу ребер, соединяющих соответствующие вершины в G2.

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

1. В графе G сумма степеней всех его вершин - число четное, равное удвоенному числу ребер графа, так как каждое ребро участвует в этой сумме ровно два раза. Этот результат, известный еще двести лет назад Эйлеру, часто называют леммой о рукопожатиях. Из нее следует, что если несколько человек обменялись рукопожатиями, то общее число пожатых рук обязательно четно, ибо в каждом рукопожатии участвуют две руки. (при этом каждая рука считается столько раз, сколько она участвовала в рукопожатиях).

2. Число нечетных вершин любого графа четно.

3. Во всяком графе с n вершинами, где n>2, всегда найдутся по меньшей мере две вершины с одинаковыми степенями.

4. Если в графе с вершинами n>2 в точности две вершины имеют одинаковую степень, то в этом графе всегда найдется либо в точности одна вершина степени 0, либо в точности одна вершина степени n -1.

Граф называется связным, если его нельзя представить в виде объединения двух графов, и несвязным - в противном случае.

Маршрутом в данном графе G называется конечная последовательность ребер вида

(v0, v1), (v1, v2), …, (vm-1 , vm)

(обозначаемая также через v0 , v1 ,v2 ,…,vm). Очевидно следующее свойство маршрута: любые два последовательных ребра либо смежны, либо одинаковы. Но не всякая последовательность ребер, обладающая этим свойством, является маршрутом (в качестве примера рассмотрим звездный граф и возьмем его ребра в произвольном порядке). Каждому маршруту соответствует последовательность вершин v0, v1…vm. v0 называется начальной вершиной, а vm конечной вершиной маршрута. Таким образом, будем говорить о маршруте из v0 в v0. Длиной маршрута называется число ребер в нем. Маршрут называется цепью, если все его ребра различны, и простой цепью, если все вершины v0,…, vm различны, кроме v0 =vm. Замкнутая простая цепь, содержащая по крайней мере одно ребро, называется циклом. В частности, любая петля или любая пара кратных ребер образует цикл. Путь (последовательность ребер, ведущая от к e1 к e2, в которой каждые два соседних ребра имеют общую вершину и никакое ребро не встречается более одного раза) от вершины e1 до вершины e2 называется простым, если он не проходит ни через одну из вершин графа более одного раза.

Граф G называется связным, если для любых двух его вершин v и w существует простая цепь из v в w. Любой граф можно разбить на непересекающиеся связные графы, называемые компонентами (связности) графа G. Таким образом, несвязный граф имеет две компоненты. Две вершины эквивалентны (или связны), если существует простая цепь из одной в другую. Связный граф состоит из одной компоненты. Граф называется несвязным, если число его компонент больше единицы. Связный граф представляет собой простой цикл тогда, когда каждая его вершина имеет степень 2.

1.2 Представления о планарном графе

Плоским графом называется граф, изображенный на плоскости так, что никакие два его ребра (представляющие их кривые) геометрически не пересекаются нигде, кроме инцидентной им обоим вершины.

Размещено на http://www.allbest.ru/

Граф, изомофорный плоскому графу, называется планарным. Планарный граф можно определить еще так: граф планарен, если его можно уложить на плоскости. Рисунок графа, в котором никакие два его ребра не пересекаются, если не считать точками пересечения общие вершины, называют плоским представлением графа. Ясно, что плоское представление имеет только плоский граф. Обратно, у всякого плоского графа непременно найдется плоское представление. Плоские графы - это простые циклы, деревья, лес, а также граф, содержащий цикл, из вершин которого «выходят» деревья Деревья - связные графы, в которых существует одна и только одна цепь, соединяющая каждую пару вершин..

В качестве характеристики плоского представления графа вводится понятие грани. Гранью в плоском представлении графа G называется часть плоскости, ограниченная простым циклом и не содержащая внутри других циклов.

На рисунке 1 показано плоское представление графа G с тремя гранями: (1,5,4,1), (1,3,2,4,1), (1,2,3,1). Часть плоскости, ограниченная простым циклом (1,2,4,1), гранью не является, так как содержит цикл (1,2,3,1). Простой цикл, ограничивающий грань, называется границей грани. Две грани называются соседними, если их границы имеют хотя бы одно общее ребро.

Размещено на http://www.allbest.ru/

рис 1

В данном графе часть плоскости, ограниченная

Размещено на http://www.allbest.ru/

простым циклом (1,2,3,4,5,1), является гранью,

так как ребро (4,5), расположенное внутри грани,

не образует цикла. Не является гранью заштрихованная часть плоскости в данном примере (рис 2), так как она содержит цикл, да к тому же эта часть плоскости не ограничена циклом. Ребро (1,2) является мостом, соединяющим циклы. Такие мосты называются перегородками.

Размещено на http://www.allbest.ru/

рис 2

В качестве грани можно рассматривать и часть плоскости, расположенную «вне» плоского представления графа. Она ограничена «изнутри» простым циклом и не содержит других циклов. Эту часть плоскости называют бесконечной гранью.

Размещено на http://www.allbest.ru/

рис 3

На рисунке 3 часть бесконечной грани заштрихована. Всякое плоское представление графа либо не имеет бесконечной грани, либо имеет в точности одну бесконечную грань. Как особый случай вводится бесконечная грань в плоском представлении дерева и леса. В плоском представлении дерева и леса за грань принимают всю плоскость рисунка. Два графа гомеоморфны (или тождественны с точностью до вершин степени 2), если они оба могут быть получены из одного и того же графа «включением» в его ребра новых вершин степени 2.

Размещено на http://www.allbest.ru/

рис 4

Изображенные графы на рисунке 4 гомеоморфны, и то же самое можно сказать о любых двух циклических графах. Гомеоморфность графов является отношением эквивалентности. Ясно, что введение термина «гомеоморфны» удобно только с технической точки зрения - включение или удаление вершин степени 2 не имеет никакого отношения к планарности. Добавление (включение) одной вершины v в какое-нибудь ребро, например e, осуществляется следующим образом: пусть ребро e инцидентно вершинам w и x. Тогда ребро e удаляется из графа, но добавляются два новых ребра: e1 инцидентное вершинам v и w, и e2, инцидентное вершинам v и x.

Введение понятия гомеоморфности графов позволяет установить следующий важный результат, известный как теорема Куратовского (точнее, как теорема Понтрягина-Куратовского, так как Л.С. Понтрягин доказал, но не опубликовал, эту теорему еще в 1927 году), который дает необходимое и достаточное условие планарности графа.

1.3 Гомеоморфные графы

Теорема (Куратовский 1930). Граф планарен тогда, когда не содержит подграфов, гомеоморфных K5 или K3.3.

Поскольку доказательство теоремы Куратовского довольно длинное и сложное, здесь оно не приводится. Тем не менее, воспользуемся теоремой Куратовского для получения другого критерия планарности. Рассмотрим еще два определения. Элементарным стягиванием называется такая процедура: берем ребро e (вместе с инцидентными ему вершинами, например, v и w) и «стягиваем» его, то есть удаляем e и отождествляем v и w.

Полученная при этом вершина инцидентна тем ребрам (отличным от e), которым первоначально были инцидентны v и w.

Размещено на http://www.allbest.ru/

рис 5

На рисунке 5 граф G называется стягиваемым к графу H, если H можно получить из G с помощью некоторой последовательности элементарных стягиваний.

Граф планарен тогда, когда он не содержит подграфов, стягиваемых в К5 или к К3,3.

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

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

Связный граф G называется эйлеровым, если существует замкнутая цепь, проходящая через каждое его ребро. Такая цепь называется эйлеровой цепью. Отметим, что в этом определении требуется, чтобы каждое ребро проходилось только один раз. Если снять ограничение на замкнутость цепи, то граф называется полуэйлеровым, при этом каждый эйлеров граф будет полуэйлеровым. (рис 6).

Размещено на http://www.allbest.ru/

Эйлеров граф Полуэйлеров граф Не эйлеров граф

Рис 6

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

Задачи с эйлеровыми графами часто встречаются в книгах по занимательной математике - например, можно ли нарисовать какую-нибудь диаграмму, не отрывая карандаш от бумаги и не проходя никакую линию дважды. Название «эйлеров» возникло в связи с тем, что Эйлер первым решил знаменитую задачу о Кенигсберских мостах, в которой нужно было узнать, имеет ли некоторый граф эйлерову цепь.

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

1.5 Гамильтоновы графы

Рассмотрим проблему существования замкнутой цепи, проходящей ровно один раз через каждую вершину графа G. (рис 7)

Размещено на http://www.allbest.ru/

Гамильтонов граф Полугамильтонов граф Не гамильтонов граф

Рис 7

Ясно, что такая цепь должна быть циклом, исключая тривиальный случай, когда G является графом N1. Если такой цикл существует, то он называется гамильтоновым циклом (путем), а G называется гамильтоновым графом. Граф, который содержит простую цепь, проходящую через каждую его вершину, называется полугамильтоновым. Название «гамильтонов цикл» возникло в связи с тем, что У. Гамильтон занимался исследованием существования таких циклов в графе, соответствующем додекаэдру. Додекаэдр - это многогранник, гранями которого служат 12 правильных пятиугольников. У него 20 вершин и 30 ребер.

Эйлеровы и гамильтоновы пути сходны по способу задания. Первые содержат все ребра, по одному разу каждое, вторые - все вершины, по одному разу каждую. Но, несмотря на внешнее сходство, задачи их поиска резко отличаются по степени трудности. Для решения вопроса о наличии эйлерова цикла в графе достаточно выяснить, все ли его вершины четны. Критерий же существования гамильтонова графа в произвольном графе еще не найден. Решение этой проблемы имеет практическую ценность, так как в игре Гамильтона близка известная задача о коммивояжере, который должен объехать несколько пунктов и вернуться обратно. Он обязан побывать в каждом пункте в точности по одному разу и заинтересован в том, чтобы затратить на поездку как можно меньше времени. А для этого требуется определить все варианты посещения городов и подсчитать в каждом случае затрату времени. По своей математической постановке игра Гамильтона близка к задаче переналадке станков, задаче о подводке электроэнергии к рабочим местам и т.д.

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

2.1 Общая характеристика задачи

Агентство по грузоперевозкам «Летучий голландец» представляет услуги по перевозке грузов по различным маршрутам. Данные о маршрутах, выполненных в течение недели, по каждому водителю приведены на рисунке. Справочные данные о технических характеристиках автомобилей и протяженности маршрутов приведены на рисунке.

1. Построить таблицы по приведенным ниже данным.

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

3. Организовать межтабличные связи для автоматического формирования ведомости расхода топлива за неделю.

4. Сформировать и заполнить ведомость расхода горючего каждым водителем за неделю.

5. Результаты расчета количества израсходованного топлива за неделю представить в графическом виде.

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

2.2 Описание алгоритма задачи

1. Заполняется таблица «Сведения о выполненных маршрутах».

Для этого рассчитывается сколько израсходовано топлива.

Израсходовано топлива = Протяженность рейса* Расход топлива/100

КАМАЗ (А112)= 420*45/100=189

ЗИЛ (С431) = 250*42/100=105

МАЗ (А112) = 420*53/100 = 222,6

МАЗ (М023) = 225*53/100 = 119,25

КАМАЗ (С431)= 250*45/100 = 130,2

КАМАЗ (В447)= 310*45/100 = 139,5

Далее рассчитывается вес перевезенного груза.

Вес перевезенного груза= выполнено рейсов*грузоподъемность

КАМАЗ (А112) = 16*4=64

ЗИЛ (С431) = 3*7=21

МАЗ (А112) = 5*12 = 60

МАЗ (М023) = 7*12 = 84

ЗИЛ (В447) = 2*7 = 14

КАМАЗ (С431) = 8*16 = 128

КАМАЗ (В447) = 4*16 = 64

2. На основе подсчитанных данных заполняется ведомость расхода горючего (стр 19)

Заключение

Начало теории графов относится к 1736 г., когда Л. Эйлер не только решил популярную в то время задачу о кенигсбергских мостах, но и нашел критерий существования в графе специального маршрута (эйлерова цикла). Однако этот результат более ста лет оставался единственным результатом теории графов. Лишь в середине XIX в. инженер-электрик Г. Кирхгоф разработал теорию деревьев для исследования электрических цепей, а математик А. Кэли в связи с описанием строения углеводородов решил задачи для тех типов деревьев.

Родившись при решении головоломок и занимательных игр (задачи о шахматном коне, о ферзях, «кругосветное путешествие», задачи о свадьбах и гаремах и т.п.), теория графов стала в настоящее время простым, доступным и мощным средством решения вопросов, относящихся к широкому кругу проблем. Графы буквально вездесущи. В виде графов можно, например, интерпретировать схемы дорог и электрические цепи, географические карты и молекулы химических соединений, связи между людьми и группами людей.

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

Размещено на Allbest.ru