Методичка (сети)

Алгоритм Ивена

Пронумеруйте узлы от 1 до N.
Сформируйте подмножество из узлов с номерами от 1 до m, где m – искомая связность.
Проверьте, что каждый узел в этом подмножестве имеет по крайней мере m маршрутов с разделенными узлами к каждому из других узлов в этом подмножестве.
Если предыдущий шаг неуспешен, то связность – меньше m. Если успешен, то перейдите к следующему этапу.
Для каждого из оставшихся j узлов (m<=j<=N) сформируйте подмножество узлов (L), содержащее набор, заданный в шаге 1 (размер m), увеличенный на число узлов из множества J.
Добавьте к сети новый узел X и соедините его с каждым узлом множества L. Проверьте, что между узлом X и каждым узлом j существует по крайней мере m маршрутов с разделенными узлами. Затем добавьте к множеству L узел j, удаленный из множества J, и продолжите процедуру со следующим узлом j.

Если выполнение всех шагов завершается успехом, сеть имеет связность по крайней мере равную m. Неудача в любом пункте алгоритма означает, что связность не обладает этим значением.

В качестве примера выберите m=3 узлам (B, E и F) и подтвердите, что в этом множестве между каждой парой узлов имеется m=3 путей (рис. 12).

BE: BE, BAFE, BCDE

BF: BAF, BCDF, BEF

EF: EF, EDF, EBAF

Рис. 12 Пример алгоритма Ивена – первый шаг

Д обавьте к сети новый фиктивный узел X и соедините его с узлами B, E и F. Выберите другой узел – C, и подтвердите, что между C и новым узлом X имеется m=3 путей (рис. 13).

CX: CBX, CAFX, CDEX

Рис 13. Пример алгоритма Ивена – второй шаг

Присоедините C к фиктивному узлу X. Выберите другой узел, A, и подтвердите, что между A и новым узлом X имеется m=3 путей (рис. 14).

AX: ABX, ACX, AFX

Содержание