Page 148 - 4335

Повернемось тепер до побудови під графа G'.
Нехай вершина J-1 на профілі n зв'язана ребром
першого виду з вершиною I2 на профілі n+1. При
послідовній прибудові ребра до кожної J вершини у
випадку, коли J1 виявиться більшим, тобто, коли є
можливість появи ребер другого або третього типу, ми
можемо зустрітись з двома варіантами: або H(J-1) =
H(J), або H(J-1)¬ =H(J). Розглянемо їх. 1-й випадок: H(J-
1) = H(J). З рівності висот вершин J і J-1 випливає й
рівність
висот вершин I2 і J1, а якщо це так, то інтервал I2 - J1
відповідає умовам парності й відповідності висот за
прийнятою аксіомою. Звідси випливає, що поява ребер
другого виду можлива тільки в тому випадку, коли
висоти вершин J-1 і J співпадають і на профілі n+1 в
інтервалі Kg n+1 є вершина з висотою, рівною H(J).
2-й випадок: H(J-1) = H(J)±ВС. Неважко впевнитись, що
в цьому випадку, якщо вершина I2+1 не утворює з
вершиною J ребро першого виду, то вершина J утворює
ребро третього виду з вершиною J1, розміщеною на
тому ж профілі n, ближньою з правої сторони, що має
таку ж висоту, як і вершина J.
Дійсно, нехай на профілі n+1 ми знайшли
вершину з висотою H(J-1) = H(J) ± ВС, номер якої не
рівний I2+1. Але в цьому випадку інтервал I2-J1 не буде
відповідати умовам парності й відповідності висот,
оскільки H(I2) = H(J-1) і не дорівнює H(J1). На
противагу цьому інтервал на профілі n J-J1 відповідає
цим вимогам, тому що H(J) = H(J1).
Доведемо також, що поява ребер третього виду
можлива тільки в тому випадку, коли висоти точок I2 і
I2+1 на профілі n+1 співпадають. Виконаємо доведення
від супротивного. Припустимо, що H(J) = H(J-1)-BC,
тоді H(I2+1) повинна дорівнювати H(I2)+BC, оскільки у
випадку H(I2 + 1)=H(J - 1) - BC, вершина I2 + 1 буде
139