Содержание
Введение
1. Определение графов
1.1 Основное определение
1.2 Смежность
Возможно вы искали - Курсовая работа: Дизайн презентаций
1.3 Другие определения
2. Способы задания графов
2.1 Изображение графа
2.2 Способы численного представления графов
2.3 Представление ориентированных граф
Похожий материал - Реферат: Понятійний апарат терміну "кібернетика"
3. Виды графов и операции над ними
3.1 Элементы графов
3.2 Изоморфизм графов
3.3 Тривиальные и полные графы
3.4 Двудольные графы
Очень интересно - Сочинение: Мова програмування Pascal
3.5 Направленные орграфы и сети
3.6 Операции над графами
4. Представление графов в ЭВМ
4.1 Требования к представлению графов
4.2 реализация алгоритмов поиска в глубину и ширину в программной среде TurboPascal
Вам будет интересно - Курсовая работа: Методика вивчення основних послуг Інтернет
Заключение
Список использованной литературы
Введение
Среди дисциплин и методов дискретной математики теория графов и особенно алгоритмы на графах находят наиболее широкое применение в программировании. Между понятием графа и понятием отношения, имеется глубокая связь — в сущности это равнообъемные понятия. Возникает естественный вопрос, почему же тогда графам оказывается столь явное предпочтение? Дело в том, что теория графов предоставляет очень удобный язык для описания программных (да и многих других) моделей. Этот тезис можно пояснить следующей аналогией. Понятие отношения также можно полностью выразить через понятие множества. Однако независимое определение понятия отношения удобнее — введение специальных терминов и обозначений упрощает изложение теории и делает ее более понятной. То же относится и к теории графов. Стройная система специальных терминов и обозначений теории графов позволяют просто и доступно описывать сложные и тонкие вещи. Особенно важно наличие наглядной графической интерпретации понятия графа. Самоназвание «граф» подразумевает наличие графической интерпретации. Картинки позволяют сразу «усмотреть» суть дела на интуитивном уровне, дополняя и украшая утомительные рациональные текстовые доказательства и сложные формулы.
Графы представляют собой наиболее абстрактную структуру, с которой приходится сталкиваться в теории ЭВМ (computerscience). Графы используются для описания алгоритмов автоматического проектирования, в диаграммах машины конечных состояний, при решении задач маршрутизации потоков и т.д. Любая система, предполагающая наличие дискретных состояний или наличие узлов и переходов между ними может быть описана графом.
Похожий материал - Курсовая работа: Интернет как инструмент реализации сервисной деятельности
Как это ни удивительно, но для понятия «граф» нет общепризнанного едино го определения. Разные авторы, особенно применительно к разным приложениям, называют «графом» очень похожие, но все-таки различные объекты. Здесь используется терминология, которая была выбрана из соображений максимального упрощения определений и доказательств.
Теория графов многократно переоткрывалась разными авторами при решении различных прикладных задач.
Например, Задача о Кенигсбергских мостах. Обойти все четыре части суши, пройдя по каждому мосту один раз, и вернуться в исходную точку Эта задача была решена Эйлером в 1736 году. Задача о трех домах и трех колодцах. Имеется три дома и три колодца. Про вести от каждого дома к каждому колодцу тропинку так, чтобы тропинки не пересекались. Эта задача была решена Куратовским в 1930 году. Задача о четырех красках. Любую карту на плоскости раскрасить четырьмя красками так, чтобы никакие две соседние области не были закрашены одним цветом.
1. Определения графов