Реферат: Графы. решение практических задач с использованием графов (С++)

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ

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

им.Н.Г. ЧЕРНЫШЕВСКОГО

Кафедра теоретических основ информатики иинформационных технологий

ГРАФЫ. РЕШЕНИЕ ПРАКТИЧЕСКИХ ЗАДАЧ СИСПОЛЬЗОВАНИЕМ ГРАФОВ (С++)

Курсовая работа

Выполнил:студент1-го курса

факультета КНиИТ, группа №121,

специальность«Вычислительные машины, комплексы, системы и сети»

Жучков Андрей Сергеевич

Научный руководитель:

Седина Юлия Олеговна

Зав. Кафедрой ТОИиИТ

Профессор, академик РАЕН,д.т.н.

Сытник Александр Александрович

Саратов2005

СОДЕРЖАНИЕ

1.

Введение

2.

История возникновения теории графов

3.

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

4.

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

5.

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

6.

Обзор задач теории графов

7.

Заключение

8.

Список литературы

9.

Приложение А

10.Приложение Б

Введение

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

Историявозникновения теории графов.

Родоначальником теории графов принято считатьматематика Леонарда Эйлера (1707-1783). Однако теория графов многократнопереоткрывалась разными авторами при решении различных прикладных задач.

1.

Задача о Кенигсбергских мостах.На рис. 1 представлен схематический план центральнойчасти города Кенигсберг (ныне Калининград), включающий два берега реки Перголя,два острова в ней и семь соединяющих мостов. Задача состоит в том, чтобы обойтивсе четыре части суши, пройдя по каждому мосту один раз, и вернуться в исходнуюточку. Эта задача была решена (показано, что решение не существует) Эйлером в1736 году.

рис. 1

2.

Задача о трех домах и трех колодцах. Имеется три дома и три колодца, каким-то образомрасположенные на плоскости. Провести от каждого дома к каждому колодцу тропинкутак, чтобы тропинки не пересекались (рис. 2). Эта задача была решена (показано,что решение не существует) Куратовским в 1930 году.

SHAPE * MERGEFORMAT <img src="/cache/referats/20858/image003.gif" v:shapes="_x0000_s1063 _x0000_s1062 _x0000_s1081 _x0000_s1069 _x0000_s1067 _x0000_s1065 _x0000_s1066 _x0000_s1068 _x0000_s1080 _x0000_s1082 _x0000_s1083 _x0000_s1084 _x0000_s1085 _x0000_s1086 _x0000_s1087 _x0000_s1088 _x0000_s1089 _x0000_s1090 _x0000_s1091 _x0000_s1092 _x0000_s1093 _x0000_s1094 _x0000_s1095 _x0000_s1096 _x0000_s1097 _x0000_s1098 _x0000_s1099 _x0000_s1102 _x0000_s1103">

рис. 2

3.

Задача о четырех красках.Разбиение на плоскости на непересекающиеся областиназывается картой. Области на карте называются соседними, если они имеют общуюграницу. Задача состоит в раскрашивании карты таким образом, чтобы никакие двесоседние области не были закрашены одним цветом (рис. 3). С конца позапрошлоговека известна гипотеза, что для этого достаточно четырех красок. В 1976 годуАппель и Хейкен опубликовали решение задачи о четырех красках, котороебазировалось на переборе вариантов с помощью компьютера. Решение этой задачи«программным путем» явилось прецедентом, породившим бурную дискуссию, котораяотнюдь не закончена. Суть опубликованного решения состоит в том, чтобыперебрать большое, но конечное число (около 2000) типов потенциальныхконтрпримеров к теореме о четырех красках и показать, что ни один случайконтрпримером не является. Этот перебор был выполнен программой примерно затысячу часов работы суперкомпьютера. Проверить «вручную» полученное решениеневозможно – объем перебора выходит далеко за рамки человеческих возможностей.Многие математики ставят вопрос: можно ли считать такое «программноедоказательство» действительным доказательством? Ведь в программе могут бытьошибки… Методы формального доказательства правильности программ не применимы кпрограммам такой сложности, как обсуждаемая. Тестирование не можетгарантировать отсутствие ошибок и в данном случае вообще невозможно. Такимобразом, остается уповать на программистскую квалификацию авторов и верить, чтоони сделали все правильно.

Рис. 3

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

1)

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

2)

Ориентированнымназывается граф, в котором <img src="/cache/referats/20858/image006.gif" v:shapes="_x0000_i1028"> — множествоупорядоченных пар вершин вида (x,y), где xназываетсяначалом, а y– концом дуги. Дугу (x, y) частозаписывают как <img src="/cache/referats/20858/image008.gif" v:shapes="_x0000_i1029"><img src="/cache/referats/20858/image008.gif" v:shapes="_x0000_i1030">xквершине y, а вершина yсмежнаяс вершиной x.<img src="/cache/referats/20858/image011.gif" v:shapes="_x0000_i1031">

3)

Если элементом множества Eможет быть пара одинаковых(не различных) элементов V, то такойэлемент множества Eназывается петлей, а граф называется графомс петлями (или псевдографом).

4)

Если Eявляется немножеством, а набором, содержащимнесколько одинаковых элементов, то эти элементы называются кратными ребрами, а граф называется мультиграфом.

5)

Если элементами множества Eявляются не обязательно двухэлементные, а любые подмножества множества V, то такие элементы множества Eназываются гипердугами,а граф называется гиперграфом.

6)

Если задана функция F: V→ Mи/или F: E→ M, то множество Mназывается множеством пометок, а граф называется помеченным(или нагруженным). В качествемножества пометок обычно используются буквы или целые числа. Если функция Fинъективна, то есть разные вершины (ребра)имеют разные пометки, то графназывают нумерованным.

7)

Подграфом называется граф G′(V′,E′), где <img src="/cache/referats/20858/image013.gif" v:shapes="_x0000_i1032"><img src="/cache/referats/20858/image015.gif" v:shapes="_x0000_i1033">

a)

Если V′ = V, то G′называется остовным подграфом G.

b)

Если <img src="/cache/referats/20858/image017.gif" v:shapes="_x0000_i1034">G′называется собственным подграфомграфа G.

c)

Подграф G′(V′,E′) называется правильным подграфом графа G(V,E), если G′ содержитвсе возможные рёбра G.

8)

Степень(валентность)вершины – этоколичество ребер, инцидентных этой вершине (количество смежных с ней вершин).

9)

Маршрутом в графеназывается чередующаяся последовательность вершин и ребер <img src="/cache/referats/20858/image019.gif" v:shapes="_x0000_i1035">

a)

Если <img src="/cache/referats/20858/image021.gif" v:shapes="_x0000_i1036">замкнут,иначе открыт.

b)

Если все ребра различны, то маршрут называется цепью.

c)

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

d)

Замкнутая цепь называется циклом.

e)

Замкнутая простая цепь называется простымциклом.

f)

Граф без циклов называется ациклическим.

g)

Для орграфов цепь называется путем, а цикл – контуром.

SHAPE * MERGEFORMAT

V1 V2

V4 V5

рис. 4. Маршруты,цепи, циклы

Пример

В графе, диаграмма которогоприведена на рис.4:

1.

v1, v3, v1, v4– маршрут, но не цепь;

2.

v1, v3, v5, v2, v3, v4– цепь, но не простая цепь;

3.

v1, v4, v3, v2, v5– простая цепь;

4.

v1, v3, v5, v2, v3, v4, v1– цикл, но не простой цикл;

5.

v1, v3, v4, v1– простой цикл.

10)

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

11)

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

12)

Деревом называетсясвязный граф без циклов.

13)

Остовомназывается дерево, содержащее все вершины графа.

14)

Паросочетанием называетсямножество ребер, в котором никакие два не смежны.

15)

Паросочетаниеназывается максимальным, если никакоеего надмножество не является независимым.

16)

Две вершины вграфе связаны, если существуетсоединяющая их простая цепь.

17)

Граф, в которомвсе вершины связаны, называется связным.

18)

Граф, состоящийтолько из изолированных вершин, называется вполненесвязным.

19)

Длиной маршрутаназывается количество ребер в нем (с повторениями).

20)

Расстояниеммежду вершинами uи vназывается длина кратчайшей цепи <img src="/cache/referats/20858/image024.gif" v:shapes="_x0000_i1038">геодезической.

21)

Диаметром графаGназывается длина длиннейшей геодезической.

22)

Эксцентриситетомвершины vв связном графе G(V,E) называется максимальное расстояние от вершины vдо других вершин графа G.

23)

Радиусом графаGназывается наименьший из эксцентриситетов вершин.

24)

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

25)

Множество центральныхвершин называется центром графа.

SHAPE * MERGEFORMAT

2 2

3 3

3

4 4

3 3

рис.5 Эксцентриситеты вершин и центры графов (выделены).

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

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

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

Доказательство.Пусть А1, А2, А3,..., An—вершиныданного графа, ap(A1), p(А2),..., p(An) – степени этих вершин. Подсчитаем число ребер,сходящихся в каждой вершине, и просуммируем эти числа. Это равносильнонахождению суммы степеней всех вершин. При таком подсчете каждое ребро будетучтено дважды (оно ведь всегда соединяет две вершины).

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

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

Доказательство.Пусть a1, a2, a3,…, ak —это степени четных вершин графа, а b1, b2, b3,…, bm—степенинечетных вершин графа. Сумма a1+a2+a3+…+ak+b1+b2+b3+…+bmровнов два раза превышает число ребер графа.Сумма a1+a2+a3+…+akчетная (как сумма четных чисел), тогда сумма b1+b2+b3+…+bmдолжна быть четной. Это возможно лишь в том случае,если m—четное, то есть четным является и число нечетных вершин графа. Что итребовалось доказать.

Этатеорема имеет немало любопытных следствий.

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

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

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

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

Доказательство.Если граф имеет nвершин, то каждая из них может иметь степень0, 1, 2, ..., (n-1). Предположим, что в некотором графе все еговершины имеют различную степень, то есть, и покажем, что этого быть неможет. Действительно, если р(А)=0, то это значит, что А— изолированная вершина, и поэтому в графене найдется вершины Х со степенью р(Х)=n-1. В самомделе, эта вершина должна быть соединена с (n-1)вершиной, в том числе и с А, но ведь А оказалась изолированной.Следовательно, в графе, имеющем nвершин, не могут быть одновременно вершины степени0и (n-1). Это значит, что из nвершиннайдутся две, имеющие одинаковые степени.

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

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

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

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

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

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

Доказательство этой теоремы очень интересно и характернодля теории графов. Его также следует считать конструктивным (обратите вниманиена то, как использована при этом теорема3.6). Для доказательства к исходному графуприсоединяем ребро (А, В); после этого все вершины графа станутчетными. Этот новый граф удовлетворяет всем условиям теоремы3.6, и поэтому в нем можно проложить эйлеровцикл Ψ. И если теперь в этом цикле удалить ребро (А, В),то останется искомая цепь АВ.

На этом любопытном приеме основано доказательствоследующей теоремы, которую следует считать обобщением теоремы7.

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

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

По поводу доказательства этой теоремы сделаем однозамечание. Эта теорема известна, восновном, как вывод английскогоматематика А. Кэли(1821—1895).Графы-деревья издавна привлекали внимание ученых. Сегодня двоичные деревьяиспользуются не только математиками, а и биологами, химиками, физиками и инженерами(подробнее об этом – в параграфе 6).

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

Доказательство.Воспользуемся формулой Эйлера: В-Р+Г=2,где В— число вершин плоскогографа, Р— число его ребер, Г— число граней. Формула Эйлера справедлива дляплоских связных графов, в которых ни один из многоугольников не лежит внутридругого.

Эту формулу можно доказать методом математическойиндукции. Это доказательство мы опускаем. Заметим только, что формуласправедлива и для пространственных многогранников. Пусть все пять вершин графасоединены друг с другом. Замечаем, чтона графе нет ни одной грани, ограниченной только двумя ребрами. Если через φ1обозначить число таких граней, то φ2=0. Далеерассуждаем от противного, а именно: предположим, что исследуемый граф плоский.Это значит, что для него верна формула Эйлера. Число вершин в данном графе В=5, число ребер Р=10, тогда числограней Г=2-В+Р=2-5+10=7.

Это число можно представить в виде суммы: Г=φ1+φ2+φ3+…, где φ3 – число граней, ограниченных тремя ребрами, φ4— число граней, ограниченных четырьмя ребрамии т. д.

С другой стороны, каждое ребро является границей двухграней, а поэтому число граней равно 2Р, в то же время 2Р=20=3φ3+4φ4+… . Умножив равенство Г=7=φ3+φ4 + φ5 + … на три, получим ЗГ=21=3(φ3 + φ4 + φ5 + …).

Ясно, что (3φ3+3φ4+3φ5+…)< (3φ3+4φ4+ 5φ5+…)или 3Г<2Р, но по условию, 2Р=20, а ЗГ=21;поэтому вывод, полученный при введенном нами предположении (граф плоский),противоречит условию. Отсюда заключаем, что полный граф с пятью вершинами неявляется плоским.

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

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

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

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

Требования кпредставлению графов

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

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

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

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

Замечание

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

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

Представление графа с помощью матрицы 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 endrecord,

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

Обзорзадач теории графов

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

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

Далее перечислим некоторые типовые задачи теорииграфов и их приложения:

— Задача о кратчайшей цепи

SYMBOL183 f «Symbol» s 10 hзамена оборудования

SYMBOL183 f «Symbol» s 10 hсоставление расписания движения транспортных средств

SYMBOL183 f «Symbol» s 10 hразмещение пунктов скорой помощи

SYMBOL183 f «Symbol» s 10 hразмещение телефонных станций

— Задача о максимальном потоке

SYMBOL183 f «Symbol» s 10 hанализ пропускной способности коммуникационной сети

SYMBOL183 f «Symbol» s 10 hорганизация движения в динамической сети

SYMBOL183 f «Symbol» s 10 hоптимальный подбор интенсивностей выполнения работ

SYMBOL183 f «Symbol» s 10 hсинтез двухполюсной сети с заданной структурнойнадежностью

SYMBOL183 f «Symbol» s 10 hзадача о распределении работ

— Задача об упаковках и покрытиях

SYMBOL183 f «Symbol» s 10 hоптимизация структуры ПЗУ

SYMBOL183 f «Symbol» s 10 hразмещение диспетчерских пунктов городскойтранспортной сети

— Раскраска в графах

SYMBOL183 f «Symbol» s 10 hраспределение памяти в ЭВМ

SYMBOL183 f «Symbol» s 10 hпроектирование сетей телевизионного вещания

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

SYMBOL183 f «Symbol» s 10 hпроектирование кратчайшей коммуникационной сети

SYMBOL183 f «Symbol» s 10 hсинтез структурно-надежной сети циркуляционной связи

SYMBOL183 f «Symbol» s 10 hанализ надежности стохастических сетей связи

— Изоморфизм графов и сетей

SYMBOL183 f «Symbol» s 10 hструктурный синтез линейных избирательных цепей

SYMBOL183 f «Symbol» s 10 hавтоматизация контроля при проектировании БИС

— Изоморфное вхождение и пересечение графов

SYMBOL183 f «Symbol» s 10 hлокализация неисправности с помощью алгоритмов поискаМИПГ

SYMBOL183 f «Symbol» s 10 hпокрытие схемы заданным набором типовых подсхем

— Автоморфизм графов

SYMBOL183 f «Symbol» s 10 hконструктивное перечисление структурных изомеров для

производных органических соединений

SYMBOL183 f «Symbol» s 10 hсинтез тестов цифровых устройств

Заключение

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

Списоклитературы

1.

Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы:построение и анализ. – М: МЦНМО, 2001

2.

Н. Кристофидес. Теория графов: алгоритмический подход,Мир, 1978.

3.

Ф.А. Новиков. Дискретная математика для программистов,Питер, 2001.

4.

В.А. Носов. Комбинаторика и теория графов, МГТУ, 1999.
Приложение А

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

#include<iostream.h>

#include<stdio.h>

<span Courier New";mso-ansi-langu

еще рефераты

Еще работы по программированию, базе данных. математике

Реферат по программированию, базе данных. математике

Теория чисел (программа-калькулятор) - формирование заданного подмножества натурального ряда с помощью общего делителя

29 Августа 2013

Реферат по программированию, базе данных. математике

Численные методы. Программа-калькулятор на Pascal

29 Августа 2013

Реферат по программированию, базе данных. математике

Программа (код) на С++ решения жесткой краевой задачи методом А.Ю.Виноградова

29 Августа 2013