Ученые записки математических кафедр вып. 1970 г.

- а н ­ одного сокращается с некоторой буквой другого. Если слово f\ сокращается со словаки В, Вк и только с ними, то гово­ рим, что й сокращается в Bil . . , , Вк • Если калдое слово из множества А1, / ) s сокращается в словах Bt , \ а каждое Bi сокращается, в словах й ^ , то мы скажем, что A 1t ■, A s взаимно сокращаются со словами Bir , , , , Вк A ~ $ i означает, что всякая буква й сокращается в й Если «£ и Д буквы Tip и об сокращается с ДЗ , то | Д /3 ]= { очевидно. Вершинами графа Г служат все Д - подслова 71р , и каждое такое подслово V tp , что целиком содержится в некотором ф - слове, не пересекается ни с каким - словом, сокраща­ ется в некотором д - слове и не является собственным подсловом другого- подслова У1р с этими свойствами. 4 Ребрами графа Г являются только такие пары / Ц , Ух. / вершин графа, что Vi сокращается с VL . Впредь мы будем называть связанным подслово 71р вида Ю / с X - i /\ Д если оно целиком содержится в некотором Д - слове, но не сокращается ни в каком Д - слове. Подслово Д - слова вида U)'5' ( с f = ± 1 ) свободно, если оно несвязанное. ЛЕММА I . . I ) В Г нет изолированных вершин. 2) В каждой компоненте связности графа Г не более X вершин, являющихся д - словами. 3) Множество тех 'компопет графа Г , что содер­ жат- не менее трех вершип либо вершины которых содержат связанные вховдення не больше, чем X / ~3 . 4) Число различных связанных подслов Tip не больше, чем 6 X . ДОКАЗАТЕЛЬСТВО. В Г нет изолированных вершин, так как 71 яесшфатимо и у* £ Р несократимы и так как 71р= i . По Определению . Гл каждая вершина Г сокращается в вершинах Г ■ 1