Page 149 - 4335

складати ребро першого виду з вершиною J. Згідно з
доведеним вище вершина I2 + 1 не утворює ребро
другого виду з вершиною на профілі n+1, бо H(J) ≠ H(J-
1). З іншої сторони, висоти всіх вершин в інтервалі J-J1
будуть меншими H(J) і при підході зліва до вершини J1
різниця H(J1) - H(J1-1) буде додатня або рівна 0. Тому
висота H(J1 + 1) буде рівна або H(J1), або H(J1) + BC.
Висота точки з номером J1 + 2 буде рівна або H(J1) +
BC, або H(J1) + 2BC, тобто висоту H(J1) + 2BC = H(I2 +
1) можуть мати лише точки J1 + 2, J1 + 4 і т.д. Але ці
точки не утворюють із точкою J інтервалу, який містить
парну кількість вершин. Значить, якщо допустити, що
вершина I2 + 1 має іншу висоту ніж H(I2) і точка J
утворює ребро з вершиною J2 на профілі n, то хоча б
одна з вершин графу в інтервалі (J1 - J2) має степінь
рівну 0, що суперечить прийнятій нами аксіомі, звідки
випливає, що поява ребер третього виду можлива тільки
за умови , що H(I2) = H(I2 + 1).
Доведені нами властивості під графу G
дозволяють скласти порівняно простий алгоритм
автоматичної побудови дискретного каркаса
горизонталей. Суть його в наступному. Послідовно, для
кожної пари, починаючи з утвореної першими
вершинами на профілях n і n + 1, ми перевіряємо
ідентичність висот і порядкових номерів вершин. У
випадку співпадіння цих параметрів з'єднуємо ці
вершини ребром першого виду. У противному випадку,
шукаємо на профілі n + 1 першу справа вершину J1 із
висотою рівною H(J). Якщо J = 1 і інтервал 1 - J1
відповідає умовам парності й відповідності висот,
з'єднуємо вершини в цьому інтервалі ребрами другого
виду. Якщо J ≠ 1, перевіряємо рівність висот H(J - 1) і
H(J). Якщо H(J - 1)=H(J), то з'єднуємо ребрами другого
виду вершини в інтервалі I2 - J1. Якщо H(J - 1) ≠H(J), то
знаходимо на профілі n першу справа вершину J1 із
140