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


         

искомых пути соответствуют словам, полученным


Тогда (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.

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