Энциклопедический словарь юного математика

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

Рис. 1

Расставим вдоль его ребер цифры, обозначающие расстояния между селами, а в конце каждого маршрута напишем сумму этих расстояний по маршруту. Из полученных 24 чисел наименьшими являются два числа по 28 км, соответствующие маршрутам M - B - Б - А - Г - М и M - Г - А - Б - В - М. Заметим, что это один и тот же путь, но пройденный в разных направлениях.