Продолжение слов де Бройна
Нас, однако, интересует еще вопрос возможности продолжения слова де Бройна шага 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)-й.
Тогда (m-2) искомых пути соответствуют словам, полученным конкатенацией 0k+1, символа y, не равного 0 или х, и v. Еще один путь получается, если взять конкатенацию 0k+1 и конца v, начинающегося с индекса (i+1). В полученных словах все подслова длины k, кроме начального и конечного, различны. Аналогично показывается существование (m-1)-го обратного пути из v в 0k+1. Для m = 2 и k > 1 аналогичное выбрасывание ребер гамильтонова цикла оставит несвязанными с остальными вершины 0k и 1k, в каждой из которых имеется по петле. Значит, хотя бы одна из этих петель не может войти ни в какое продолжение исходного гамильтонова цикла, соответственно, никакое его продолжение не будет соответствовать слову де Бройна шага (k+1). Доказательство того, что 2-слово де Бройна шага k можно продолжить до 2-слова де Бройна шага (k+2), можно найти в [30]. Утверждение 6 (гипотеза).
При m = 2 для всякого k ? 2 существует слово де Бройна шага k, которое можно продолжить до слова длины mk+1+(k+1)-2, содержащего все возможные 2-слова длины (k+1), кроме одного.
Это значит, что при m = 2 некоторые (не все!) слова де Бройна (назовем их продолжающимися) можно продолжить почти до нужной длины (на 1
меньшей длины следующего слова де Бройна), а значит мы можем модифицировать предложенный выше способ построения слова длины N с максимально возможным числом разных подслов для m = 2
следующим образом: находим минимальное k, такое что 2k+k-1 ? N, строим продолжающееся слово де Бройна шага k и продолжаем его до длины N. Поскольку N ? 2k+1+(k+1)-2, мы сможем это сделать, и полученное слово будет иметь максимально возможное число разных подслов — для длин, не превосходящих k, это следует из того, что его начало является словом де Бройна шага k, а для больших длин из того, что все такие подслова в нем различны. Доказательство этого утверждения автору неизвестно, хотя оно выглядит истинным. Примеры продолжающихся 2-слов де Бройна шагов 2, 3, 4, 5, 6 приведены в Таблице 1. В этих примерах продолжающееся слово де Бройна отделено точкой от продолжения, которое дополняет его до слова, содержащего все слова длины (k+1), кроме 1k+1.
Таблица 1. Продолжающиеся 2-слова де Бройна.
Примеры можно искать как гамильтоновы пути в B(2, k+1), начинающиеся в 0k
и заканчивающиеся в 10k-1.Предположительно, такой путь всегда можно выбрать так, чтобы он пересекался с каждым циклом графа B(2, k+1) (т.е. имел хотя бы одно общее с циклом ребро), за исключением петель 0k+1 и 1k+1, тогда он дополняется до «почти эйлерова» пути, который не покрывает только ребро 1k+1.
