Примеры сетевых топологий
Точное вычисление некоторых коэффициентов
В разделе 2.3 мы показали, что возможность вычисления размера набора проходов l с минимальной мощностью и размера с набора разрезов с минимальной мощностью делает возможным точное определение числа коэффициентов. Когда l эффективно вычислимо, дальнейшая информация может быть часто получена с помощью вычисления Nl. В k-терминальной проблеме это по правде безнадежно, так как нужно подсчитать минимальное число деревьев Штайнера, что является #P-сложной задачей. В двух других случаях, однако, эффективные алгоритмы существуют.
Во всетерминальной проблеме Ni.равно числу деревьев связи. Кирхофф в 1847 разработал элегантный метод подсчета деревьев связи; он был разработан в форме, удобной для реализации на ЭВМ. В двухтерминальной проблеме Ni равно числу наикратчайших s,t-проходов. Болл и Провен разработали эффективную стратегию для вычисления этого числа. Было установлено, что для любого фиксированного kі 0, набор проходов размера l+k в двухтерминальной проблеме может быть эффективно вычислен.
Эффективный алгоритм для вычисления с дает нам возможность также определить точно число дополнительных коэффициентов. Эта проблема легко решаема во всех трех случаях, представляющих интерес, с использованием идентичного метода в каждом из случаев. Теорема Менгера гарантирует, что минимальный s,t-разрез имеет в точности размер с, когда максимальное число s,t-проходов с разъединенными ребрами равно с. Эта проблема легко адаптируется для задачи сетевых потоков со всеми ребрами, имеющими полосу (пропускную способность) равную 1.
Имея вычисленное с, было бы интересно вычислить Cc, число наборов разрезов минимальной мощности. Прован и Болл показали, что в двухтерминальном случае вычисление лишь этого коэффициента является #P-сложным; так как k-терминальная проблема включает в себя двухтерминальную проблему. Однако для всетерминальной проблемы был разработан метод эффективного вычисления Cc. Ломоносов и Полесски [М.V.Lomonosov and V.P.Polesskii, “Lower bound of network reliability”, Problems of Information Transmission, 8 (1972), 118-123] показали, что каждый n-узловой граф G имеет
