Алгоритъм на Prim, TsST
Формулиране на проблема
- Необходимо е да се приложи изпълнението на паралелния алгоритъм на Prim.
- Необходими са изчислителни експерименти.
- Необходимо е да се конструират теоретични оценки, като се вземат предвид параметрите на използваната изчислителна система.
- Сравнете получените оценки с експериментални данни.
Теоретична част
Ненасочена графика
Оптималната рамка на претеглена графика е рамка, която минимизира някаква функция от тежестите на нейните ръбове. Най-често като такава функция действа сумата от тежестите на ръбовете, по-рядко произведението. Оптималният скелет се нарича още най-късата свързваща мрежа за дадена графика. Проблемът с изграждането на най-късата свързваща мрежа се среща доста често в различни приложения.
Оптимален проблем с рамката.
Проблемът с оптималната рамка (обхващащо дърво) е както следва. Като се има предвид обикновена графика G = (V, E) и функция на тежестта върху множеството ребра u: V R. Теглото на множество X E се дефинира като сбор от теглата на съставните му ребра. В графиката Ж се изисква да се намери скелет с минималното тегло В този раздел ще приемем, че графиката G е свързана, така че решението на проблема винаги ще бъде дърво. Известни са няколко алгоритма, които решават проблема с оптималната рамка. Помислете за две от тях.
Алгоритъм на Прим.
Този алгоритъм е кръстен на американския математик Робърт Прим, който е открил този алгоритъм през 1957 г. Въпреки това, през 1930 г. този алгоритъм е открит от чешкия математик Войтех Ярник. В допълнение, Edsger Dijkstra през 1959 г. също изобретява този алгоритъм, независимо от тях.