Метод графов

В последние годы особую важность приобрели те разделы математики, которые имеют отношение к развитию цифровых устройств, цифровой связи и цифровых вычислительных машин. Базой для преподавания этих дисциплин наряду с классическими методами анализа непрерывных физических моделей стали алгебраические, логические и комбинаторные методы исследования различных моделей дискретной математики.
Родившись при решении головоломок и игр, таких, например, как задача о кенигсбергских мостах и игра Гамильтона, теория графов стала мощным средством исследования и решения многих задач, возникающих при изучении больших и сложных систем. Для специалистов по вычислительной технике, информационным системам и системам цифровой связи теория графов – это удобный язык выражения понятий из этой области; многие результаты теории графов имеют непосредственную связь с задачами, с которыми им приходится сталкиваться.
Зарождение теории графов можно отнести к концу XVIII в., к работам А.Эйлера, посвященным решению математич. развлекательных задач. В ХХ в. толчком к развитию теории графов служат задачи, возникающие в физике, химии, электротехнике, биологии, экономике, социологии, а также во многих математич. дисциплинах. Современная теория графов включает различные подходы к решению соответствующих задач: комбинаторно-логические, геометрические (типологич.), теоретико-вероятностные.
Цель курсовой работы – исследовать теоретические аспекты метода графов и изучить примеры решения задач методом графов.
Задачи курсовой работы:
- исследование классификации и основных понятий метода графов;
- рассмотрение нахождения кратчайшего пути в графе;
- решение практических задач методом графов.

Теория графов это область дискретной математики, особенностью к-рой является геометрич. подход к изучению объектов. Основной объект Т.г. граф. Граф (G,(V,Е)) задается множеством вершин (V) и набором (Е) неупорядоченных и упорядоченных пар вершин. Неупорядоченная пара вершин наз. ребром, упорядоченная дугой. Граф, содержащий только ребра, наз. неориентированным; граф, содержащий только дуги, ориентированным. Пара вершин может соединяться двумя и более ребрами (дугами одного направления; направление дуги отвечает упорядоченности соответствующей пары вершин).
Значительно возросла популярность теории графов – ветви дискретной математики. Графы встречаются во многих областях под разными названиями: "структуры" в гражданском строительстве, "сети" – в электронике, "социограммы" – в социологии и экономике, "молекулярные структуры" – в химии, "дорожные карты", электрические или газовые распределительные сети и т. д.
Граф – это множество точек или вершин и множество линий или ребер, соединяющих между собой все или часть этих точек.
Петля – это дуга, начальная и конечная вершина которой совпадают.
Степень вершин – это удвоенное количество петель, находящихся у этой вершины плюс количество остальных прилегающих к ней ребер.
Путь в ориентированном графе – это последовательность дуг, в которой конечная вершина всякой дуги, отличной от последней, является начальной вершиной следующей.
Маршрут в графе – путь, ориентацией дуг которого можно пренебречь. Цепь – маршрут, в котором все ребра попарно различны. Цикл – замкнутый маршрут, являющийся цепью.
Подграф графа – это граф, являющийся подмоделью исходного графа. Т. е. подграф содержит некоторые вершины исходного графа и некоторые ребра (только те, оба конца которых входят в подграф).
Граф называется связным, если любая пара его вершин связана.
Дерево – это связный граф без циклов.