205
правок
Изменения
м
→Доказательство корректности алгоритма
== Доказательство корректности алгоритма ==
Рассмотрим два узла <tex>u, v</tex> корневого дерева <tex>T</tex>. Пусть узел <tex>w</tex> - наименьший общий предок узлов <tex>u, v.</tex> Очевидно, что в поддереве с корнем <tex>w</tex> узел <tex>w</tex> будет иметь наименьшую глубину.
Осталось доказать, что всегда для любых значений <tex>I[u],\; I[v]\; \exists</tex> значение <tex>I[w]</tex>, что выполняется неравенство <tex>I[u] \le I[w] \le I[v]\;(*).</tex>
Пусть вершина <tex>u</tex> посещается раньше, чем вершина <tex>v.</tex> Тогда, если вершина <tex>v</tex> не явлется потомком вершины <tex>u,</tex> будет выполняться неравенство <tex>\;(*)</tex> (так как после посещения поддерева, содержащего вершину <tex>u</tex>, в список будет добавлена вершина <tex>w</tex>, а после - вершина <tex>v</tex>). А если вершина <tex>u</tex> является предком вершины <tex>v,</tex> то вершина <tex>u</tex> будет наименьшим общим предком вершин <tex>u, v</tex>. Очевидно, что неравенство выполняется.
