Шрифт:
Существует ли гамильтонова цепь в ромбододекаэдре? Коксетер отвечает на этот вопрос решительным «нет», приводя гениальное доказательство: если бы в ромбододекаэдре существовала гамильтонова цепь, которая бы начиналась и заканчивалась в одной из его вершин, то она проходила бы через 14 вершин по одному разу, причем каждый раз цвет вершин чередовался (с черного на белый или с белого на черный). Такое чередование цветов невозможно, так как в черный цвет окрашено шесть вершин, а в белый — восемь.
* * *
ГАРОЛЬД КОКСЕТЕР (1907–2003)
Гарольд Скотт Макдональд Коксетер родился в Лондоне, изучал математику в Тринити-колледже Кембриджа, но вся его научная карьера прошла в Канаде, в Торонтском университете, где он проработал 60 лет. Его считают одним из величайших геометров XX века, он является автором 12 важных трудов и множества работ, выполненных в соавторстве с другими блестящими геометрами. Он внес неизмеримый вклад в изучение многогранников, в частности многогранников, расположенных в пространстве, имеющем более трех измерений. Коксетер дружил со знаменитым голландским художником М. Эшером, который отразил в своих картинах множество свойств, открытых Коксетером.
* * *
Графы на неплоских поверхностях
Хотя графы обычно изображаются на плоскости, задачи о раскраске графов и анализ их планарности стимулировали изучение графов, расположенных на других поверхностях: сферах, торах, цилиндрах и так далее. Графы также изображаются в трехмерном пространстве, как, например, при решении задач теории узлов.
Анализ графов на различных поверхностях помог определить множество топологических свойств, которые являются инвариантными относительно непрерывных деформаций и лежат в основе классификации кривых и поверхностей. Представим надутый шарик, на поверхности которого фломастером нарисован граф. Если мы будем сминать шарик (но так, чтобы он не лопнул), то заметим, что свойства графа будут оставаться неизменными (число вершин, ребер; число ребер, инцидентных каждой вершине, и другие свойства).
Еще один любопытный пример — граф, построенный на ленте Мёбиуса. Если даны четыре точки на плоскости и мы хотим построить плоский граф, соединяющий каждую точку с остальными тремя, у нас не возникнет затруднений при решении этой задачи. Для этого нужно расположить четыре точки в вершинах четырехугольника, соединить две противоположные точки диагональю, остальные две — линией, проходящей вне четырехугольника. Однако соединить каждую из пяти точек с остальными четырьмя уже не получится, так как появятся нежелательные пересечения ребер (напомним, граф К5 не является плоским).
Чтобы построить модель ленты Мёбиуса, нужно взять вытянутую прямоугольную полоску бумаги и склеить ее края, предварительно повернув один из них. Если не поворачивать один из краев перед склеиванием, получится обычный цилиндр. Благодаря своей особой форме лента Мёбиуса обладает интересным свойством: она имеет только одну сторону. Цилиндр делит пространство на две части, внутреннюю и внешнюю, но с лентой Мёбиуса этого не происходит: у нее всего одна сторона.
Можно ли построить на ней такой граф с пятью вершинами, чтобы каждая из них соединялась с четырьмя другими? На следующем рисунке Мигеля де Гузмана показано, что эта задача не имеет решения на плоскости, но решаема на ленте Мёбиуса.
Мигель де Гузман всегда считал, что игры и головоломки составляют основу математики.
Обозначим пять точек ABCDE на ленте Мёбиуса так, чтобы получился четырехугольник ABCD, а точка Е располагалась в его центре. Таким образом, ее сразу можно соединить с четырьмя другими точками. На ленте (у которой всего одна сторона!) можно провести линию из точки В в точку D и из точки А в точку С, как показано на рисунке выше. Все пять точек окажутся соединены между собой согласно условию задачи.
Конечные геометрии
Представьте себе плантацию, где в несколько рядов высажены деревья или другие растения. Очевидно, что их можно представить в виде графа, имеющего множество изолированных вершин, не соединенных ребрами. Предположим, что мы хотим составить схему полетов небольшого самолета, который будет опрыскивать посадки, или же возможный маршрут сбора плодов. Такой маршрут укажут ребра графа.
Множество задач подстегнули интерес к конечным геометриям — геометрическим системам, имеющим конечное количество точек и линий, которые представляют собой некие совокупности этих точек.
На предыдущем рисунке с помощью графа представлена конечная геометрия, имеющая пять точек 1, 2, 3, 4, 5 и следующие «линии», образованные точками: {1, 2}, {1, 3}, {1, 4}, {1, 5}, {2, 5}, {3, 4, 5}. Как можно видеть из этого примера, связь между графами и конечными геометриями очевидна.
Подобно тому как в традиционной геометрии с бесконечным множеством точек и линий можно сформулировать ряд аксиом, подобных аксиомам Евклида, так и в конечной геометрии можно ввести различные аксиомы и говорить о пересечениях (общих точках) и параллельных линиях (линиях без общих точек).