Алгоритм Клейтмана

1. Выберите любой узел N₁.

2. Убедитесь, что узловая связность узла N₁ со всеми другими узлами равна по крайней мере m.

3. Удалите узел N₁ и все его связи.

4. Выберите второй узел N₂.

5. Убедитесь, что узел N₂ имеет m-1 соединений со всеми другими узлами.

6. Удалите узел N₂ и все его связи.

7. Выберите третий узел N₃.

8. Убедитесь, что он имеет по крайней мере m-2 соединений со всеми другими узлами.

9. Повторяйте процедуру, пока не доберетесь до узла m, т.е. выберите узел N_m и убедитесь, что он соединен по крайней мере еще с одним узлом.

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

В качестве примера рассмотрим следующую сеть (рис. 9).

BA: BA, BCA, BEFA

BC: BC, BAC, BEDC

BD: BCD, BAFD, BED

BE: BE, BAFE,BCDE

BF: BAF, BCDF, BEF

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

В ыберите любой узел, например, узел B и убедитесь, что между узлом B и всеми другими узлами этой сети существует m=3 путей с разделенными узлами. Так как это условие удовлетворяется, то удалите из сети узел B вместе с его связями. Выберите другой узел, например, D, и убедитесь, что между узлом D и всеми другими узлами имеется m=3-1=2 пути с разделенными узлами (рис. 10).

DA: DCA, DEFA

DC: DC, DFAC

DE: DE, DFE

DF: DF, DEF

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

Т ак как это условие удовлетворяется, то удалите из сети узел D вместе с его связями. Выберите другой узел, например, F, и убедитесь, что между узлом F и всеми другими узлами существует m=3-2=1 путь (рис. 11).

FA: FA

FC: FAC

FE: FE

Рис. 11 Пример алгоритма Клейтмана – третий шаг

Таким образом, связность равна по крайней мере 3.

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

1. Пронумеруйте узлы от 1 до N.

2. Сформируйте подмножество из узлов с номерами от 1 до m, где m – искомая связность.

3. Проверьте, что каждый узел в этом подмножестве имеет по крайней мере m маршрутов с разделенными узлами к каждому из других узлов в этом подмножестве.

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

5. Для каждого из оставшихся j узлов (m<=j<=N) сформируйте подмножество узлов (L), содержащее набор, заданный в шаге 1 (размер m), увеличенный на число узлов из множества J.

6. Добавьте к сети новый узел 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