Каталог книг:


Жемчужины теории многогранников - Приложение - Леммы Коши

Леммы Коши

Лемма 1 (Коши). Пусть на выпуклом многограннике некоторые ребра отмечены знаком "+" или "-". Выделим все те вершины многогранника, к которым подходит хотя бы одно отмеченное ребро. Тогда среди выделенных вершин найдется такая вершина, при обходе которой встретится менее четырех перемен знака.

Ребра, отмеченные тем или иным знаком, образуют граф. Этот граф, имеющий В вершин и Р ребер, состоит из k компонент и разбивает поверхность многогранника на Г областей. Обозначим через N общее число перемен знака при обходах всех вершин многогранника. Так как нейтральные ребра при подсчете числа N не учитываются, то число N перемен знака будет равно общему числу перемен знака при обходе вершин лишь нашего графа.

Для доказательства леммы достаточно показать, что N<4В. В действительности, мы, вслед за Коши, докажем более сильное неравенство: N ≤ 4В-8.

Легко видеть, что общее число перемен знака при обходах вершин равно общему числу перемен знака при обходах контуров всех областей (рис.26, а). Это следует из того, что каждая пара соседних ребер при обходе вершины является одновременно парой соседних ребер и при обходе контура соответствующей области и наоборот.


а) б)
Рис.26.

Так как области, на которые граф разбивает поверхность многогранника, могут оказаться довольно сложными, то необходимо чуть подробнее разобраться с тем, что такое число перемен знака при обходе контура области. Представим себе, что наша область - это озеро, а ребра, примыкающие к ней, составляют берега озера. Эти берега окаймляют, в частности, острова, полуострова. Некоторые из этих островов-полуостровов могут быть "нулевой" ширины, так как в них входят ребра, омываемые с обеих сторон этим озером (рис.26, б). Находясь в лодке возле какого-то берегового ребра, отправимся в прибрежное плавание. Плывя вдоль берега от одного ребра к следующему, подсчитываем число перемен знака. Если при этом очередное ребро имеет свободную концевую вершину, то мы оплываем это ребро сначала с одной его стороны, а затем, после вершины, это же ребро, но с другой стороны. Естественно, что перемены знака при переходе с одной стороны на другую сторону того же ребра нет. Рано или поздно наше каботажное плавание завершится возвращением к исходному ребру. Если мы при этом оплыли все береговые ребра данного озера (области), то мы подсчитали вклад данной области в общее число перемен знака. Если же имеются еще ребра, мимо которых мы не проплывали, нам нужно совершить новое прибрежное плавание, отправляясь от одного из них, и т. д. В результате мы получим полный вклад в общее число перемен знака при обходе ребер данной области. Вклад области, изображенной на рис.26, б равен 8. Просуммировав вклады по всем областям, получим общее число N перемен знака.

Обозначим через Гi число областей, ограниченных i ребрами, i ≥ 3. При этом каждое ребро считается один раз, если данная область прилегает к нему только с одной стороны, и два раза, если с обеих. Например, область, изображенная на рис.26, имеет 20 ребер.

Тогда

Г=Г3456+...(1)

Ясно, что при обходе контура i-реберной области число перемен знака не больше i, а если i нечетно, то не больше чем i-1. Поэтому

N ≤ 2Г3+4Г4+4Г5+6Г6+6Г7+...(2)

Так как каждое ребро либо принадлежит двум областям, либо считается дважды в одной области,

2Р=3Г3+4Г4+5Г5+6Г6+...(3)

Так как граф состоит из k ≥ 1 компонент, то, по обобщенной теореме Эйлера, имеем:
В-Р+Г ≥ 2.

Последнее неравенство перепишем в виде
4В-8 ≥ 4Р-4Г.(4)

Подставим в (4) соотношения (3) и (1):
4В-8 ≥ 2(3Г3+4Г4+5Г5+...)-4(Г345+...)= 2iГi-i =(2i-4)Гi =2(i-2)Гi. (5)

В неравенстве (5) коэффициент при Гi равен 2(i-2) и при i ≥ 3 не меньше ближайшего к i снизу четного числа. А именно такой коэффициент стоит при Гi в неравенстве (2). Поэтому из (2) и (5) следует требуемое неравенство N ≤ 4В-8.

Лемма 2 (Коши). Пусть у двух выпуклых n-угольников на плоскости (или на сфере) соответственные стороны равны, а среди соответственных углов имеются неравные. Отметим знаком "+" (или "-") вершины тех углов первого многоугольника, которые строго больше (или меньше) соответствующих углов другого. Тогда число перемен знака при обходе вершин первого многоугольника не меньше четырех.

Предположим, что число перемен знака при обходе вершин многоугольника равно двум. Тогда вершины многоугольника группируются в два блока: в одном нет ни одной вершины со знаком "-", во втором - нет вершин со знаком "+".

Возьмем на многоугольнике =A1A2... An точки E и F, лежащие между вершинами с разными знаками (рис.27). Возьмем теперь на многоугольнике =B1B2... Bn соответствующие точки G и H, т.е. такие что AiE=BiG, AjF=BjH (см. рис.27).


Рис.27.

Сравним ломаные EAi... AjF и GBi... BjH. Среди углов Ak первой ломаной есть хотя бы один, который строго больше соответствующего угла второй, а все остальные углы Ak не меньше своих визави. Поэтому ломаную EAi... AjF можно получить из ломаной GBi... BjH увеличением углов последней. Представляется очевидным, что в результате такой деформации ломаной замыкающая ее хорда должна увеличиваться, т. е. EF>GH. Это неравенство следует из теоремы Коши о многоугольниках (см. ниже). Хорда EF стягивает и другую ломаную - EAi-1... Aj+1F, которая получается из ломаной GBi-1... Bj+1H уменьшением углов последней. Поэтому EF<GH. Два противоречащих друг другу неравенства показывают, что предположение о наличии ровно двух перемен знака неверно. Аналогичные рассуждения показывают, что число перемен знака не может равняться и нулю. Следовательно, перемен знака не меньше четырех, что и требовалось доказать.





Это интересно!

Полезные ссылки