Том 11. Карты метро и нейронные сети. Теория графов

При переходе к пределу имеем:

Иными словами, постоянные а и Ь связывает равенство

2а + 2Ь = ab,

что можно записать в таком виде:

(а — 2)(Ь — 2) = 4.

Все возможные натуральные решения этого уравнения представлены в таблице:

Интересно, что это доказательство относится исключительно к теории графов и не зависит от каких-либо геометрических свойств (расстояний, углов, параллельности сторон) фигур, образующих мозаику. Например, следующие мозаики относятся к тем же трем типам, хотя очевидно состоят из других фигур. Единственная разница заключается в изоморфизме соответствующих им графов.

* * *

ФОРМУЛА НА МАРКАХ

На этой марке, выпущенной в ГДР в честь Леонарда Эйлера, изображен икосаэдр и формула A — C + V = 2 в немецком варианте. Интересный способ рассказать о формуле всему свету.

* * *

Другие геометрические задачи с графами

Помимо формулы Эйлера и ее удивительных следствий, существует множество других областей геометрии, где теория графов представляет особый интерес. Далее мы приведем несколько примеров.

Гамильтоновы циклы в многогранниках

Мы уже рассказали о том, что Гамильтон впервые представил цепи, которые сегодня носят его имя, в игре, где нужно было обойти по разу все вершины додекаэдра. (Напомним, гамильтоновы цепи — это пути в графе, которые проходят через все его вершины ровно по одному разу.) Именно поэтому позднее были предприняты попытки найти гамильтоновы цепи во всех возможных многогранниках либо показать, что они не существуют. На следующих рисунках представлены так называемый граф Гершеля и граф Петерсена — два примера графов, в которых не существует гамильтоновых цепей. Попробуйте убедиться в этом самостоятельно, проведя карандашом линию, проходящую через все вершины этих графов ровно один раз.

Перейдем в трехмерное пространство. Следуя по пути Гарольда Коксетера, попробуем отыскать гамильтоновы цепи в других многогранниках. Коксетер весьма хитроумным способом решил эту задачу для ромбододекаэдра.

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

Этот любопытный многогранник, представленный на рисунке, в соответствии с названием, имеет 12 равных граней, которые являются параллелограммами, и обладает интересным свойством: в восьми его вершинах сходится по три ребра (такие вершины обозначены кругами белого цвета), в оставшихся шести вершинах сходится по четыре ребра (такие вершины обозначены кругами черного цвета). Заметьте, что вершины, выделенные белым цветом, являются вершинами воображаемого куба. Следовательно, ромбододекаэдр можно считать кубом, дополненным шестью пирамидами, в основаниях которых находятся квадраты. Его объем равен удвоенному объему вписанного куба. Ромбододекаэдрами, так же как и кубами, можно заполнить пространство — получится мозаика в трехмерном пространстве.

Существует ли гамильтонова цепь в ромбододекаэдре? Коксетер отвечает на этот вопрос решительным «нет», приводя гениальное доказательство: если бы в ромбододекаэдре существовала гамильтонова цепь, которая бы начиналась и заканчивалась в одной из его вершин, то она проходила бы через 14 вершин по одному разу, причем каждый раз цвет вершин чередовался (с черного на белый или с белого на черный). Такое чередование цветов невозможно, так как в черный цвет окрашено шесть вершин, а в белый — восемь.

* * *

ГАРОЛЬД КОКСЕТЕР (1907–2003)

Гарольд Скотт Макдональд Коксетер родился в Лондоне, изучал математику в Тринити-колледже Кембриджа, но вся его научная карьера прошла в Канаде, в Торонтском университете, где он проработал 60 лет. Его считают одним из величайших геометров XX века, он является автором 12 важных трудов и множества работ, выполненных в соавторстве с другими блестящими геометрами. Он внес неизмеримый вклад в изучение многогранников, в частности многогранников, расположенных в пространстве, имеющем более трех измерений. Коксетер дружил со знаменитым голландским художником М. Эшером, который отразил в своих картинах множество свойств, открытых Коксетером.

* * *

Графы на неплоских поверхностях