Полиномиальные и труднорешаемые задачи

Остовное дерево связного неориентированного графа с n вершинами — неориентированное дерево, содержащее все n вершин и n-1 ребро исходного. Любой граф имеет N = n​ n-2​ остовных дерева. Алгоритм Прима​ ​ . 1. Выбрать начальную вершину, пометить ее как выбранную 2. Определить веса между выбранной вершиной и всеми остальными 3. Выбрать вершину с наименьшим весом и зафиксировать данное ребро и вес 4. Выбранную вершину исключить из перечня невыбранных 5. Вернуться в 1.Алгоритм Крускала. Построение дерева начинается с графа, который содержит все вершины изначального без ребер. Каждая вершина представляет собой компоненту связности. Построение дерева сводится к формированию набора связных компонент, постепенно из которых собирается остов. 1. T = <V, 0> 2. Упорядочить ребра по весу 3. Выбрать минимальное и включить в T 4. Выбрать следующее ребро: если оно связывает 2 вершины из разных компонент — добавить, иначе отбросить 5. Повторить 4 Алгоритм Борувки 1. Каждая вершина включается в T = <V, 0> 2. Для каждой вершины ищем минимальное ребро и добавляем в граф, если они соединяют разные компоненты. Алгоритм может работать неправильно, если есть одинаковые ребра по длине. Поэтому нужно выбирать ребро с наименьшим номером.

Мы поможем в написании ваших работ!