50301 (Графы и их представление на ЭВМ)

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

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

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

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

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

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

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

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

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

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

Содержание

Введение

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 VV, E = E^-

Соединения между узлами графа называются ребрами. Если узлы графа не нумерованы, то ребра являются неориентированными. У графа с нумерованными узлами ребра ориентированы. Ребрам могут быть присвоены определенные веса или метки. На рис. 1.1А и 1.1Б приведены примеры обычного и ориентированного графа.

Число вершин графа A обозначим р, а число ребер – q:

p : = p ( A ) : = V , q : = = q ( A ) : = E ;

Более простое определение графа - совокупность точек и линий, в которой каждая линия соединяет две точки. Для ориентированного графа E  V_x - конечный набор ориентированных ребер. Ребром может быть прямая или кривая линия. Ребра не могут иметь общих точек кроме вершин (узлов) графа. Замкнутая кривая в E может иметь только одну точку из множества V, а каждая незамкнутая кривая в E имеет ровно две точки множества V. Если V и E конечные множества, то и граф им соответствующий называется конечным. Граф называется вырожденным, если он не имеет ребер. Параллельными ребрами графа называются такие, которые имеют общие узлы начала и конца.

1.2 Смежность

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

Пусть v₁, v₂ — вершины, е = (v₁, v₂) — соединяющее их ребро. Множество вершин, смежных с вершиной 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 и наоборот.

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

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

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

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

Рис.1

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

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