Тестирование софта - статьи


         

Продолжение слов де Бройна


Нас, однако, интересует еще вопрос возможности продолжения слова де Бройна шага k до слова де Бройна шага (k+1). Ответ на этот вопрос дается следующим утверждением.

Утверждение 5.

1) При m = 1 для всякого k ? 1 единственное слово де Бройна шага k представляет собой слово 0k, соответственно, оно может быть продолжено до слова де Бройна шага (k+1) 0k+1.

2) При m ? 3 для всякого k ? 1 любое слово де Бройна шага k может быть продолжено до слова де Бройна шага (k+1).
Это значит, что для m = 1 или m ? 3 существуют бесконечные слова, каждое начало которых имеет максимальное среди слов той же длины число разных подслов.

3) При m = 2 ни для какого k ? 2 ни одно слово де Бройна шага k не может быть продолжено до слова де Бройна шага (k+1), но любое такое слово может быть продолжено до слова де Бройна шага (k+2).
Для k = 1 слова де Бройна — 01 и 10; каждое из них продолжается до слова де Бройна шага 2 — 01100 и 10011.

Поскольку пункт 1 достаточно очевиден, докажем основные утверждения из пунктов 2 и 3. Отдельные утверждения этих пунктов доказаны в [30-32]. В [32], кроме того, несколько иначе доказано утверждение, что именно продолжения слов де Бройна имеют максимально возможное количество разных подслов.

Слово де Бройна шага k соответствует эйлерову циклу в графе B(m, k) и гамильтонову в графе B(m, k+1). Если выбросить все ребра этого гамильтонова цикла, при m > 2 граф B(m, k+1) останется связным (см. ниже), и эйлеровым, поскольку входящие и исходящие полустепени всех вершин уменьшатся на 1 и останутся равными. Поэтому можно дополнить выброшенный гамильтонов цикл до эйлерова цикла в B(m, k+1), который соответствует искомому продолжению.

Связность B(m, k+1) не нарушится от выбрасывания ребер гамильтонова цикла, поскольку каждую его вершину v можно соединить с 0k+1 (m-1)-м непересекающимся путем и наоборот, 0k+1 можно соединить с v таким же количеством непересекающихся путей. Для доказательства этого достаточно рассмотреть следующую конструкцию. Пусть в v i ? 0 первых символов равны 0 и x — первый символ v, отличный от 0, т.е. (i+1)-й.

Содержание  Назад  Вперед