ГЕОМЕТРИЯ КОМБИНАТОРНАЯ

На рис. 1 каждый из шести кругов имеет общую точку с кругом, расположенным внутри; при этом никакие два круга не имеют общих внутренних точек. А на рис. 2 имеется восемь квадратов, каждый из которых также имеет общую точку с внутренним квадратом (и снова фигуры попарно не имеют общих внутренних точек). А можно ли вокруг некоторой выпуклой фигуры таким же образом расположить девять равных ей фигур, полученных из исходной с помощью параллельного переноса? Ответ отрицателен, хотя доказать это и непросто.

Рис. 1

Рис. 2

Рассмотренный вопрос относится к комбинаторной геометрии новой ветви математики, сформировавшейся лишь в XX в. Она занимается различными задачами, связанными с взаимным расположением нескольких фигур (чаще всего выпуклых), с разрезанием фигур на части, с освещением границы фигуры несколькими источниками света и т. п. При этом всегда ставится экстремальная задача: найти наибольшее число выпуклых фигур, расположенных так, как говорилось выше (рис. 1, 2), найти наименьшее число параллельных световых пучков, освещающих всю границу выпуклого тела (рис. 3), и т. п. Различных постановок комбинаторно-геометрических задач очень много, причем, как правило, они легко формулируются, но решение каждой из них требует огромных усилий.

Рис. 3

В настоящее время в комбинаторной геометрии выделились несколько ведущих направлений. Одним из них является круг задач, связанных с теоремой Хелли (см. Выпуклые фигуры). Например, из теоремы Хелли следует, что для любого набора точек на плоскости, такого, что каждые три его точки можно покрыть кругом радиуса r, найдется такой круг радиуса r, который покроет все эти точки.

Вот еще пример утверждения, которое легко получить из теоремы Хелли. В параллелограмме (или иной центрально симметричной фигуре) имеется такая точка O, что на любой прямой, проходящей через O, высекаются отрезки AO,BO, отношение которых равно 1 (рис. 4). В треугольнике такой точки нет, но можно выбрать такую точку O, что отношение отрезков AO и BO заключено между 1/2 и 2 (рис. 5). Оказывается, что внутри любой выпуклой фигуры F на плоскости найдется такая точка O, для которой отношение отрезков AO и BO (на любой прямой, проходящей через O) заключено между 1/2 и 2. Треугольник в этом смысле самая несимметричная фигура.

Рис. 4

Рис. 5

Теорема Хелли и различные ее обобщения и применения составляют сегодня важный раздел комбинаторной геометрии. Причем применяется она не только в геометрии, но и во многих других областях математики. Например, в прошлом столетии русский математик П. Л. Чебышев установил ряд интересных свойств функций, «наименее уклоняющихся от нуля». А впоследствии оказалось, что свойства этих функций наиболее просто и геометрично выводятся именно с помощью теоремы Хелли.

Зарождение еще одного направления в комбинаторной геометрии связано с именем польского математика К. Борсука. Он исходил из интересного результата, полученною венгерским математиком Палом: всякая фигура диаметра d (т. е. фигура, у которой наибольшее расстояние между двумя точками равно d) может быть вмещена в правильный шестиугольник, у которого расстояние между противоположными сторонами равно d (рис. 6). Этот шестиугольник (а вместе с ним и расположенная в нем фигура) может быть разбит на три части, каждая из которых имеет диаметр <d (рис. 7). Итак, любая плоская фигура диаметра d может быть разбита на три части меньшего диаметра. Для некоторых фигур существует разбиение и на две части меньшего диаметра (рис. 8), но трех частей достаточно для любой плоской фигуры. Опираясь на этот факт, в 1930 г. Борсук сформулировал гипотезу: любая фигура диаметра d в пространстве может быть разбита на 4 части, каждая из которых имеет диаметр <d. Для шара такое разбиение показано на рис. 9. Лишь в 1955 г. английский математик Эгглстон доказал, что эта гипотеза Борсука справедлива.

Рис. 6

Рис. 7

Рис. 8

Рис. 9

Вот интересная комбинаторная проблема, еще не решенная для пространства. На рис. 10 показано, что параллелограмм можно покрыть четырьмя меньшими параллелограммами, полученными из данного гомотетиями. А иные фигуры – даже тремя меньшими «копиями» (рис. 11). Ясно, что в пространстве надо разрешить иметь восемь меньших «копий»: ведь параллелепипед нельзя покрыть семью меньшими гомотетичными параллелепипедами (поскольку сразу две вершины одной меньшей «копией» не покрываются). Но можно ли любое выпуклое тело в пространстве покрыть восемью меньшими гомотетичными телами? Это неизвестно даже для выпуклых многогранников. Гипотеза швейцарского математика Хадвигера (любое выпуклое тело может быть покрыто 8 меньшими гомотетичными «копиями») еще ждет своего решения.

Рис. 10

Рис. 11

Удивительно, что проблема Хадвигера эквивалентна следующей проблеме, поставленной советским математиком В. Г. Болтянским: какое наименьшее число пучков параллельных лучей нужно взять, чтобы осветить всю границу выпуклого тела? В частности, границу любого ли выпуклого трехмерного многогранника можно осветить восемью параллельными пучками лучей? При этом лучи, проходящие по касательной, как на рис. 12, не считаются освещающими точку касания (т.е. луч, освещающий точку M, должен после прохождения через эту точку войти внутрь тела, рис. 13). Интересно отметить, что теорема об эквивалентности указанных проблем справедлива лишь для ограниченных выпуклых фигур. На рис. 14 показано, что для параболической области F любая меньшая гомотетичная фигура содержит лишь конечную дугу MN границы фигуры F. Поэтому нужно бесконечное число «копий», чтобы покрыть всю фигуру F, т.е. для этой фигуры число Хадвигера равно ∞. А число освещающих параллельных пучков равно 1 (рис. 15).

Рис. 12

Рис. 13

Рис. 14

Рис. 15

ГРАФЫ

Графом в математике называется конечная совокупность точек, называемых вершинами; некоторые из них соединены друг с другом линиями, называемыми ребрами графа.

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

Граф на рис. 1 изображает схему дорог между селами M,A,Б,B, и Г. Здесь каждые две вершины соединены между собой ребром. Такой граф называется полным. Числа на рисунке указывают расстояния между селами по этим дорогам. Пусть в селе M находится почта и почтальон должен развезти письма в остальные четыре села. Существует много различных маршрутов поездки. Как из них выбрать наикратчайший? Проще всего проанализировать все варианты. Сделать это поможет новый граф (рис. 1, внизу), на котором легко увидеть возможные маршруты. Вершина M вверху – начало маршрутов. Из нее можно начать путь четырьмя различными способами: в A, в Б, в B или в Г. После посещения одного из сел остается три возможности продолжения маршрута, потом две, потом дорога в последнее село и вновь в M. Всего 4·3·2·1 = 24 способа. Все они на этом графе.