Задача дискретной математики о разбиении множества. Графовое представление связей между объектами. Анализ и тестирование алгоритма построения кратчайшего остовного дерева для ориентированного графа на основе решения задачи линейного программирования.
Аннотация к работе
РАЗБИЕНИЕ ДИСКРЕТНОГО КОНЕЧНОГО МНОЖЕСТВА ЭЛЕМЕНТОВ НА ОСНОВЕ КРАТЧАЙШЕГО ОСТОВНОГО ДЕРЕВАОпределение связей между объектами сильно облегчается, если исходное множество всех объектов удается описать более кратким способом, чем перечисление всех объектов со всеми их свойствами. A=[aij], i,j=1,2…n, в которой: aij= m , если существует m ребер (xi, xj ), 0, если вершины xi , xj не связаны ребром (xi, xj). При описании графа списком его ребер каждое ребро представляется парой его вершин. Ребро Li,j графа выходит из вершины ri и входит в вершину tj. Если ребро образует цикл с уже включенными в остов ребрами, то оно вычеркивается из списка и просматривается следующее по списку ребро.
План
7. СОДЕРЖАНИЕ ОТЧЕТА
1. Краткое описание задачи разбиения дискретного конечного множества
2. Результаты решения задачи по пунктам 4-9 выполнения лабораторной работы
3. Выводы
БИБЛИОГРАФИЧЕСКИЙ СПИСОК
1. Новиков Ф.А. Дискретная математика для программистов. СПБ.: Питер, 2000. 304 с.(глава 9-Деревья).
2. Владимирский Б.М., Горстко А.Б., Ерусалимский Я.М. Математика. Общий курс. СПБ.: Лань, 2002. 960 с.