Реферат на тему: Определение графов. Основное определение. Смежность. Другие определения

Введение

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

Графы представляют собой наиболее абстрактную структуру, с которой приходится сталкиваться в теории ЭВМ (computerscience). Графы используются для описания алгоритмов автоматического проектирования, в диаграммах машины конечных состояний, при решении задач маршрутизации потоков и т.д. Любая система, предполагающая наличие дискретных состояний или наличие узлов и переходов между ними может быть описана графом.

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

Теория графов многократно переоткрывалась разными авторами при решении различных прикладных задач.

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

Оглавление

- Введение

- Определение графов

- Основное определение

- Смежность

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

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

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

- Способы численного представления графов

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

- Виды графов и операции над ними

- Элементы графов

- Изоморфизм графов

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

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

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

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

- Представление графов в ЭВМ

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

- реализация алгоритмов поиска в глубину и ширину в программной среде Turbo Pascal Заключение

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

Заключение

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

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

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

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

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

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

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

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

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

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