Федеральноеагентство по образованию
Федеральноегосударственное общеобразовательное учреждение
высшегопрофессионального образования
Чувашскийгосударственный университет им. И.Н. Ульянова
Алатырскийфилиал
Факультетуправления и экономики
Кафедравысшей математики и информационных технологий
Курсоваяработа
подисциплине: Дискретнаяматематика для программистов
натему: Графы и их представление на ЭВМ
Содержание
Введение
1. Определение графов
1.1 Основное определение
1.2 Смежность
1.3 Другие определения
2. Способы задания графов
2.1 Изображение графа
2.2 Способы численного представленияграфов
2.3 Представление ориентированныхграф
3. Виды графов и операциинад ними
3.1 Элементы графов
3.2 Изоморфизм графов
3.3 Тривиальные и полные графы
3.4 Двудольные графы
3.5 Направленные орграфы исети
3.6 Операции над графами
4. Представление графов вЭВМ
4.1 Требования к представлениюграфов
4.2 реализация алгоритмовпоиска в глубину и ширину в программной среде Turbo Pascal
Заключение
Список использованнойлитературы
Введение
Среди дисциплини методов дискретной математики теория графов и особенно алгоритмы на графах находятнаиболее широкое применение в программировании. Между понятием графа и понятиемотношения, имеется глубокая связь — в сущности это равнообъемные понятия. Возникаетестественный вопрос, почему же тогда графам оказывается столь явное предпочтение?Дело в том, что теория графов предоставляет очень удобный язык для описанияпрограммных (да и многих других) моделей. Этот тезис можно пояснить следующей аналогией.Понятие отношения также можно полностью выразить через понятие множества. Однаконезависимое определение понятия отношения удобнее — введение специальныхтерминов и обозначений упрощает изложение теории и делает ее более понятной. Тоже относится и к теории графов. Стройная система специальных терминов и обозначенийтеории графов позволяют просто и доступно описывать сложные и тонкие вещи. Особенноважно наличие наглядной графической интерпретации понятия графа. Самоназвание «граф»подразумевает наличие графической интерпретации. Картинки позволяют сразу «усмотреть»суть дела на интуитивном уровне, дополняя и украшая утомительные рациональные текстовыедоказательства и сложные формулы.
Графы представляютсобой наиболее абстрактную структуру, с которой приходится сталкиваться в теорииЭВМ (computerscience). Графы используются для описания алгоритмов автоматическогопроектирования, в диаграммах машины конечных состояний, при решении задач маршрутизациипотоков и т.д. Любая система, предполагающая наличие дискретных состояний или наличиеузлов и переходов между ними может быть описана графом.
Как это ни удивительно,но для понятия «граф» нет общепризнанного едино го определения. Разные авторы, особенноприменительно к разным приложениям, называют «графом» очень похожие, но все-такиразличные объекты. Здесь используется терминология, которая была выбрана из соображениймаксимального упрощения определений и доказательств.
Теория графовмногократно переоткрывалась разными авторами при решении различных прикладных задач.
Например, Задачао Кенигсбергских мостах. Обойти все четыре части суши, пройдя по каждому мостуодин раз, и вернуться в исходную точку Эта задача была решена Эйлером в 1736 году.Задача о трех домах и трех колодцах. Имеется три дома и три колодца. Провести от каждого дома к каждому колодцу тропинку так, чтобы тропинки не пересекались.Эта задача была решена Куратовским в 1930 году. Задача о четырех красках. Любуюкарту на плоскости раскрасить четырьмя красками так, чтобы никакие две соседниеобласти не были закрашены одним цветом.
1. Определенияграфов
1.1 Основноеопределение
Графом G(V, Е) называется совокупность двухмножеств — непустого множества V(множества вершин) имножества Е неупорядоченных пар различных элемен тов множества V(Е — множество ребер).
G (V, E ) = { V, E}, V ¹ Æ, E Ì V´V, E = E-
Соединения междуузлами графа называются ребрами. Если узлы графа не нумерованы, то ребра являютсянеориентированными. У графа с нумерованными узлами ребра ориентированы. Ребрам могутбыть присвоены определенные веса или метки. На рис. 1.1А и 1.1Б приведены примерыобычного и ориентированного графа.
Число вершин графаAобозначим р, а числоребер – q:
p: = p ( A ): = | V |, q: = = q ( A ): = | E |;
Более простоеопределение графа — совокупность точек и линий, в которой каждая линия соединяетдве точки. Для ориентированного графа E Vx — конечный набор ориентированныхребер. Ребром может быть прямая или кривая линия. Ребра не могут иметь общих точеккроме вершин (узлов) графа. Замкнутая кривая в E может иметь только одну точку измножества V, а каждая незамкнутая кривая в E имеет ровно две точки множества V.Если V и E конечные множества, то и граф им соответствующий называется конечным.Граф называется вырожденным, если он не имеет ребер. Параллельнымиребрами графа называются такие, которые имеют общие узлы начала и конца.
1.2 Смежность
Если ребро соединятдве вершины, то говорят, что оно им инцидентно; вершины, соединенные ребром называютсясмежными. Две вершины, соединенные ребром, могут совпадать; такое ребро называетсяпетлей. Число ребер, инцидентных вершине, называется степенью вершины. Если степеньвершины равна 0, то получается изолированная графа. Если два ребра инцидентны однойи той же паре вершин, они называются кратными; граф, содержащий кратные ребра, называетсямультиграфом.
Пусть v1, v2— вершины, е = (v1, v2) — соединяющее их ребро.Множество вершин, смежных с вершиной v, называется множеством смежностивершины vи обозначается Г+( v):
Г+(v): = { u Î V | (u, v) Î E}
Г( v): = Г*( v): = Г+( v) È {v}
uÎ Г( v) Û v Î Г( u)
Замечание. Если не оговорено противное,то подразумевается Г+ и обозначается просто Г.
Если А ÌV— множество вершин, то Г(А) — множество всех вершин, смежных с вершинами из А:
Г (А): = { u Î V | $v Î A u Î Г ( v )};
1.3 Другиеопределения
Часто рассматриваютсяследующие родственные графам объекты.
1. Если элементами множества Е являютсяупорядоченные пары, то граф называется ориентированным (или орграфом).В этом случае элементы множества Vназываются узлами, аэлементы множества Е — дугами.
2. Если элементом множества Е может бытьпара одинаковых (не различных)элементов V, то такой элемент множестваЕ называется петлей, а граф называется графом с петлями (илипсевдографом).
3. Если Е является не множеством, а набором,содержащим несколько одинаковых элементов, то эти элементы называются кратнымиребрами, а граф называется мулътиграфом.
4. Если элементами множества Е являютсяне обязательно двухэлементные, алюбые подмножества множества V, то такие элементы множестваЕ называются гипердугами, а граф называется гиперграфом.
5. Если задана функция Е: V® М и/или F: Е®М, то множество М называетсямножеством пометок, а граф называется помеченным (или нагруженным).Вкачестве множества пометок обычно используются буквы или целые числа.
2. Способызадания графов
2.1 Изображениеграфа
Графы отображаютсяна плоскости набором точек и соединяющих их линий или векторов. При этом грани могутотображаться и кривыми линиями, а их длина не играет никакой роли.
Граф G называетсяплоским, если его можно отобразить в плоскости без пересечения егограней. Очертанием графа (face) считается любая топологически связанная область,ограниченная ребрами графа.
Неориентированныйграф G = называется связанным, если для любых двух узловx,y О V существует последовательность ребер из набора E, соединяющий x и y. ГрафG связан тогда и только тогда, когда множество его вершин нельзя разбить на дванепустых подмножества V1 и V2 так, чтобы обе граничные точки каждого ребра находилисьв одном и том же подмножестве. Граф G называется k-связным (k і 1),если не существует набора из k-1 или меньшего числа узлов V`Н V, такого, что удалениевсех узлов V` и сопряженных с ними ребер, сделают граф G несвязанным.
Теорема Менгера: граф G является k-связаннымтогда и только тогда, когда любые два различные узла x и y графа G соединены покрайне мере k путями, не содержащими общих узлов. k-связанные графы представляютособый интерес для сетевых приложений. Определенную проблему составляет автоматическоеотображение графа на экране или бумаге. Кроме того, для многих приложений (например,CAD) все узлы графа должны совпадать с узлами технологической сетки. Возникают идругие ограничения, например необходимость размещения всех узлов на прямой линии.В этом случае ребра графа могут представлять собой кривые линии, дуги или ломаныелинии, состоящие из отрезков прямых.
2.2Способы численного представления графа
1. Матричный способ(с помощью матрицы смежности). Матрица смежности имеет m – строк и n – столбцов, где m – количество вершин графа.
Элементами матрицысмежности являются 0 и 1, Если вершины соединены, то ставится 1 и наоборот. 1 2 3 4 5 1 1 1 2 1 1 3 1 1 4 1 1 5 1 1
Матрицасмежности графа GРис.
2.2.1Граф и его матрица смежности
Матрица смежностисимметрична относительно главной диагонали (рис. 2.2.1).
2. Матрица инцидентностивершин и рёбер содержит m – строк и n – столбцов, где m – количество вершин, n – количество рёбер.
/>
Рис.1
a b c d e A 1 1 B 1 1 1 C 1 1 D 1 1 E 1 F
Рис 2.2.2 Графи его матрица инцидентности
В любом столбцематрицы инцидентности (рис. 2.2.2) лиши две единички.
Другой способпредставления графа обеспечивает функция, которая выдает списки узлов, с которымиданный узел связан непосредственно. Для графа, отображенного на рис. 2.2.3, такоеописание можно представить в виде структуры (таблица 2.1). В колонке s представленыномера узлов, далее в строке таблицы следует список соседних узлов. По этой причинечисло колонок в каждой из строк различно.
Таблица 2.1
/>
2.3 Представлениеориентированных граф
Представлениеориентированных граф элементами матриц смежности и инцидентности являются 0, 1,-1. Пусть даны два ориентированных графа (рис. 2.3.1), тогда матрицы смежности иинцидентности для них будут выглядеть как в таблицe 2.3
/>
Рис. 2.3.1 Ориентированныеграфы
Таблица 2.3Матрица смежности A B A B C A 1 B C 1 A B C A 1 B 1 C Матрица инцидентности a b A -1 B 1 C 1 -1 a b A -1 B -1 C 1 1
В матрице инцидентностидля ориентированных граф ставится 0 – если вершина и ребро не инцидентны, -1 – есливершина является началом, 1 – если вершина является концом.
3. Виды графови операции над ними
3.1 Элементыграфов
Для рассмотрениявидов граф и операций над ними необходимо познакомиться с такими понятиями как подграфы,маршрут, цепь, цикл.
Граф G'(V', Е') называется подграфом графаG(V, Е) (обозначается G' Ì G), если V' Ì Vи/или Е' Ì Е.
Если V' = V, то G' называется остовным подграфомG.
Если V' Ì V& Е' Ì Е & (V' ¹VÚ Е' ¹Е), то граф G' называется собственнымподграфом графа G.
Подграф G'(V', Е') называется правильным подграфомграфа G(V, Е), если G' содержит все возможные ребраG:
"и,vÎ V' (и, v) Î Е Þ(и, v) Î Е'.
Правильный подграфG'(V', Е') графа G(V, Е) определяется подмножествомвер шин V'.
Маршрутом в графе называется чередующаясяпоследовательность вершин и ребер в которой любые два соседних элемента инцидентны.
v0, e1, v1, e2, v2,…,ek, vk,
Это определениеподходит также для псевдо-, мульти- и орграфов. Для «обычного» графа достаточноуказать только последовательность вершин или только последовательность ребер.
Если v0= vk, то маршрут замкнут, иначеоткрыт. Если все ребра различны, то маршрут называется цепью. Есливсе вершины (а значит, и ребра) различны, то маршрут называется простой цепью.В цепи v0, e1, v1, e2, v2,…,ek, vk,
вершины v0и vk,называются концамицепи. Говорят, что цепь с концами и и vсоединяет вершины и и v. Цепь, соединяющая вершиныи и v, обозначается (и, v). Очевидно, что если есть цепь,соединяющая вершины и и v, то есть и простая цепь, соединяющая эти вершины.
Замкнутая цепьназывается циклом; замкнутая простая цепь называется простым циклом. Числоциклов в графе Gобозначается z(G). Граф без циклов называетсяациклическим.
Элементы графа– любое чередование вершин и рёбер графа, в котором каждому ребру предшествует смежнаяей вершина, называющаяся контуром графа.
/>
Рис 3.1 Маршруты,цепи, циклы
По рисунку 3.1можно определить следующие утверждения:
1. A,C, A, D – маршрут, но не цепь;
2. A,C, E, B, C, D – цепь, но не простая цепь;
3. A,D, C, B, E, — простая цепь;
4. A,C, E, B, C, D, A – цикл, но не простой цикл;
5. A,C, D – простой цикл;
Цепь в ориентированномграфе называется путём, а цикл – контуром.
3.2 Изоморфизмграфов
Говорят, что дваграфа G1(V1 , Е1) и G2(V2 , Е2) изоморфны (обозначаетсяG1 ~ G2), если существует биекцияh: V1®V2, сохраняющая смежность:
e1= ( u, v ) Î E1 Þ e2 = ( h( u ), h( v ) ) Î E2,
e2= ( u, v ) Î E2 Þ e1 = ( h-1( u ), h-1( v ) )Î E1
Изоморфизм графовесть отношение эквивалентности. Действительно, изомор физм обладает всеми необходимымисвойствами:
1. рефлексивность: G~ G, где требуемая биекция сутьтождественная функция;
2. симметричность: если G1 ~ G2 с биекцией h, то G2 ~ G1 с биекцией h-1;
3. транзитивность: если G1 ~ G2 с биекцией h, и G2 ~ G3 с биекцией g, тоG1 ~ G3 с биекцией g o h.
Графы рассматриваютсяс точностью до изоморфизма, то есть рассматриваются классы эквивалентностипо отношению изоморфизма.
/>Приведём примеры изоморфных графов рис. 3.2
/>/>
Рис. 3.2 Диаграммыизоморфных граф
Числовая характеристика,одинаковая для всех изоморфных графов, называется инвариантом графа. Так,р(G) и д(G) — инварианты графа С.
Не известно никакогонабора инвариантов, определяющих граф с точностью до изоморфизма.
3.3 Тривиальныеи полные графы
Граф, состоящийиз одной вершины, называется тривиальным. Граф, состоящий из простого циклас k вершинами, обозначается Сk.
Пример
С3— треугольник.
Граф, в которомкаждая пара вершин смежна, называется полным. Полный граф ср вершинамиобозначается Кр, он имеет максимально возможное число ребер:
/>
Полный подграф(некоторого графа) называется кликой (этого графа).
3.4 Двудольныеграфы
Двудольныйграф (илибиграф, или четный граф) — это граф G(V, Е), такой что множество Vразбито на два непересекающихсямножества V1 и V2(V1 ÈV2= V&V1 Ç V2) причем всякое ребро из Еинцидентно вершине из V1 и вершине из V2(то есть соединяет вершинуиз V1с вершиной из V2). Множества V1 и V2называются долями двудольногографа. Если двудольный граф содержит все ребра, соединяющие множества V1и V2, то он называется полнымдвудольным графом. Если |V1 | = m и |V1 | = п, то полный двудольныйграф обозначается Km,n
3.5 Направленныеорграфы и сети
Если в графе ориентироватьвсе ребра, то получится орграф, который называется направленным. Направленныйорграф, полученный из полного графа, называется турниром.
Название «турнир»имеет следующее происхождение. Рассмотрим спортивное соревнование для пар участников(или пар команд), где не предусматриваются ничьи. Пометим вершины орграфа участникамии проведем дуги от победителей к побежденным. В таком случае турнир в смысле теорииграфов — это как раз результат однокругового турнира в спортивном смысле.
Если в орграфеполустепень захода некоторой вершины равна нулю (то есть d+(v) = 0), то такая вершина называетсяисточником, если же нулю равна полу степень исхода (то есть d-(v) = 0), то вершина называетсястоком. Направлен ный орграф с одним источником и одним стоком называетсясетью.
3.6 Операциинад графами
1. Дополнением графа G1(V1 , Е1) называется граф G(V2 , Е2) рис. 3.6.1, где
/>/>/>/>/>/>/>V2 : = V1&Е2: = ØЕ1: = {eÎV1´V1êeÏЕ1}/>/>/>/>/>/>/>
G1ØG
Рис 3.6.1 Дополнение
Объединением графовG1(V1 , Е1) и G2(V2 , Е2) (обозначение — G1 È G2, при условии V1ÇV1= Æ, Е1ÇЕ2 = Æ) называется граф G(V,E), рис. 3.6.3
V: = V2 È V1&Е: = Е1ÇЕ2
/>
Рис. 3.6.3 Объединениеграфов
2. Соединением графов G1(V1 , Е1) и G2(V2 , Е2)(обозначение — G1(V1 , Е1) + G2(V2 , Е2), при условии V1 ÇV2 называется граф G(V,E), где
V:= V1 ÇV2&E: = Е1È Е2 È {e = (v1,v2) êv1 ÎV1&v2ÎV2}
3. Удаление вершины v из графа G1(V1 , Е1) (обозначение — G1(V1 , Е1) – v, при условии vÎV1) даёт граф G2(V2 , Е2), где
V2: = V1 \ {v} &E2: = E1\ {e = (v1, v2) ê v1 = v Úv2 = v}
4. Удаление ребра e из графа G1(V1 , Е1)(обозначение — G1(V1 , Е1) – e, при условии e ÎE1) даёт граф G2(V2 , Е2), где
V2: = V1&E2: = E1\ {e}
5. Добавление вершины v в граф G1(V1 , Е1) (обозначение — G1(V1 , Е1) + v, при условии v Ï V1) даёт граф G2(V2 , Е2), где
V2: = V1 È {v} &E2: = E1
6. Добавление ребра e в граф G1(V1 , Е1) (обозначение — G1(V1 , Е1) + v, при условии eÏE1) даёт граф G2(V2 , Е2), где
V2: = V1&E2: = E1È{e}
7. Стягивание подграфа А графа G1(V1 , Е1) (обозначение — G1(V1 , Е1) / А, при условии А ÌV1) даёт граф G2(V2 , Е2), где
V2: = (V1 \ A) È {v} &
E2: = E1 \ {e = (u,w) êu ÎA Úw ÎA}È{e = (u,v) êu ÎГ(А) \ А}
4. Представлениеграфов в ЭВМ
Следует еще разподчеркнуть, что конструирование структур данных для представления в программе объектовматематической модели — это основа искусства практического программирования. Используетсячетыре различных базовых представления графов. Выбор наилучшего представления определяетсятребованиями конкретной задачи. Более того, при решении конкретных задач используются,как правило, некоторые комбинации или модификации указанных представлений, общеечисло которых необозримо. Но все они, так или иначе, основаны на тех базовых идеях,которые описаны в этом разделе.
4.1 Требованияк представлению графов
Известны различныеспособы представления графов в памяти компьютера, которые различаются объемом занимаемойпамяти и скоростью выполнения операций над графами. Представление выбирается, исходяиз потребностей конкретной задачи. Далее приведены четыре наиболее часто используемыхпредставления с указанием характеристики п(р, q) — объема памяти для каждогопредставления. Здесь р — число вершин, аq— число ребер. Указанные представленияпригодны для графов и орграфов, а после некоторой модификации также и для псевдографов,мультиграфов и гиперграфов.
1. Матрица смежности.Представление граф с помощью квадратной булевской матрицы, отражающей смежностьвершин, называется матрицей смежности,
M:array [1..p, 1..p] of 0..1,
/>M [i, j] = 1, если вершина vi смежна с вершиной vj
0, если вершиныне vi и vj смежны.
Для матрицы смежностип(р, q) = O(p2).
2. Матрица инциденций.Представление графа с помощью матрицы H: array [1..p, 1..q] of 0..1 (для орграфов H: array [1..p, 1..q] of -1..1), отражающей инцидентность вершин и рёбер, называется матрицейинциденций, где для неориентированного графа
/>H [i, j] = 1, если вершина vi инцидентна ребру ej,
0, в противномслучае.
/>а для ориентированного графа
1, если вершинаvi инцидентна ребру ej и является его концом,
H [i, j] = 0, если вершина vi и ребро ej не инцидентны,
-1, если вершинаvi инцидентна ребру ej и является его началом
3. Списки смежности.Представление графа с помощью списочной структуры, отражающей смежность вершин исостоящей из массива указателей Г: array[1… р] оf N на списки смежных вершин(элемент списка представлен структурой N: record v:1… р; п :N endrecord), называется списком смежности. В случае представления неориентированныхграфов списками смежности п(р, q) = О(р + 2q), а в случае ориентированныхграфов п(р, q) = О(р + q).
4. Массив дуг.Представление графа с помощью массива структур Е: array [1… р] of record b,e: 1..p endrecord, отражающего список пар смежныхвершин, называется мас сивом ребер(или, для орграфов, массивом дуг).Для массива ребер (или дуг) п(р, q) = О( 2q).
5. Обход графа— это некоторое систематическое перечисление его вершин (и/или ребер). Наибольшийинтерес представляют обходы, использующие локальную информацию (списки смежности).Среди всех обходов наиболее известны поиск в ширину и в глубину. Алгоритмы поискав ширину и в глубину лежат в основе многих конкретных алгоритмов на графах.
ТЕОРЕМА Если граф Gсвязен (и конечен), то поискв ширину и поиск в глубину обойдут все вершины по одному разу.
Доказательство
1. Единственностьобхода вершины. Обходятся только вершины, попавшие в Т. В Т попадаюттолько неотмеченные вершины. При попадании в Т вершина отмечается. Следовательно,любая вершина будет обойдена не более одного раза.
2. Завершаемость алгоритма. Всего в Т можетпопасть не более р вершин. На каждом шаге одна вершина удаляется из Т.Следовательно, алгоритм завершит работу не более чем через р шагов.
3. Обход всех вершин. От противного. Пусть алгоритмзакончил работу, и вер шина w не обойдена. Значит, wне попала в Т. Следовательно,она не былаотмечена. Отсюда следует, что все вершины, смежные с w, не были обойденыи отмечены.Аналогично, любые вершины, смежные с неотмеченными, самине отмечены (после завершенияалгоритма). Но G связен, значит, существуетпуть (v,w). Следовательно, вершина vне отмечена. Но она была отмеченанапервом шаге.
4.2 Реализацияалгоритмов поиска в ширину и в глубину в программной среде Turbo Pascal
Задача состоитв том, найти путь из вершины A в вершину B. Будем задавать граф матрицей смежности,т.е. квадратной таблицей NxN, в которой на пересечении i-й строки и j-го столбцазначение TRUE, если i и j соединены ребром, и FALSE в противном случае.
Поиск в ширину.
Подобно тому как,согласно принципу Гюйгенса, каждая точка волнового фронта является источником вторичнойволны, мы, отправляясь из заданной вершины A, посещаем все смежные с ней вершины(т.е. вершины, в которые ведут стрелки из A). Каждая посещенная вершина становитсяисточником новой волны и т.д. При этом необходимо позаботиться о том, чтобы не вернутсяв ту вершину, в которой уже были. Для реализации алгоритма понадобятся: матрицаm[1..n, 1..n] — матрица смежности графа; вспомогательный массив queue[1..n], в которомбудет формироваться очередь, т.е. тип данных первый вошел – первый вышел (FIFO).Размер его достаточен, так как мы не посещаем вершины дважды. С массивом queue связаныдве переменные — head и tail. В переменной head будет находиться номер текущей вершины,из которой идет волна, а при помощи переменной tail новые вершины помещаются в «хвост»очереди queue; вспомогательный массив visited[1..n], который нужен для того, чтобыотмечать уже пройденные вершины (visited[i]=TRUE вершина i пройдена);вспомогательный массив prev[1..n] для хранения пройденных вершин. В этом массивеи будет сформирован искомый путь; переменная f, которая примет значение TRUE, когдапуть будет найден. Кроме того, мы введем несколько вспомогательных переменных, которыепонадобятся при организации циклов.
Program breadth_first_search;
Const n=9;
m:array[1..n, 1..n] of boolean =
(
(False, True, True, False, False, False, False, False,
False),
(True, False, True, False, False, False, True, True,
False),
(True, True, False, True, True, False, False, False,
False),
(False, False, True, False, True, False, False, False,
False),
(False, False, True, True, False, True, False, True,
False),
(False, False, False, False, True, False, True, True, True
),
(False, True, False, False, False, True, False, True, True
),
(False, True, False, False, True, True, True, False,
False),
(False, False, False, False, False, True, True, False, False)
);
Var A, B: integer;
Procedure A_to_B(A, B: integer);
Var
Visited: array[1..n] of boolean;
Prev: array[1..n] of integer;
c: array[1..n] of integer;
head, tail: integer;
f: boolean;
i, v, k: integer;
Begin
head:=1;
tail:=1;
f:=False;
For i:=1 to n do
Begin
Visited[i]:=False;
Prev[i]:=0
End;
C[tail]:=A;
Visited[A]:=True;
While (head
Begin
v:=C[head];
head:=head+1;
For k:=1 to n do
if m[v, k] and not Visited[k] then
Begin
tail:=tail+1;
C[tail]:=k;
Visited[k]:=True;
Prev[k]:=v;
if k=B then
Begin
f:=true;
break
End
End
End;
if f then
Begin
k:=B;
Write(B);
While Prev[k]0 do
Begin
Write('
k:=Prev[k]
end
End
else
Write('Пути из ', A, ' в ', B, ' нет')
end;
Begin
Write('A= '); readln(A);
Write('B= '); readln(B);
A_to_B(A, B)
End.
Поиск в глубину.
Идея поиска вглубину проста: отправляясь от текущей вершины, мы находим новую (еще не пройденную)смежную с ней вершину, которую помечаем как пройденную и объявляем текущей. Послеэтого процесс возобновляется. Если новой смежной вершины нет (тупик), возвращаемсяк той вершине, из которой попали в текущую, и делаем следующую попытку. Если попадемв вершину B, печатаем путь. Если все вершины исчерпаны — такого пути нет. Заметим,что построенный таким образом алгоритм способен находить все пути из A в B, но первыйнайденный необязательно должен быть кратчайшим. Как обычно, алгоритм с возвратамилегче всего оформить с помощью рекурсивной процедуры. Для ее реализации нам понадобятся:матрица m[1..n, 1..n] — матрица смежности графа; вспомогательный массив visited[1..n],который мы будем для того, чтобы отмечать уже пройденные вершины (visited[i]=TRUE вершина i пройдена); переменная f, которая примет значение TRUE, когдапуть будет найден.
Program depth_first_search;
Const n=9;
m:array[1..n, 1..n] of boolean =
(
(False, True, True, False, False, False, False, False,
False),
(True, False, True, False, False, False, True, True,
False),
(True, True, False, True, True, False, False, False,
False),
(False, False, True, False, True, False, False, False,
False),
(False, False, True, True, False, True, False, True,
False),
(False, False, False, False, True, False, True, True, True
),
(False, True, False, False, False, True, False, True, True
),
(False, True, False, False, True, True, True, False,
False),
(False, False, False, False, False, True, True, False, False)
);
Var A, B: integer;
Procedure A_to_b(A, B: integer);
Var
Visited: array[1..n] of boolean;
f: boolean;
i: integer;
Procedure Depth(p: integer);
var k: integer;
Begin
Visited[p]:=True;
For k:=1 to n do
If not f then
If m[p, k] and not Visited[k] then
If k=B then
Begin
f:=True;
Write(B);
Break
End
else Depth(k);
If f then write('
End;
Begin
For i:=1 to n do Visited[i]:=False;
f:=false;
Depth(A);
If not f then write('Пути из ', A, ' в ', B, ' нет')
End;
Begin
write('A= '); readln(A);
write('B= '); readln(B);
A_to_B(A, B)
End.
Заключение
Курсовой проектвыполнен на тему «Графы и их представление на ЭВМ». В нём рассмотрены следующиевопросы:
§ Определениеграфов: основное определение, смежность, другие определения;
§ Способызадания графов: изображение графа, способы численного представления графов, представлениеориентированных граф;
§ Виды графови операции над ними: элементы графов, изоморфизм графов, тривиальные и полые графы,двудольные графы, направленные орграфы и сети, операции над графами;
§ Представлениеграфов в ЭВМ: требование к представлению графов, реализация алгоритмов поискав глубину и ширину в программной среде Turbo Pascal;
На основании найденнойинформации (учебная литература, Internet), я выделил основные пункты, которые наиболее полнои точно дают представление о графах и их представлении на ЭВМ. При выполнении работыбыли приведены примеры графов, а также различные способы их задания и представленына основании заданных графов соответствующие им матрицы смежности и инцидентности.Были исследованы свойства операций над графами и к некоторым их них составлены графическиеизображения. В последней главе необходимо было указать на связь между графами иих представлением на ЭВМ, особенно это важно, на мой взгляд, для специальности математика-программиста.
После проделаннойработы можно сделать следующий вывод:
Графы широко используютсякак в самой математике, так и в ее приложениях. Они применяются при построении различныхматематических моделей: линий электропередачи, сетей автодорог, линий воздушныхсообщений и пр.
Список использованнойлитературы
1. Дискретнаяматематика для программистов / Ф.А.Новиков. – СПб.: Питер, 2002. – 304 с.
2. СудоплатовС.В., Овчинникова Е.В. Элементы дискретной математики: Учебник. – М.: ИНФРА-М, Новосибирск:Изд-во НГТУ, 2002. – 280 с. – (Серия «Высшее образование»)
3. Материализ Википедии — свободной энциклопедии. Элементы теории граф (http://referats/mat_graph);
4. Элементытеории граф (http://book.itep.ru/10/graph1021.htm).