Изменения
Бор
,→Построение
Непосредственно построение:
#Начинаем с [[Дерево, эквивалентные определения | дерева ]] из одной вершины (корня).
#Добавляем шаблоны <tex>P_i</tex> один за другим.
#Следуем из корня по [[Основные определения теории графов | ребрам]], отмеченным буквами из <tex>P_i</tex>, пока возможно.
#Если <tex>P_i</tex> заканчивается в <tex>v</tex>, сохраняем идентификатор <tex>P_i</tex> (например, <tex>i</tex>) в <tex>v</tex> и отмечаем вершину <tex>v</tex> как терминальную.
#Если [[Основные определения теории графов | ребра]], отмеченного очередной буквой <tex>P_i</tex> нет, то создаем новые ребра и вершины для всех оставшихся символов <tex>P_i</tex>.
Это занимает, очевидно, <tex>O (|P_1| + ... + |P_k|) = O (n)</tex> времени.
