proof.tex

%% It is just an empty TeX file.
%% Write your code here.
        Запись $i\pi j$ означает, что $\pi$ - это путь в графе от вершины $i$ к вершине $j$.\\
        $Length(\pi)$ - сумма весов ребер, входящих в путь $\pi$.\\
        $Word(\pi)$ - слово, образаемое конкатенацией меток на ребрах, входящих в путь $\pi$ в порядке прохождения.\\
        $Shortest(i,A,j)$ - длина кратчайшего пути $i\pi j$ такого, что существует дерево вывода $Word(\pi)$ из $A$.\\
        Пусть $GoodTrees(i,A,j)$ - наименьшие по высоте деревья выводов кратчайших путей $i\pi j$, таких, что существует дерево вывода $Word(\pi)$ из $A$.\\
        
        
        Теорема\\
            Алгоритм 2 возвращает матрицу, такую, что $T_{i,j}(A) = Shortest(i,A,j)$\\
            
            
        Доказательство\\
            Пусть $T = \bigcup_{A \in N,~i,j \in V}GoodTrees(i,A,j)$ Из $T$ выберем класс $H$ наибольших по высоте деревьев. Это возможно, так как в $T$ может быть не больше $|V|^2|N|$ попарно различных по высоте деревьев.\\
                Пусть $t \in H$ и высота $t$ равна $h$, $t$ - это дерево вывода $i\pi j$ из нетерминала $A$. Тогда хотя бы одно из поддеревьев $t$ принадледжит $T$ и при этом имеет высоту $h-1$. Предположим, что это не так и все поддеревья $t$, имеющие высоту $h-1$, не принaдлежат $T$. Тогда каждое из таких деревьев можно заменить на меньшее по высоте и можно построить дерево вывода $i\pi j$ из $А$ по высоте меньше $h$, что противоречит выбору $t$. Выбирая каждый раз по