Графы. решение практических задач с использованием графов (С++)

  • Просмотров 17975
  • Скачиваний 913
  • Размер файла 47
    Кб

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ САРАТОВСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ им. Н.Г. ЧЕРНЫШЕВСКОГО Кафедра теоретических основ информатики и информационных технологий ГРАФЫ. РЕШЕНИЕ ПРАКТИЧЕСКИХ ЗАДАЧ С ИСПОЛЬЗОВАНИЕМ ГРАФОВ (С++) Курсовая работа Выполнил: студент 1-го курса факультета КНиИТ, группа № 121, специальность «Вычислительные машины, комплексы, системы и сети» Жучков Андрей Сергеевич Научный

руководитель: Седина Юлия Олеговна Зав. Кафедрой ТОИиИТ Профессор, академик РАЕН, д.т.н. Сытник Александр Александрович Саратов 2005 СОДЕРЖАНИЕ 1.  Введение 2.  История возникновения теории графов 3.  Основные понятия теории графов 4.  Основные теоремы теории графов 5.  Способы представления графов в компьютере 6.  Обзор задач теории графов 7.  Заключение 8.  Список литературы 9.  Приложение А 10. Приложение Б

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

Причины этого нетрудно понять, просто обозначив круг задач, решаемых на базе этого математического аппарата. История возникновения теории графов. Родоначальником теории графов принято считать математика Леонарда Эйлера (1707-1783). Однако теория графов многократно переоткрывалась разными авторами при решении различных прикладных задач. 1.           Задача о Кенигсбергских мостах. На рис. 1 представлен

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