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

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

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

КАФЕДРА АВТОМАТИЗИРОВАННОЙ ОБРАБОТКИ ЭКОНОМИЧЕСКОЙ ИНФОРМАЦИИ

КУРСОВАЯ РАБОТА

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

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

Исполнитель:

специальность

группа

№ зачетной книжки

Руководитель:

Туймазы – 2007

СодержаниеВведение 5 51. Теоретическая часть 61.1 История возникновения теории графов 61.2 Основные понятия теории графов 81.3 Основные теоремы теории графов 111.4 Способы представления графов в компьютере 161.4.1 Требования к представлению графов 161.4.2 Матрица смежности 161.4.3 Матрица инциденций 171.4.4 Списки смежности 171.4.5 Массив дуг 171.5 Обзор задач теории графов 18Заключение 192. Практическая часть 212.1. Общая характеристика задачи 212.2. Описание алгоритма решения задачи 22Список использованной литературы 26

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

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

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

Рисунок

Задача о трех домах и трех колодцах. Имеется три дома и три колодца, каким-то образом расположенные на плоскости. Провести от каждого дома к каждому колодцу тропинку так, чтобы тропинки не пересекались (рис. 2). Эта задача была решена (показано, что решение не существует) Куратовским в 1930 году [2, стр. 51].

Рисунок 2

Задача о четырех красках. Разбиение на плоскости на непересекающиеся области называется картой. Области на карте называются соседними, если они имеют общую границу. Задача состоит в раскрашивании карты таким образом, чтобы никакие две соседние области не были закрашены одним цветом (рис. 3). С конца позапрошлого века известна гипотеза, что для этого достаточно четырех красок. В 1976 году Аппель и

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