Читать курсовая по математике: "Граф и его элементы" Страница 1

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

Содержание Введение

. Граф и его элементы

.1 Основные понятия

.2 Ориентированный граф

.3 Неориентированный граф

.4 Смежность

.5 Маршруты и пути

. Постановка задачи коммивояжера и алгоритмы решения

.1 Задача коммивояжера

.2 Методы решения задачи коммивояжера

. Понятия транспортной сети

.1 Понятие увеличивающая дуга, цепь, разрез

. Алгоритм Флойда-Уоршелл

. Постановка задачи

. Решение задачи аналитическим методом

. Создание приложения для решения задачи

.1 Описание алгоритма

.3 Тестирование программы

.4 Руководство пользователя

Заключение

Список использованных источников

Приложение A. Расчет элементов для матриц

Теория графов представляет собой раздел математики, имеющий широкие практические приложения. Теория графов - область дискретной математики, особенностью которой является геометрический подход к изучению объектов. Во многих случаях жизни в частности, в проектной практике нам приходится рисовать на бумаге точки, изображающие города, отдельные объекты, железнодорожные узлы и т.п., и соединять эти точки линиями или стрелками, обозначающими некоторые связи или отношения. Такие схемы под различными названиями встречаются всюду, электрические цепи, в физике - радиосхемы; в экономике - диаграммы организации работ и т.д. В основном все схемы рассматриваются в абстрактной форме как самостоятельные математические объекты, названные графами. Такой подход к изучаемым объектам дает возможность теории графов иметь самые разнообразные и многочисленные приложения, в том числе и в области градостроительного проектирования и научных исследований. Первая работа по теории графов, принадлежавшая Эйлеру, появилась в 1736 году и была связана c решением задачи о Кёнигсбергских мостах. Однако, эта работа Эйлера была единственной в течение почти ста лет. Вначале теория графов казалась незначительным разделом математики, так как имела дело лишь c математическими развлечениями и головоломками, например, в схемотехнике, топология межсоединений элементов на печатной плате или микросхеме, задача o перевозках, задача o кругосветном путешествии и др. Развитие математики и ее приложении послужило сильным толчком к развитию теории графов. Уже в середине Х века графы использовались при построении эхем электрических цепей и молекулярных схем. Впервые термин «граф» ввел в 1936г. венгерский математик Денеш Кёниг. B его работе теория графов была представлена как отдельная математическая дисциплина, находящая в настоящее время широкое применение в автоматике, телемеханике, кибернетике, электронике, физике, экономике, психологии, биологии и других областях науки. 1. Граф и его элементы 1.1 Основные понятия Граф - это множество точек, называемых вершинами, и множество линий, называемых ребрами, которые соединяют пары вершин (или вершину саму с собой).

Геометрически граф можно представить как набор вершин (точек), определенные пары которых соединены линиями.

Например: сеть дорог, соединяющая города 1, 2, 3, 4, 5 можно представить в виде графа следующим образом: города обозначим точками (вершинами), а дороги неориентированными линиями (рисунок 1). Неориентированные линии означают наличие двустороннего движения между соответствующей парой городов.

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