Полностью динамические минимальные остовные деревья: различия между версиями

Инвариант (3) может использоваться для доказательства утверждения, что среди всех ребер замены ребро с минимальным весом будет находиться на максимальном уровне. Пусть <math>e_1 \; </math> и <math>e_2 \; </math> – два ребра замены с <math>w(e_1) < w(e_2) \; </math>; пусть <math>C_i \;</math> – цикл, порожденный <math>e_i \;</math> в F, i = 1, 2. Поскольку F – минимальный остовный лес, <math>e_i \; </math> имеет максимальный вес среди всех ребер в <math>C_i \;</math>. В частности, поскольку, согласно предположению, <math>w(e_1) < w(e_2) \; </math>, <math>e_2 \; </math> также имеет максимальный вес среди ребер в цикле <math>C = (C_1 \cup C_2) \setminus (C_1 \cap C_2)</math>. В силу инварианта (3), ребро <math>e_2 \; </math> имеет минимальный уровень в C, что доказывает, что <math>\ell (e_2) \le \ell (e_1) \; </math>. Таким образом, рассмотрение недревесных ребер от максимального до минимального уровня является корректным.