Параллельные алгоритмы вычисления компонент связности и минимальных остовных деревьев: различия между версиями

Без потери общности будем считать, что все веса ребер различны. В таком случае граф G имеет уникальное минимальное остовное дерево; обозначим его как <math>T^*_G \;</math>. Пусть B – подмножество ребер графа G, не содержащих циклов. B естественным образом порождает множество деревьев <math>F = {T_1, T_2, ..., T_l} \;</math>: две вершины G принадлежат к одному дереву, если они связаны ребром из множества B. B называется <math>\lambda</math>-лесом, если каждое дерево <math>T \in F \;</math> имеет не менее <math>\lambda</math> вершин. Например, если множество B пусто, то B является 1-лесом; остовное дерево является n-лесом.