Научно-исследовательская работа по теме: «Программная реализация алгоритма построения минимальных связывающих деревьев с дополнительными вершинами (деревьев Штейнера)»
Теория графов = раздел дискретной математики, изучающий свойства графов. В общем смысле граф представляется как множество вершин (узлов), соединённых рёбрами. В строгом определении графом называется такая пара множеств G=(V,E), где V есть подмножество любого счётного множества, а E = подмножество V*V.
Теория графов находит применение, например, в геоинформационных системах (ГИС). Существующие или вновь проектируемые проектирования информационные сети и т. п. рассматриваются как вершины, а соединяющие их дороги, инженерные сети, линии электропередачи и т. п. = как рёбра. Применение различных вычислений, производимых на таком графе, позволяет, например, найти кратчайший объездной путь или ближайший продуктовый магазин, спланировать оптимальный маршрут.
При изображении графов чаще всего используется следующая система обозначений: каждой вершине сопоставляется точка на плоскости, и если между вершинами существует ребро, то соответствующие точки соединяются отрезком. В случае ориентированного графа отрезки заменяют стрелками.
Не следует путать изображение графа с собственно графом (абстрактной структурой), поскольку одному графу можно сопоставить не одно графическое представление. Изображение призвано лишь показать, какие пары вершин соединены рёбрами, а какие = нет. Часто на практике бывает трудно ответить на вопрос, являются ли два изображения моделями одного и того же графа или нет. В зависимости от задачи, одни изображения могут давать более наглядную картину, чем другие.
Для поиска кратчайших маршрутов существует множество алгоритмов, самые популярные:
- Алгоритм Дейкстры
- Алгоритм Форда
- Алгоритм Флойда
- Волновой алгоритм
В данной работе будет рассмотрены алгоритмы построения минимальных связывающих деревьев без дополнительных вершин (деревья Прима-Краскала) и с дополнительными вершинами (деревья Штейнера).
