Изменения
→Основные свойства
|about = о количестве вершин и рёбер в графе
|statement= В <tex> B(n, l) \ |V| = n^l, |E| = n^{l+1}</tex>
|proof= Число вершин очевидно находится из определения графа и равно <tex> n^l </tex>. Число рёбер следует из доказательства предыдущей леммы: каждой вершине инцидентно ровно <tex> 2n </tex> ребер. Таким образомЗначит, <tex> |E| = \frac{1}{2} \cdot n^l \cdot 2n = n^{l+1} </tex> по [[Лемма о рукопожатиях | лемме о рукопожатиях]].
}}
|statement= В <tex> B(n, l) \ (u, v) \in E \Leftrightarrow </tex> <tex> prefix_{l-1}(v) = suffix_{l-1}(u) </tex>
|proof= <tex> \Leftarrow </tex>
Составим слово длины <tex>l+1 \ L = a \gamma b </tex>, тогда <tex> \gamma b = suffix(L), a \gamma = prefix(L) </tex> . При этом <tex> |a \gamma| = |\gamma b| = |L|-1 = l </tex>. Если выбрать <tex> a, b \ </tex> как первый и последний символ слов <tex> u, v </tex> соответственно, и взять <tex> \gamma = prefix_{l-1}(v) = suffix_{l-1}(u) </tex>, то ребро между этими вершинами есть по определению.
<tex> \Rightarrow </tex> Возьмём подстроку слова <tex> L </tex> (из определения) без крайних символов (её длина <tex> l - 1 </tex>). Так же из определения следует, что это будет суффиксом строки, соответствующей вершине <tex> u </tex>, и префиксом для строки, соответствующей <tex> v </tex>.
2. Двум разным рёбрам <tex>(u_1, v_1), (u_2, v_2) </tex> соответствует два ''различных'' слова <tex> L </tex> длины <tex> l </tex>. Иначе <tex> u_{1} = prefix(L) = u_{2} </tex> и <tex> v_{1} = suffix(L) = v_{2} </tex>. То есть это одно и то же ребро, при этом кратных рёбер в графе нет.
{{Задача
