Читать курсовая по информатике, вычислительной технике, телекоммуникациям: "Применение теории графов в информатике" Страница 1

(Назад) (Cкачать работу)

ВСЕРОССИЙСКИЙ ЗАОЧНЫЙ

ФИНАНСОВО-ЭКОНОМИЧЕСКИЙ ИНСТИТУТ

КАФЕДРА МАТЕМАТИКИ И ИНФОРМАТИКИ

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

по дисциплине «Информатика»

на тему: «Применение теории графов в информатике»

УФА 2010

Содержание

Введение

Теоретическая часть

1.1 История возникновения теории графов

1.2 Основные понятия теории графов

1.3 Основные теоремы теории графов

1.4 Способы предоставления графов в компьютере

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

1.4.2 Матрица смежности

1.4.3 Матрица инциденций

1.4.4 Списки смежности

1.4.5 Массив дуг

1.5 Обзор задач теории графов

1.6 Программа определения кратчайшего пути в графах

1.6.1 Язык программирования Delphi

1.6.2 Программа «Определения кратчайшего пути в графе»

Практическая часть

2.1 Общая характеристика задачи

2.2 Описание алгоритма решения задачи

Заключение

Введение

Начало теории графов как математической дисциплины было положено Эйлером в его знаменитом рассуждении о Кенигсбергских мостах. Однако эта статья Эйлера 1736 года была единственной в течение почти ста лет. Интерес к проблемам теории графов возродился около середины прошлого столетия и был сосредоточен главным образом в Англии. Имелось много причин для такого оживления изучения графов. Естественные науки оказали свое влияние на это благодаря исследованиям электрических цепей, моделей кристаллов и структур молекул. Развитие формальной логики привело к изучению бинарных отношений в форме графов. Большое число популярных головоломок подавалось формулировкам непосредственно в терминах графов, и это приводило к пониманию, что многие задачи такого рода содержат некоторое математическое ядро, важность которого выходит за рамки конкретного вопроса. Наиболее знаменитая среди этих задач–проблема четырех красок, впервые поставленная перед математиками Де Морганом около 1850 года. Никакая проблема не вызывала столь многочисленных и остроумных работ в области теории графов.

Настоящее столетие было свидетелем неуклонного развития теории графов, которая за последние десять – двадцать лет вступила в новый период интенсивных разработок. В этом процессе явно заметно влияние запросов новых областей: теории игр и программирования, теории передачи сообщений, электрических сетей и контактных цепей, а также проблем психологии и биологии.

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

1. Теоретическая часть

Родоначальником теории графов принято считать математика Леонарда Эйлера (1707-1783) [3, стр. 36]. Однако теория графов многократно переоткрывалась разными авторами при решении различных прикладных задач.

Задача о Кенигсбергских мостах. На рис. 1 представлен схематический план центральной части города Кенигсберг (ныне Калининград), включающий два берега реки Перголя, два острова в ней и семь

Похожие работы