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

Содержание

Введение

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. Определения графов

--> ЧИТАТЬ ПОЛНОСТЬЮ <--