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

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

  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.