Обобщённые графы де Брейна

Изучаются графы переходов между состояниями неавтономных автоматов, обеспечивающих при независимых равновероятных входных знаках равновероятное распределение на множестве всех состояний за минимально возможное число тактов, как это имеет место для графов де Брейна, соответствующих регистрам сдвига. Доказано, что в случае двоичного входного алфавита имеется не менее $12r-33$ попарно не изоморфных ориентированных графов с $2^r$ вершинами, обладающих таким свойством. Найдены все графы такого типа с 8 и 9 вершинами.