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

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

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

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

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

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

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

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

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

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

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

Если проверки всех шагов проходят удовлетворительно, то сеть имеет связность, равную, по крайней мере, 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.