Исследовательский потенациал молодых ученых: взгляд в будущее - 2017

ХIII Региональная научно-практическая конференция аспирантов, соискателей, молодых ученых и магистрантов 194 А. С. Угаров, Я. С. Маркова РЕАЛИЗАЦИЯ АЛГОРИТМА ПРИМА-КРАСКАЛА СРЕДСТВАМИ ЛОГИЧЕСКОГО ПРОГРАММИРОВАНИЯ Научный руководитель – кандидат пед. наук, доцент Ю. М. Мартынюк Тульский государственный педагогический университет им. Л. Н. Толстого Основу многих алгоритмов обработки сетевой информации со‐ ставляют алгоритмы обхода (итерации) графов, в процессе которых производится поиск необходимой информации или определение ка‐ ких‐либо характеристик сети. Теория графов, как самостоятельная математическая дисциплина, сформировалась в тридцатые годы два‐ дцатого века и нашла широкое применение во многих разделах науки и техники. Методы теории графов успешно используются в теории информации, планировании производства, генетике и химии, на транспорте, в маршрутизации данных в интернете и многих других областях науки, техники и общественной жизни. Особенное место в теории графов занимают алгоритмы генерации минимальных ос‐ товных деревьев. Минимальное остовное дерево – это связный подграф исходного графа, содержащий все его вершины и имеющий минимальный вес. Под весом остовного дерева будем понимать сумму весов его ребер. Пример минимального остовного дерева изображен на рисунке 1. Рис. 1. Минимальное остовное дерево