Задача Прима-Каскала

Многие задачи, с которыми приходится иметь дело в повседневной практике, являются многовариантными. Среди множества возможных вариантов в условиях рыночных отношений приходится отыскивать наилучшие, в некотором смысле при ограничениях, налагаемых на природные, экономические и технологические возможности. В связи с этим возникла необходимость применять для анализа и синтеза экономических ситуаций и систем математические методы и современную вычислительную технику.

Как в самой математике, так и в ее приложениях широко используются графы. Теория графов даёт исключительно удобный аппарат для моделирования структурных свойств различных систем и отношений между объектами разной природы, в том числе программных моделей.

Теория графов — раздел дискретной математики, особенностью которого является геометрический подход к изучению объектов. Первые задачи теории графов были связаны с решением математических развлекательных задач и головоломок (задача о Кёнингсбергских мостах, задача о расстановке ферзей на шахматной доске, задачи о перевозках, задача о кругосветном путешествии и др.). В общем смысле граф (сеть) G = (V, E) состоит из конечного, непустого множества m вершин (m ≤ 1) и конечного множества n неупорядоченных пар элементов [u, v] (n ≥ 0), называемых рёбрами графа G. В строгом определении графом называется такая пара множеств G = {R, V}, где V есть подмножество любого счётного множества, а R — подмножество VxV. Теория графов находит применение, например, в геоинформационных системах (ГИС). Существующие или вновь проектируемые дома, сооружения, кварталы и т. п. рассматриваются как вершины, а соединяющие их дороги, инженерные сети, линии электропередач и т. п. — как рёбра. Применение различных вычислений, производимых на таком графе, позволяет, например, найти кратчайший объездной путь или ближайший продуктовый магазин, спланировать оптимальный маршрут.

Графы могут быть представлены в ЭВМ матрицей смежности, инцидентности или матрицей весов. Существуют такие модели задач динамического программирования: модель распределения усилий (инвестиций), модель замены оборудования, поиск кратчайшего пути на графе, задачи календарного планирования, поиск критического пути, вычисление ранних и поздних сроков наступления событий.

Цель курсовой работы — решить задачу о жадном «алгоритме», посвященной нахождению минимальной суммы длин между его вершинами методом ПримаКраскала средствами SWI-Prolog.