Применение теории графов в информатике

Тема: Применение теории графов в информатике

Раздел: Бесплатные рефераты по информатике

Тип: Курсовая работа | Размер: 5.70M | Скачано: 308 | Добавлен 21.01.13 в 20:59 | Рейтинг: +1 | Еще Курсовые работы

Вуз: ВЗФЭИ

Оглавление

Введение 3

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

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

1.2. Основные теоремы теории графов 6

1.3. Способы и требования к представлению графов в компьютере 8

1.4. Типовые задачи теории графов 10

Заключение 12

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

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

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

Список используемой литературы 20

 

Введение

Родоначальником теории графов считается Леонард Эйлер. В 1736 г. в одном из своих писем он формулирует и предлагает решение задачи о семи кёнигсбергских мостах, ставшей впоследствии одной из классических задач теории графов.Он смог найти правило, пользуясь которым легко определить, можно ли пройти по всем мостам, не проходя дважды ни по одному из них.

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

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

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

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

 

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

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

Теория графов — раздел дискретной математики, изучающий свойства графов.

В общем смысле граф представляется как множество вершин (узлов), соединённых рёбрами. Таким образом, ребро определяется парой вершин. Два ребра, у которых есть общая вершина называются смежными (или соседними). В строгом определении граф -это пара множеств G=(V,E), где V есть подмножество любого счётного множества, а E — подмножество V×V.

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

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

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

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

Контур – это цикл без повторения вершин, за исключением первой вершины, совпадающей с последней.

Последовательности вершин (рис. 1): 1–2–3–4–2–5 не простой путь, а маршрут; последовательности 1–2–3–4–7–5 и 1–2–5 – простые пути; 1–2–3–4–2–5–6–1 –это цикл (но не контур); 1–2–5–6–1 – это контур[3, стр.29—31].

Если имеется некоторый маршрут из вершины t в вершину s, заданный в виде последовательности ребер, которые в этом случае приобрели направление, и если в этот маршрут входит ребро, соединяющее вершины (i, j), то это ребро по отношению к вершине i называют иногда прямой дугой, а по отношению к вершине j – обратной дугой (или обратным ребром).

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

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

Теория графов находит применение, например, в геоинформационных системах (ГИС). Существующие или вновь проектируемые дома, сооружения, кварталы и т. п. рассматриваются как вершины, а соединяющие их дороги, инженерные сети, линии электропередачи и т. п. — как рёбра. Применение различных вычислений, производимых на таком графе, позволяет, например, найти кратчайший объездной путь или ближайший продуктовый магазин, спланировать оптимальный маршрут.

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

 

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

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

Теорема 1.Удвоенная  сумма степеней вершин любого графа равна   числу его ребер. [4, стр. 66]

Доказательство. Пусть А₁, А₂, А₃, ...,A_n — вер­шины данного графа, ap(A₁), p(А₂), ...,p(A_n) – степени этих вершин. Подсчитаем число ребер, сходящихся в каждой вершине, и просуммируем эти числа. Это рав­носильно нахождению суммы степеней всех вершин. При таком подсчете каждое ребро будет учтено дважды (оно ведь всегда соединяет две вершины).

Отсюда следует: p(A₁)+p(А₂)+ ...+p(A_n)=0,5N,или 2(p(A₁)+p(А₂)+ ...+p(A_n))=N , где N— число ребер.

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

Следствие 1. Нечетное число знакомых в любой компании всег­да четно.

Следствие 2. Число вершин многогранника, в которых сходится нечетное число  ребер,  четно.

Следствие 3. Число всех людей, когда-либо пожавших руку дру­гим людям, нечетное число раз, является четным.

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

Теорема 4.Если в графе с nвершинами (nбольше или равно 2) только одна пара имеет одинаковуюстепень, то в этом графе всегда найдется либо единственная изолированная вершина, либо единственная вершина, соединенная со всеми другими.

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

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

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

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

Теорема 9.Различных деревьев с n перенумерованными вершинами можно построить   n^n-2.

Теорема 10.Полный граф с пятью верши­нами не является плоским.

Теорема 11. (Теорема Понтрягина-Куратовского) Граф является плоским тогда и только тогда, когда он не имеет в качестве подграфа полного графа с пятью вершинами.

 

Способы и требования к представлению графов в компьютере

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

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

Далее приведены четыре наиболее часто используемых представления с указанием характеристики n(p,q) – объема памяти для каждого представления. Здесь p – число вершин, а q – число ребер.

Матрица смежности

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

Для матрицы смежности n(p,q) = O(p²).

Матрица смежности неориентированного графа симметрична относительно главной диагонали, поэтому достаточно хранить только верхнюю (или нижнюю) треугольную матрицу.

Матрица инциденций

Представление графа с помощью матрицы H, отражающей инцидентность вершин и ребер, называется матрицей инциденций, где для неориентированного графа

а для орграфа

Для матрицы инциденцийn(p,q) = O(pq).

Списки  смежности

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

N :record v : 1..p; n :↑ N end record,

называется списком смежности. В случае представления неориентированных графов списками смежности n(p,q) = O(p+2q), а в случае ориентированных графов n(p,q) = O(p+q).

Массив дуг

Представление графа с помощью массива структур

E :array [1..q] of record b,e : 1..p end record,

отражающего список пар смежных вершин, называется массивом ребер (или, для орграфов, массивом дуг). Для массива ребер (или дуг) n(p,q) = O(2q) [5].

 

Типовые задачи теории графов

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

Задача о кратчайшем пути. Пусть задана сеть из n + 1 вершины,  то  есть  ориентированный  граф,  в  котором  выделены две вершины  –  вход (нулевая  вершина)  и  выход (вершина  с  номером n). Для каждой дуги заданы числа, называемые длинами дуг. Длиной  пути  (контура)  называется  сумма  длин  входящих  в  него  дуг, если длины дуг не заданы, то длина пути (контура) определяется как  число  входящих  в  него  дуг).  Задача  заключается  в  поиске кратчайшего пути (пути минимальной длины) от входа до выхода сети1 Известно, что для существования кратчайшего пути необходимо и достаточно отсутствия в сети контуров отрицательной длины. Предположим,  что  в  сети  нет  контуров.  Тогда  всегда  можнопронумеровать  вершины  таким образом, что для любой дуги (i, j) имеет место  j > i. Такая  нумерация называется  правильной. Легко показать,  что  в  сети  без  контуров  всегда  существует  правильная нумерация.

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

Алгоритмы  решения  задачи  о  кратчайшем  пути  позволяют решать широкий класс задач дискретной оптимизации. В качестве примера  приведем  задачу  целочисленного  линейного  программирования –  задачу о ранце  (о рюкзаке), к которой  сводятся многие практически важные задачи определения оптимальной комбинации факторов при ограничениях на общий вес, площадь, объем, финансирование и т.д. [6, стр.34, 36]

         Существует ещё ряд типовых задач теории графов. Рассмотрим их краткую расшифровку:

1. Задача о максимальном потоке:

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

2. Раскраска в графах:

• распределение памяти в ЭВМ;
• проектирование сетей телевизионного вещания.

3. Связность графов и сетей:

• проектирование кратчайшей коммуникационной сети;
• синтез структурно-надежной сети циркуляционной связи;
• анализ надежности стохастических сетей связи.

4. Изоморфизм графов и сетей:

• структурный синтез линейных избирательных цепей;
• автоматизация контроля при проектировании БИС.

5. Автоморфизм графов:

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

 

Заключение

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

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

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

 

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

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

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

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

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

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

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

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

Сведения о выполненных маршрутах
№ п/п	ФИО водителя	Марка автомобиля	№ рейса	Выполнено рейсов, шт.	Протяженность рейса, км.	Расход топлива на 100 км, л	Израсходовано топлива, л	Грузоподъемность, т	Вес перевезенного груза, т
1	Соловьев В.В.	КАМАЗ	А112	4
2	Михайлов С.С.	ЗИЛ	С431	3
3	Кузнецов Я.Я.	МАЗ	А112	5
4	Иванов К.К.	МАЗ	М023	7
5	Сидоров А.А.	ЗИЛ	В447	2
6	Волков Д.Д.	КАМАЗ	С431	8
7	Быков Л.Л.	КАМАЗ	В447	4
	ИТОГО	Х	Х
	В СРЕДНЕМ	Х	Х

Рис. 1. Данные о выполненных маршрутах

Технические характеристики автомобилей
№ п/п	Марка автомобиля	Расход топлива на 100 км, л	Грузоподъемность, т
1	ЗИЛ	42	7
2	КАМАЗ	45	16
3	МАЗ	53	12

Протяженность рейсов
№ п/п	№ рейса	Протяженность рейса, км
1	А112	420
2	В447	310
3	М023	225
4	С431	250

Рис. 2 Данные о технических характеристиках автомобилей и данные о протяженности рейсов

ФИО водителя № рейса Выполнено рейсов, шт Израсходовано топлива, л Соловьев В.В. А112     Михайлов С.С. С431     Кузнецов Я.Я. А112     Иванов К.К. М023     Сидоров А.А. В447     Волков Д.Д. С431     Быков Л.Л. В447     ИТОГО         Бухгалтер _________________________

Рис.3 ведомость расхода горючего

 

Описание алгоритма решения задачи  смотрите в файле

 

Список используемой литературы

1. БурковВ.Н.,ЗаложневА.Ю.,НовиковД.А.Теорияграфоввуправлении организационными системами. М.: Синтег, 2001. – 124 с
2. Ивушкин Г.В., Способы представления графов в компьютере. -http://www.cross-kpk.ru/ims/00408/page20.html
3. Кордемский Б.А., Математическая смекалка – М.: Физматгиз, 1954 – 326 с.
4. Кук Д., Бейз Г., Компьютерная математика. – М.: Наука, 1990 – 315с.
5. Самохин А. В. Проблема четырех красок: неоконченная история доказательства – СОЖ:2000. - № 7. – 253с
6. Оре О. Теория графов. — 2-е изд. — М.: Наука, 1980 — С. 336.
7. Рабкин Е.Л., Фарфоровская Ю.Б. Дискретная математика – М.: Просвещение, 2005 – 465с

---

Понравилось? Нажмите на кнопочку ниже. Вам не сложно, а нам приятно).

---

Чтобы скачать бесплатно Курсовые работы на максимальной скорости, зарегистрируйтесь или авторизуйтесь на сайте.

Важно! Все представленные Курсовые работы для бесплатного скачивания предназначены для составления плана или основы собственных научных трудов.

---

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

Добавить работу

---

Если Курсовая работа, по Вашему мнению, плохого качества, или эту работу Вы уже встречали, сообщите об этом нам.

---

Добавление отзыва к работе

Добавить отзыв могут только зарегистрированные пользователи.

---

Похожие работы

• Применение теории графов в информатике (понятия, задачи)
• Применение теории графов в информатике