Примеры сетевых топологий
K терминалов
Набор путей с минимальной мощностью для k-терминальной меры является деревом Штейнера с минимальной мощностью. Известно, что задача распознавания является NP сложной для ориентированных и неориентированных сетей. Из теоремы 2.3 следует, что анализ функциональной и рациональной надежности для задачи анализа имеют NP сложность. Валиант [L.G.Valiant, “The complexity the enumeration and reliability problems”, SIAM, J. Computing, 8 (1979), 410-421] приводит альтернативное доказательство, заключающееся в демонстрации того, что вычисление SN(K)=? Fi = |{S : S соответствует субграфу, который содержит путь до каждого узла в К}|, имеет сложность NP. Здесь K является набором терминалов.
