Максимальное и минимальное количество ребер в суффиксном дереве

Во-первых, о максимальном количестве ребер:

Это довольно легко понять, если представить ребра в двух вариантах: ребра, которые ведут к листовому узлу, и ребра, которые ведут к внутреннему узлу. Далее я предполагаю, что строка, для которой построено дерево суффиксов, имеет длину N символов.

1. О краях, ведущих к листьям. Для каждого суффикса должен быть ровно один лист, и каждый лист имеет только одно входящее ребро (и ни одного исходящего ребра). Таким образом, должно быть N ребер, ведущих к листьям.

2. О ребрах, ведущих к внутренним узлам. Как и в случае с листовыми узлами, внутренние узлы также имеют только одно входящее ребро. Поэтому, чтобы определить, сколько может быть ребер, ведущих к внутренним узлам, достаточно определить, сколько может быть внутренних узлов. Итак, каково максимально возможное количество внутренних узлов?

   Для этого важно следить, чтобы внутренние узлы вставлялись в суффиксное дерево только в точках ветвления, т.е. количество исходящих ребер внутреннего узла всегда не менее 2 (если было только одно исходящее ребро, внутренний узел не был бы построен в первую очередь). Но каждое исходящее ребро должно в конечном итоге привести к конечному узлу (возможно, после прохождения дополнительных внутренних узлов). Другими словами, каждый внутренний узел, вставленный в дерево, увеличивает общее количество конечных узлов по крайней мере на 1. Кроме того, даже дерево без каких-либо внутренних узлов должно иметь хотя бы одно ребро, выходящее из корневого узла (если только дерево не пустой). Следовательно, в непустом дереве общее количество листьев L должно быть

   L >= I + 1
   

   где I — количество внутренних узлов. И наоборот, количество внутренних узлов равно

   I <= L - 1 = N - 1
   

   Возвращаясь к исходному вопросу, количество ребер, ведущих к внутренним узлам, как мы сказали, совпадает с количеством внутренних узлов, следовательно, оно также ограничено N - 1.

Мы заключаем, что общее количество ребер равно количеству ребер, ведущих к листьям (N), плюс количество ребер, ведущих к внутренним узлам (<=N-1), поэтому его максимум равен связаны

N + (N-1) = 2N - 1

quod эрат демонстрандум.

Относительно минимального количества ребер: здесь действует тот же принцип, т. е. мы вычисляем количество ребер, ведущих к листьям, и количество ребер, ведущих к внутренним узлам, а затем складываем их вместе.

Количество узлов, ведущих к листьям, всегда равно N, т. е. N является как максимально возможным, так и минимально возможным.

Однако количество узлов, ведущих к внутренним узлам, может быть равно нулю. Например. когда во входной строке нет повторяющихся элементов, таких как abcdef, имеется ровно N ребер, каждое от корня прямо до листа. Нет точек ветвления, нет внутренних узлов. Следовательно, минимальное количество ребер, ведущих к внутренним узлам, равно 0.

В заключение отметим, что минимальное количество ребер — N + 0 = N.