Вопрос 11. Минимальное остовное дерево.
Пусть дан G=(X,E) связный неориентированный.
Опр.: Остовный подграф H графа G порождающий на каждой компоненте связности графа G дерево наз. остовным деревом графа G.
Опр.: Отображение w:E→Z ставящее в соответствие каждому ребру e графа G некоторое целое число w(e)  наз. весом G. Число w(e) наз. весом ребра.
Опр.: Пара (G,w) наз. взвешенным графом.
Одна из наиболее известных задач связанных с деревьями это задача нахождения минимального остовного дерева (минимального по весу) в некотором взвешенном графе.
Алгоритм Краскала(1956г.) и алгоритм Прима(1957г.)
Пусть дан связный взвешенный граф (G,w). Определить остовное дерево минимального веса в графе G.
Алгоритм Краскала:
1) Строим T1=On+e1, где e1-ребро минимального веса графа G. w(e1)-min.
2) Если i<n-1, то строим Ti+1=Ti+ei+1, где ei+1 – минимальное по весу ребро графа G не принадлежащее Ti и не образующее с ребрами Ti цикла.
ei+1: w(ei+1)-min и не сущ. цикла в Ti+1
Алгоритм Прима:
1) Строим дерево Ti=ei, где ei-минимальное по весу ребро графа G. w(e1)-min.
2) Если i<n-1, то строим Ti+1=Ti+ei+1, где ei+1 – наименьшее по весу ребро графа G не принадлежащее Ti и имеющее строго один конец в дереве Ti