Минимизированное вложение произвольных гамильтоновых графов в отказоустойчивый граф и реконфигурация при отказах. II. Решетки и $k$-отказоустойчивость

Даны оптимальные алгоритмы построения 1-отказоустойчивых структур на примерах простых и диагональных решеток и тора в соответствии с алгоритмом А2, рассмотренным в первой части работы. Приведена общая процедура построения $k$-отказоустойчивых структур сначала для простого цикла, затем для более сложных графов-решеток. Даны алгоритмы реконфигурации после возникновения отказа в структуре. Для 1-отказоустойчивых структур эти алгоритмы реализуются через простую таблицу автоморфизмов отказоустойчивого графа. Для случая $k$-отказоустойчивости корректная реконфигурация требует процедуры симметрирования редуцированного графа после $i$-го отказа путем удаления избыточных связей, введенных для увеличения отказоустойчивости с $i-1$ до $i$ при построении $k$-отказоустойчивого графа системы.

Статья представлена к публикации членом редколлегии: П. П. Пархоменко