Теория многогранников

m – n + l = 2.

В случае, изображенном на рисунке 3, все условия теоремы Эйлера выполнены, m=12, n=18, l=8 и m–n+l=2. На рисунках 4 и 5 изображены случаи, когда условия этой теоремы не выполняются. Так, на рисунке 4 из точки A₁ нельзя попасть в точку A₅ и m–n+l=3≠2, а на рисунке 5 линия, соединяющая точки A₁ и A₂, является самопересекающейся и опять m–n+l=3≠2.

Рис. 3.

Рис. 4.

Рис. 5.

В некоторых задачах совокупность, состоящую из нескольких точек и  соединяющих их попарно непересекающихся дуг, мы называем картой; при этом точки  из этой совокупности мы называем вершинами, а области, на которые дуги делят  плоскость, — странами.

Теперь мы можем перейти к  решению задач.

ЗАДАЧА 1. Можно ли десять городов соединить между собой непересекающимися дорогами так, чтобы из каждого города выходило пять дорог, ведущих в пять других городов?

Решение. Предположим, что города можно соединить между собой дорогами так, как указано в задаче. В таком случае, если какие-то два города окажутся не соединенными дорогой непосредственно, то найдётся третий город, который уже будет непосредственно соединён с каждым из них. Изобразив на плоскости города точками, а дороги — дугами, получим, что любые две точки соединены цепочкой дуг. Так как в каждой точке сходятся пять дуг, то общее число дуг равно ·5·10 = 25. Согласно теореме Эйлера эти дуги делят плоскость на 2 + 25 – 10 = 17 областей. Каждая из этих семнадцати областей ограничена, по крайней мере, тремя дугами, так как в противном случае нашлись бы два города, непосредственно соединённые по крайней мере двумя дорогами, а это противоречит условию задачи. Следовательно, число дуг не меньше ½·3·17 = 25,5. Таким образом, исходное предположение приводит нас к противоречию, и города нельзя соединить между собой так, как это требуется в задаче.

ЗАДАЧА 2. Три поссорившихся соседа имеют три общих колодца. Можно ли провести непересекающиеся дорожки от каждого дома к каждому колодцу?

Решение. Предположим, что это сделать можно. Изобразим дома синими, а колодцы — чёрными точками и каждую синюю точку соединим дугой с каждой чёрной точкой так, чтобы девять полученных дуг попарно не пересекались. Тогда всякие две точки, изображающие дома или колодцы, будут соединены цепочкой дуг, и в силу теоремы Эйлера эти девять дуг разделят плоскость на 9–6+2=5 областей. Каждая из пяти областей ограничена по крайней мере четырьмя дугами, так как по условию задачи ни одна из дорожек не должна непосредственно соединять два дома или два колодца. Поэтому число дуг должно быть не меньше ½·5·4 = 10, и, следовательно, наше предположение неверно.

ЗАДАЧА 3. Докажите, что на всякой карте найдётся страна, граничащая не более чем с пятью странами.

Решение. Если число стран на карте не превосходит шести, то утверждение задачи очевидно. Мы докажем, что на карте, имеющей более шести стран, найдутся даже четыре страны, каждая из которых граничит не более чем с пятью странами. Окрасим вершины и дуги исходной карты в чёрный цвет, а красной краской отметим в каждой стране по одной точке. Всякие две отмеченные точки, лежащие в соседних странах (то есть странах, имеющих общую граничную дугу), соединим внутри этих стран красной дугой так, чтобы красные дуги попарно не пересекались. Тогда всякие две красные точки будут соединены цепочкой дуг, и так как никакие две построенные дуги не будут соединять одни и те же точки, то каждая страна на карте, состоящей из точек и дуг красного цвета, будет ограничена не менее чем тремя дугами. Если какая-то страна на этой карте ограничена более чем тремя дугами, то на её границе можно выбрать две вершины, не соединённые дугой, и соединить их красной дугой внутри этой страны. Повторяя несколько раз эту операцию, мы получим красную карту, на которой каждая страна ограничена ровно тремя дугами. Так как, кроме того, на этой карте никакие две дуги не соединяют одни и те же вершины и так как число вершин больше трёх, то из каждой вершины выходят не менее чем три дуги. Обозначим через n число дуг, через l — число стран, через m — число всех вершин красной карты и через a — число вершин, из которых выходят менее чем шесть дуг. Тогда получим

3l = 2n,            (1)

3a + 6(m – a) ≤ 2n.          (2)

Из формулы (1) и теоремы Эйлера, применённой к системе точек  и дуг красного цвета, следует, что

2n = 6m – 12,

3a + 6(m – a) ≤ 6m – 12

которое показывает, что a≥4. Остаётся заметить, что если некоторая страна на чёрной карте имеет больше пяти соседей, то из отмеченной в этой стране красной точки выходит больше пяти дуг, и потому, в силу неравенства a≥4, на чёрной карте найдутся четыре страны, каждая из которых имеет  не больше пяти соседей.

ЗАДАЧА 4. Можно ли семиугольник разрезать на выпуклые шестиугольники?

Решение. Предположим, что какой-то семиугольник удалось разрезать на выпуклые шестиугольники. Обозначим число тех вершин шестиугольников, которые лежат внутри исходного семиугольника, через m, а число оставшихся вершин (то есть лежащих на границе семиугольника) — через m'. В качестве дуг, соединяющих вершины, выберем прямолинейные отрезки сторон многоугольников, удовлетворяющие следующему условию: отрезок должен соединять две вершины и не проходить через остальные вершины. Обозначим через n число таких дуг и через l — число областей, на которые эти дуги делят плоскость (число l на единицу больше числа шестиугольников). Ясно, что любые две вершины окажутся соединёнными цепочкой дуг. В силу теоремы Эйлера

m + m' – n + l = 2.          (3)

Так как внешняя область ограничена m' дугами, а каждая из остальных —  не менее чем шестью дугами, то

2n ≥ 6(l – 1) + m'.           (4)

Из некоторых вершин на границе  семиугольника выходят только две  дуги. Обозначим число таких вершин через a. Из всякой другой вершины выходят  по крайней мере три дуги, так  что

3m + 3(m' – a) + 2a ≤ 2n.

Отсюда в силу равенства(3)

n ≤ 3l + a – 6.

Сравнивая это неравенство и  неравенство(4), мы получаем

2a – m' ≥ 6.            (5)

Так как на границе семиугольника  найдутся по крайней мере две вершины, из которых выходят дуги, ведущие  внутрь семиугольника, то m' – a ≥ 2. Из этого  неравенства и неравенства (5) следует, что a ≥ 8.

С другой стороны, так как семиугольник разрезан на выпуклые многоугольники, то всякая вершина, из которой выходят  две дуги, является вершиной семиугольника, и потому a ≤ 7. Таким образом, семиугольник нельзя разрезать на выпуклые шестиугольники.

ЗАДАЧА 5. Гранями некоторого выпуклого многогранника являются только четырехугольники. Сколько он имеет вершин и граней, если Р=12? Р=15?

Решение. Пусть n – число сторон каждой грани. Тогда Гn=2Pб т.к. каждое ребро принадлежит двум граням. Отсюда .

1) При n=4, Р=12  

Применяя теорему Эйлера, получаем: В=2+Р-Г=2+12-6=8. Т.е. у данного выпуклого  многогранника 6 граней, 8 вершин, 12 ребер.

2) При n=4, Р=15  

Следовательно, такой многогранник не существует.

ЗАДАЧА 6. Из каждой вершины выпуклого многогранника выходят 4 ребра. Сколько он имеет вершин и граней, если Р=20?

Решение. Пусть количество ребер, выходящих из каждой вершины – m, по условию m=4, тогда Вm=2Р, т.к. каждое ребро принадлежит двум вершинам. Отсюда: .

При m=4, Р=20 получим В=10, используя теорему Эйлера, вычисляем Г=2+20-10=12. Т.Е. у данного многогранника 12 граней, 10 вершин, 20 ребер.

 

§ 9. Леммы Коши

 

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

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

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

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

а)	б)
Рис. 4.

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

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

Тогда

Г=Г₃+Г₄+Г₅+Г₆+...(1)

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

N 2Г₃+4Г₄+4Г₅+6Г₆+6Г₇+...(2)

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

2Р=3Г₃+4Г₄+5Г₅+6Г₆+...(3)

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

Последнее неравенство перепишем в виде

4В-8 4Р-4Г.(4)

Подставим в (4) соотношения (3) и (1):

4В-8 2(3Г₃+4Г₄+5Г₅+...)-4(Г₃+Г₄+Г₅+...)=

2iГ_i - 4Г_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-угольников на плоскости (или на сфере) соответственные стороны равны, а среди соответственных углов имеются неравные. Отметим знаком "+" (или "-") вершины тех углов первого многоугольника, которые строго больше (или меньше) соответствующих углов другого. Тогда число перемен знака при обходе вершин первого многоугольника не меньше четырёх.

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

Возьмём на многоугольнике =A₁A₂... A_n точки E и F, лежащие между вершинами с разными знаками (рис. 3). Возьмём теперь на многоугольнике =B₁B₂... B_n соответствующие точки G и H, т. е. такие, что A_iE=B_iG, A_jF=B_jH (см. рис. 3).

Рис. 5.

Сравним ломаные EA_i... A_jF и GB_i... B_jH. Среди углов A_k первой ломаной есть хотя бы один, который строго больше соответствующего угла второй, а все остальные углы A_k не меньше своих визави. Поэтому ломаную EA_i... A_jF можно получить из ломаной GB_i... B_jH увеличением углов последней. Представляется очевидным, что в результате такой деформации ломаной замыкающая её хорда должна увеличиваться, т. е. EF>GH. Это неравенство следует из теоремы Коши о многоугольниках (см. ниже). Хорда EF стягивает и другую ломаную --- EA_i-1... A_j+1F, которая получается из ломаной GB_i-1... B_j+1H уменьшением углов последней. Поэтому EF<GH. Два противоречащих друг другу неравенства показывают, что предположение о наличии ровно двух перемен знака неверно. Аналогичные рассуждения показывают, что число перемен знака не может равняться и нулю. Следовательно, перемен знака не меньше четырёх, что и требовалось доказать.