Банк рефератов содержит более 364 тысяч рефератов, курсовых и дипломных работ, шпаргалок и докладов по различным дисциплинам: истории, психологии, экономике, менеджменту, философии, праву, экологии. А также изложения, сочинения по литературе, отчеты по практике, топики по английскому.
Полнотекстовый поиск
Всего работ:
364150
Теги названий
Разделы
Авиация и космонавтика (304)
Административное право (123)
Арбитражный процесс (23)
Архитектура (113)
Астрология (4)
Астрономия (4814)
Банковское дело (5227)
Безопасность жизнедеятельности (2616)
Биографии (3423)
Биология (4214)
Биология и химия (1518)
Биржевое дело (68)
Ботаника и сельское хоз-во (2836)
Бухгалтерский учет и аудит (8269)
Валютные отношения (50)
Ветеринария (50)
Военная кафедра (762)
ГДЗ (2)
География (5275)
Геодезия (30)
Геология (1222)
Геополитика (43)
Государство и право (20403)
Гражданское право и процесс (465)
Делопроизводство (19)
Деньги и кредит (108)
ЕГЭ (173)
Естествознание (96)
Журналистика (899)
ЗНО (54)
Зоология (34)
Издательское дело и полиграфия (476)
Инвестиции (106)
Иностранный язык (62792)
Информатика (3562)
Информатика, программирование (6444)
Исторические личности (2165)
История (21320)
История техники (766)
Кибернетика (64)
Коммуникации и связь (3145)
Компьютерные науки (60)
Косметология (17)
Краеведение и этнография (588)
Краткое содержание произведений (1000)
Криминалистика (106)
Криминология (48)
Криптология (3)
Кулинария (1167)
Культура и искусство (8485)
Культурология (537)
Литература : зарубежная (2044)
Литература и русский язык (11657)
Логика (532)
Логистика (21)
Маркетинг (7985)
Математика (3721)
Медицина, здоровье (10549)
Медицинские науки (88)
Международное публичное право (58)
Международное частное право (36)
Международные отношения (2257)
Менеджмент (12491)
Металлургия (91)
Москвоведение (797)
Музыка (1338)
Муниципальное право (24)
Налоги, налогообложение (214)
Наука и техника (1141)
Начертательная геометрия (3)
Оккультизм и уфология (8)
Остальные рефераты (21697)
Педагогика (7850)
Политология (3801)
Право (682)
Право, юриспруденция (2881)
Предпринимательство (475)
Прикладные науки (1)
Промышленность, производство (7100)
Психология (8694)
психология, педагогика (4121)
Радиоэлектроника (443)
Реклама (952)
Религия и мифология (2967)
Риторика (23)
Сексология (748)
Социология (4876)
Статистика (95)
Страхование (107)
Строительные науки (7)
Строительство (2004)
Схемотехника (15)
Таможенная система (663)
Теория государства и права (240)
Теория организации (39)
Теплотехника (25)
Технология (624)
Товароведение (16)
Транспорт (2652)
Трудовое право (136)
Туризм (90)
Уголовное право и процесс (406)
Управление (95)
Управленческие науки (24)
Физика (3463)
Физкультура и спорт (4482)
Философия (7216)
Финансовые науки (4592)
Финансы (5386)
Фотография (3)
Химия (2244)
Хозяйственное право (23)
Цифровые устройства (29)
Экологическое право (35)
Экология (4517)
Экономика (20645)
Экономико-математическое моделирование (666)
Экономическая география (119)
Экономическая теория (2573)
Этика (889)
Юриспруденция (288)
Языковедение (148)
Языкознание, филология (1140)

Курсовая работа: Графы и их представление на ЭВМ

Название: Графы и их представление на ЭВМ
Раздел: Рефераты по информатике, программированию
Тип: курсовая работа Добавлен 23:04:32 05 февраля 2011 Похожие работы
Просмотров: 3375 Комментариев: 2 Оценило: 1 человек Средний балл: 5 Оценка: неизвестно     Скачать

Федеральное агентство по образованию

Федеральное государственное общеобразовательное учреждение

высшего профессионального образования

Чувашский государственный университет им. И.Н. Ульянова

Алатырский филиал

Факультет управления и экономики

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

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

по дисциплине: Дискретная математика для программистов

на тему: Графы и их представление на ЭВМ


Содержание

Введение

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 реализация алгоритмов поиска в глубину и ширину в программной среде TurboPascal

Заключение

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


Введение

Среди дисциплин и методов дискретной математики теория графов и особенно алгоритмы на графах находят наиболее широкое применение в программировании. Между понятием графа и понятием отношения, имеется глубокая связь — в сущности это равнообъемные понятия. Возникает естественный вопрос, почему же тогда графам оказывается столь явное предпочтение? Дело в том, что теория графов предоставляет очень удобный язык для описания программных (да и многих других) моделей. Этот тезис можно пояснить следующей аналогией. Понятие отношения также можно полностью выразить через понятие множества. Однако независимое определение понятия отношения удобнее — введение специальных терминов и обозначений упрощает изложение теории и делает ее более понятной. То же относится и к теории графов. Стройная система специальных терминов и обозначений теории графов позволяют просто и доступно описывать сложные и тонкие вещи. Особенно важно наличие наглядной графической интерпретации понятия графа. Самоназвание «граф» подразумевает наличие графической интерпретации. Картинки позволяют сразу «усмотреть» суть дела на интуитивном уровне, дополняя и украшая утомительные рациональные текстовые доказательства и сложные формулы.

Графы представляют собой наиболее абстрактную структуру, с которой приходится сталкиваться в теории ЭВМ (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, то получается изолированная графа. Если два ребра инцидентны одной и той же паре вершин, они называются кратными; граф, содержащий кратные ребра, называется мультиграфом.

Пусть v 1 , v 2 вершины, е = (v 1 , v 2 ) — соединяющее их ребро. Множество вершин, смежных с вершиной v , называется множеством смежности вершины v и обозначается Г+ ( v ):

Г+ ( v ) : = {uÎV|(u , v ) ÎE}

Г( v ) : = Г* ( v ) : = Г+ ( v ) È{v }

u ÎГ( v ) Ûv ÎГ( u )

Замечание. Если не оговорено противное, то подразумевается Г+ и обозначается просто Г.

Если А Ì V множество вершин, то Г (А) — множество всех вершин, смежных с вершинами из А:

Г (А) : = {uÎV|$vÎAuÎГ ( v)};

1.3 Другие определения

Часто рассматриваются следующие родственные графам объекты.

1.Если элементами множества Е являются упорядоченные пары, то граф называется ориентированным (или орграфом). В этом случае элементы множества V называются узлами, а элементы множества Е — дугами.

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

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

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

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


2. Способы задания графов

2.1 Изображение графа

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

Граф G называется плоским , если его можно отобразить в плоскости без пересечения его граней. Очертанием графа (face) считается любая топологически связанная область, ограниченная ребрами графа.

Неориентированный граф G = <V,E> называется связанным , если для любых двух узлов 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 0 0 1 1 0
2 0 0 0 1 1
3 1 0 0 0 1
4 1 1 0 0 0
5 0 1 1 0 0

Матрица смежности графа GРис.

2.2.1 Граф и его матрица смежности

Матрица смежности симметрична относительно главной диагонали (рис. 2.2.1).

2. Матрица инцидентности вершин и рёбер содержит m– строк и n– столбцов, где m– количество вершин, n– количество рёбер.

Рис.1


a b c d e
A 0 1 1 0 0
B 1 0 0 1 1
C 0 0 1 0 1
D 0 1 0 1 0
E 1 0 0 0 0
F 0 0 0 0 0

Рис 2.2.2 Граф и его матрица инцидентности

В любом столбце матрицы инцидентности (рис. 2.2.2) лиши две единички.

Другой способ представления графа обеспечивает функция, которая выдает списки узлов, с которыми данный узел связан непосредственно. Для графа, отображенного на рис. 2.2.3, такое описание можно представить в виде структуры (таблица 2.1). В колонке s представлены номера узлов, далее в строке таблицы следует список соседних узлов. По этой причине число колонок в каждой из строк различно.

Таблица 2.1


2.3 Представление ориентированных граф

Представление ориентированных граф элементами матриц смежности и инцидентности являются 0, 1, -1. Пусть даны два ориентированных графа (рис. 2.3.1), тогда матрицы смежности и инцидентности для них будут выглядеть как в таблицe2.3

Рис. 2.3.1 Ориентированные графы

Таблица 2.3

Матрица смежности
A B
A B C
A 0 0 1
B 0 0 0
C 0 1 0
A B C
A 0 0 1
B 0 0 1
C 0 0 0
Матрица инцидентности
a b
A -1 0
B 0 1
C 1 -1
a b
A -1 0
B 0 -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 Изоморфизм графов

Говорят, что два графа G 1 ( V 1 , Е1 ) и G 2 ( V 2 , Е2 ) изоморфны (обозначается G 1 ~ G 2 ), если существует биекция h : V 1 ® V 2 , сохраняющая смежность:

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.симметричность: если G 1 ~ G 2 с биекцией h, то G 2 ~ G 1 с биекцией h-1 ;

3.транзитивность: если G 1 ~ G 2 с биекцией h, и G 2 ~ G 3 с биекцией g, тоG 1 ~ G 3 с биекцией goh.

Графы рассматриваются с точностью до изоморфизма, то есть рассматриваются классы эквивалентности по отношению изоморфизма.

Приведём примеры изоморфных графов рис. 3.2

Рис. 3.2 Диаграммы изоморфных граф

Числовая характеристика, одинаковая для всех изоморфных графов, называется инвариантом графа. Так, р( G ) и д( G ) — инварианты графа С.

Не известно никакого набора инвариантов, определяющих граф с точностью до изоморфизма.


3.3 Тривиальные и полные графы

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

Пример

С3 — треугольник.

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

Полный подграф (некоторого графа) называется кликой (этого графа).

3.4 Двудольные графы

Двудольный граф (или биграф, или четный граф) — это граф G ( V ,Е), такой что множество V разбито на два непересекающихся множества V 1 и V 2 ( V 1 ÈV 2 = V & V 1 ÇV 2 ) причем всякое ребро из Е инцидентно вершине из V 1 и вершине из V 2 (то есть соединяет вершину из V 1 с вершиной из V 2 ). Множества V 1 и V 2 называются долями двудольного графа. Если двудольный граф содержит все ребра, соединяющие множества V 1 и V 2 , то он называется полным двудольным графом. Если |V 1 | = mи |V 1 | = п, то полный двудольный граф обозначается Km , n

3.5 Направленные орграфы и сети

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

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

Если в орграфе полустепень захода некоторой вершины равна нулю (то есть d+(v) = 0), то такая вершина называется источником, если же нулю равна полу степень исхода (то есть d-(v) = 0), то вершина называется стоком. Направлен ный орграф с одним источником и одним стоком называется сетью.

3.6 Операции над графами

1.Дополнением графа G 1 ( V 1 , Е1 ) называется граф G ( V 2 , Е2 ) рис. 3.6.1, где

V 2 : = V 1 & Е2 : = Ø Е1 : = { e Î V 1 ´ V 1 ê e Ï Е1 }

G1 ØG

Рис 3.6.1 Дополнение


Объединением графов G 1 ( V 1 , Е1 ) и G 2 ( V 2 , Е2 ) (обозначение - G 1 ÈG 2 , при условии V 1 Ç V 1 = Æ, Е1 Ç Е2 = Æ) называется граф G(V,E), рис. 3.6.3

V : = V 2 ÈV 1 & Е : = Е1 Ç Е2


Рис. 3.6.3 Объединение графов

2.Соединением графов G 1 ( V 1 , Е1 ) и G 2 ( V 2 , Е2 ) (обозначение - G 1 ( V 1 , Е1 ) + G 2 ( V 2 , Е2 ), при условии V 1 Ç V 2 называется граф G ( V , E ), где

V : = V1 Ç V2 & E : = Е 1 ÈЕ 2 È{e = (v1 , v2 ) ê v1 Î V1 & v2 Î V2 }

3.Удаление вершины vиз графа G 1 ( V 1 , Е1 ) (обозначение - G 1 ( V 1 , Е1 ) – v , при условии v Î V 1 ) даёт граф G 2 ( V 2 , Е2 ) , где

V2 : = V1 \ {v }& E2 : = E1 \ {e = (v1 , v2 ) ê v1 = v Ú v2 = v }

4.Удаление ребра e из графа G 1 ( V 1 , Е1 ) (обозначение - G 1 ( V 1 , Е1 )e , при условии e Î E 1 ) даёт граф G 2 ( V 2 , Е2 ) , где

V 2 : = V 1 & E 2 : = E 1 \ { e }

5.Добавление вершины v в граф G 1 ( V 1 , Е1 ) (обозначение - G 1 ( V 1 , Е1 ) + v , при условии vÏV1 ) даёт граф G 2 ( V 2 , Е2 ) , где


V2 : = V1 È{v }& E2 : = E1

6.Добавление ребра e в граф G 1 ( V 1 , Е1 ) (обозначение - G 1 ( V 1 , Е1 ) + v , при условии e Ï E 1 ) даёт граф G 2 ( V 2 , Е2 ) , где

V 2 : = V 1 & E 2 : = E 1 È { e }

7.Стягивание подграфа А графа G 1 ( V 1 , Е1 ) (обозначение - G 1 ( V 1 , Е1 ) / А, при условии А Ì V 1 ) даёт граф G 2 ( V 2 , Е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 ( p 2 ) .

2. Матрица инциденций. Представление графа с помощью матрицы H: array[1..p, 1..q] of0..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 : recordv:1..р; п : ­N endrecord), называется списком смежности. В случае представления неориентированных графов списками смежности п(р, q ) = О(р + 2 q ), а в случае ориентированных графов п(р, q ) = О(р + q ).

4. Массив дуг. Представление графа с помощью массива структур Е : array[1..р] ofrecordb,e: 1..pendrecord, отражающего список пар смежных вершин, называется мас сивом ребер(или, для орграфов, массивом дуг). Для массива ребер (или дуг) п(р, q ) = О( 2 q ).

5. Обход графа — это некоторое систематическое перечисление его вершин (и/или ребер). Наибольший интерес представляют обходы, использующие локальную информацию (списки смежности). Среди всех обходов наиболее известны поиск в ширину и в глубину. Алгоритмы поиска в ширину и в глубину лежат в основе многих конкретных алгоритмов на графах.

ТЕОРЕМА Если граф G связен (и конечен), то поиск в ширину и поиск в глубину обойдут все вершины по одному разу.

Доказательство

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

2.Завершаемость алгоритма. Всего в Т может попасть не более р вершин. На каждом шаге одна вершина удаляется из Т. Следовательно, алгоритм завершит работу не более чем через р шагов.

3.Обход всех вершин. От противного. Пусть алгоритм закончил работу, и вер шина w не обойдена. Значит, w не попала в Т. Следовательно, она не былаотмечена. Отсюда следует, что все вершины, смежные с w , не были обойденыи отмечены. Аналогично, любые вершины, смежные с неотмеченными, самине отмечены (после завершения алгоритма). Но Gсвязен, значит, существуетпуть ( v , w ). Следовательно, вершина v не отмечена. Но она была отмечена напервом шаге.

4.2 Реализация алгоритмов поиска в ширину и в глубину в программной среде TurboPascal

Задача состоит в том, найти путь из вершины 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<=tail) and not f do 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('<-', Prev[k]); k:=Prev[k] end End elseWrite('Пути из ', 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('<=', p); 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.

Заключение

Курсовой проект выполнен на тему «Графы и их представление на ЭВМ». В нём рассмотрены следующие вопросы:

- Определение графов: основное определение, смежность, другие определения;

- Способы задания графов: изображение графа, способы численного представления графов, представление ориентированных граф;

- Виды графов и операции над ними: элементы графов, изоморфизм графов, тривиальные и полые графы, двудольные графы, направленные орграфы и сети, операции над графами;

- Представление графов в ЭВМ: требование к представлению графов, реализация алгоритмов поиска в глубину и ширину в программной среде TurboPascal;

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

После проделанной работы можно сделать следующий вывод:

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


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

1. Дискретная математика для программистов / Ф.А.Новиков. – СПб.: Питер, 2002. – 304 с.

2. Судоплатов С.В., Овчинникова Е.В. Элементы дискретной математики: Учебник. – М.: ИНФРА-М, Новосибирск: Изд-во НГТУ, 2002. – 280 с. – (Серия «Высшее образование»)

3. Материал из Википедии — свободной энциклопедии. Элементы теории граф (http://referats/mat_graph);

4. Элементы теории граф (http://book.itep.ru/10/graph1021.htm).

Оценить/Добавить комментарий
Имя
Оценка
Комментарии:
Где скачать еще рефератов? Здесь: letsdoit777.blogspot.com
Евгений08:11:04 19 марта 2016
Кто еще хочет зарабатывать от 9000 рублей в день "Чистых Денег"? Узнайте как: business1777.blogspot.com ! Cпециально для студентов!
09:32:49 29 ноября 2015

Работы, похожие на Курсовая работа: Графы и их представление на ЭВМ
Основы дискретной математики
Федеральное агентство по образованию Новомосковский институт (филиал) Государственного образовательного учреждения высшего профессионального ...
Тогда говорят, что ребро E инцидентно вершинам a и b. И обратно - вершины a и b инцидентны ребру E.
Графы G и G1 изоморфны, если существует взаимнооднозначное соответствие между множествами их вершин V и V1 и вершины в графе G соединены ребром в том и только том случае, если ...
Раздел: Рефераты по информатике, программированию
Тип: учебное пособие Просмотров: 4172 Комментариев: 2 Похожие работы
Оценило: 0 человек Средний балл: 0 Оценка: неизвестно     Скачать
Задача остовных деревьев в k-связном графе
... Молдавский Государственный Университет Кафедра Информатики и Дискретной Оптимизации Дипломная работа: "Задача остовных деревьев в k-связном графе"
Можно встать и на другую точку зрения и рассматривать I(G) как матрицу смежности вершин для нового графа, также обозначаемого через I(G), вершинами которого являются ребра Е графа ...
Для произвольной вершины x графа G через dG(x) мы будем обозначать степень вершины x в графе G(V, E). Для x V, A V через dG(x, A) обозначим количество ребер, соединяющих вершину x ...
Раздел: Рефераты по математике
Тип: реферат Просмотров: 1728 Комментариев: 2 Похожие работы
Оценило: 0 человек Средний балл: 0 Оценка: неизвестно     Скачать
Графы. Решение практических задач с использованием графов (С++
Курсовая работа Выполнил: студент 1-го курса факультета КНиИТ, группа № 121, Жучков Андрей Сергеевич Саратовский государственный университет им. Н.Г ...
Графом G(V,E) называется совокупность двух множеств - непустого множества V(множества вершин) и множества E двухэлементных подмножеств множества V(E - множество ребер).
Представление графа с помощью матрицы H, отражающей инцидентность вершин и ребер, называется матрицей инциденций, где для неориентированного графа
Раздел: Рефераты по математике
Тип: реферат Просмотров: 6613 Комментариев: 6 Похожие работы
Оценило: 5 человек Средний балл: 3.6 Оценка: неизвестно     Скачать
Графика в системе Maple V
1. Двумерная графика 1.1. Основные возможности двумерной графики Лидером по графическим возможностям среди математических систем для персональных ...
x = ((a'2-u)*(si'2-v)*(a'2-w)/{V2-a'2))'(l/2) у = ((b"2-u)*(b"2-v)*(b-2-w)/(b-2-a-2) Г(1/2) z = (a"2+b"2-u-v-w)/2
obsrange = TRUE,FALSE - задает (при TRUE) прерывание вычислений,
Раздел: Рефераты по информатике, программированию
Тип: доклад Просмотров: 7848 Комментариев: 2 Похожие работы
Оценило: 2 человек Средний балл: 5 Оценка: неизвестно     Скачать
Эйлеровы и гамильтоновы графы
Министерство народного образования Республики Дагестан Дагестанский Государственный Университет Курсовая работа Программирование задач на графах ...
Маршрутом в графе G(V,E) называется чередующаяся последовательность вершин и ребер: v0,e1, . en,vn, в которой любые два соседних элемента инцидентны.
Для этого, например, достаточно к вершинам v1,.,vp графа G добавить вершины u1,.,up и множество ребер {(vi,ui)}{(ui,vi+1)}
Раздел: Рефераты по информатике, программированию
Тип: реферат Просмотров: 6742 Комментариев: 3 Похожие работы
Оценило: 1 человек Средний балл: 2 Оценка: неизвестно     Скачать
Проектирование трансляторов
ЛЕКЦИЯ 1 СУЩНОСТЬ ПРЕДМЕТА. СОДЕРЖАНИЕ КП. СРОКИ. ОРГАНИЗАЦИЯ РАБОТ. МАТЕМАТИЧЕСКИЙ АППАРАТ. СТРУКТУРНАЯ СХЕМА ТРАНСЛЯТОРА. ПРОХОДЫ ТРАНСЛЯТОРА ...
Рассмотрим набор переменных V1, V2, V3, ..., Vn.
Для вычисления значения выражения (a+b*c)/(f*g-(d+e)/(h+k))
Раздел: Рефераты по информатике, программированию
Тип: реферат Просмотров: 655 Комментариев: 3 Похожие работы
Оценило: 1 человек Средний балл: 5 Оценка: неизвестно     Скачать
AGraph: библиотека классов для работы с помеченными графами
1. Актуальность разработки библиотек для работы с графами К настоящему времени накоплен большой опыт решения теоретико-графовых задач на ЭВМ ...
G.AddEdges([1, 2, 2, 4]); // ребра (v1, v2) и (v2, v4)
/ присваивание значений атрибутам вершины v и ребра e графа G
Раздел: Рефераты по информатике, программированию
Тип: курсовая работа Просмотров: 1852 Комментариев: 2 Похожие работы
Оценило: 0 человек Средний балл: 0 Оценка: неизвестно     Скачать
Орграфы, теория и применение
Федеральное агентство по образованию РФ Государственное образовательное учреждение высшего профессионального образования "Санкт-Петербургский ...
Граф G=(V,E) связен тогда и только тогда, когда множество го вершин нельзя разбить на два непустых подмножества V1 и V2 так, чтобы бе граничные точки каждого ребра находились в ...
1) Сумма элементов матрицы A(G), где G=(V, E) - мультиграф, V={v1, v2, ..., vn}, по i-й строке (или по i-му столбцу) равна ѭ(vi).
Раздел: Рефераты по математике
Тип: реферат Просмотров: 1147 Комментариев: 2 Похожие работы
Оценило: 0 человек Средний балл: 0 Оценка: неизвестно     Скачать

Все работы, похожие на Курсовая работа: Графы и их представление на ЭВМ (4857)

Назад
Меню
Главная
Рефераты
Благодарности
Опрос
Станете ли вы заказывать работу за деньги, если не найдете ее в Интернете?

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



Результаты(150154)
Комментарии (1830)
Copyright © 2005-2016 BestReferat.ru bestreferat@mail.ru       реклама на сайте

Рейтинг@Mail.ru