Том 11. Карты метро и нейронные сети. Теория графов - Клауди Альсина

3V3 + 4V4 + 5V3 + 6V6 + … = 2A. (4)

Используя формулу Эйлера, где обе части умножены на 2, то есть 2С + 2V = 4 + 2A, учитывая (1), (2) и (3), получим:

2С3 + 2С4 + 2С5 + 2С6  + … + 2V3 + 2V4 + 2V5 + 2V6 + … = 4 + 3С3 + 4C4 + 5C5 + 6C6 + …

Иными словами,

2V3 + 2V4 + 2V5 + 2V6 + … = 4 + C3 + 2C4 + 3C5 + 4C6 + … (5)

Аналогично на основе (1), (2) и (4) получим:

2С3 + 2С4 + 2С5 + 2С6 + … + 2V3 + 2V4  + 2V5  + 2V6 + … = 4 + 3V3 + 4V4 + 5V5 + 6V6  + …

Иными словами,

2C3 + 2C4  + 2C5  + 2C6 + … = 4 + V3 + 2V4  + 3V5 + 4V6 + … (6)

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

Если прибавить к (5) выражение (6), умножив обе его части на 2, получим:

2V3  + 2V4  + 2V5 + 2V6 + … + 4С3 + 4С4 + 4С5 + 4С6 + … = 12 + С3 + 2С4  + 3С5 + 4С6 +… + 2V3 + 4V4 + 6V5 + 8V6 + …

Упростив это выражение, получим удивительный результат:

3C3 + 2C4  + C5 = 12 + 2V4 + 4V5 + … + C7 + 2С8 + … (*)

В этом выражении не фигурирует число ребер, а также отсутствуют шестиугольные грани и вершины, в которых сходятся три ребра. Запомните выражение (*): оно поможет нам совершить много удивительных открытий. Например, вспомним, какую форму имеет футбольный мяч. Это многогранник, в котором сочетаются пятиугольные и шестиугольные грани, а в каждой вершине сходятся три ребра.

Существуют ли другие многогранники, где вершины и грани обладают теми же особенностями? Заметим, что С3 = С4 = Сn = 0 при n >= 7, V4 = Vn = 0 при n >= 5, следовательно, согласно (*) должно выполняться равенство С5 = 12, но С6 остается неопределенным. Б. Грюнбаум и Т. С. Моцкин доказали, что С6 может принимать любое значение, отличное от 1. Любопытно, что пятиугольных граней именно 12.

В многограннике, образованном четырехугольниками и шестиугольниками, согласно (*) 2С4 = 12 + 2V4 + 4V5 + …, то есть минимум шесть его граней будут четырехугольниками. Если вершины будут иметь степень 3, то таких граней будет ровно 6. Если гранями многогранника являются треугольники и шестиугольники, то 3С3 = 12 + 2V4 + 4V5 + … и как минимум четыре грани будут иметь форму треугольника. Если вершины будут иметь степень 3, то треугольных граней будет ровно четыре.

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

Вспомним формулу (*) из прошлого раздела:

3C3 + 2C4 + C5 = 12 + 2V4 + 4V5 + … + С7 + 2С8 + … (*)

Заметим, что выражение в правой части больше или равно 12, то есть всегда выполняется соотношение

3С3 + 2С4 + С5 >= 12.

Кроме того, С3, С4 и С5 не могут быть равны нулю одновременно. Можно сформулировать следующую теорему:

«В любом выпуклом многограннике всегда существует как минимум одна грань в форме треугольника, четырехугольника или пятиугольника».

Другие грани могут иметь любую форму, но как минимум одна грань должна иметь три, четыре или пять ребер. Вспомним, что правильным многогранником называется выпуклый многогранник, все грани которого являются одинаковыми правильными многоугольниками и во всех вершинах которого сходится одинаковое число ребер. Тогда предыдущую теорему можно записать так:

«Единственными правильными многогранниками являются тетраэдр, октаэдр, икосаэдр, куб и додекаэдр».

* * *

ГРАФЫ, СООТВЕТСТВУЮЩИЕ ПРАВИЛЬНЫМ МНОГОГРАННИКАМ

Пять правильных многогранников необязательно изображать в перспективе — можно построить соответствующие им плоские графы. Значения V, А и С для следующих фигур представлены в таблице ниже.

Заметим, что в полученной нами теореме общее соотношение Эйлера сочетается с характеристиками многоугольников, ограничивающих часть пространства, образующего многогранник.

* * *

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

Если все грани многогранника — равносторонние треугольники (их углы равны 60°), формула (*) сводится к 3С3 = 12 + 2V4  + 4V5. В тетраэдре С3 = 4 (и, разумеется, V3  = 4, V4 = V5 = 0). Для октаэдра V4 = 6, V3 = V5 = 0 и С3 = 8. В икосаэдре С3 = 20 и V5 = 12.

Если все грани многогранника — квадраты, то в его вершинах могут сходиться только три ребра, поэтому V4 = V5 = 0 и по формуле (*) 2С4 = 12, то есть С4 = 6. Таким образом, этот многогранник — куб.

Если все грани многогранника — правильные пятиугольники, то степень его вершин может равняться только 3. По формуле (*) С5 = 12 — это додекаэдр.

* * *

ТОЧНЫЙ ПОДСЧЕТ

Пусть Р — выпуклый многогранник с r(Р) гранями. Рассмотрим два его параметра:

r(Р) — количество натуральных чисел i, таких что в Р существует грань с i ребрами;

К(Р) — число сторон грани Р с наибольшим числом вершин или ребер.

Так, в кубе Р r(Р) = 1, К(Р) = 4. Для пирамиды Р, в основании которой лежит пятиугольник, r(Р) = 2, К(Р) = 5.

Если многоугольник Р имеет грань, число сторон которой равно К(Р), так как каждая из этих сторон является ребром другой грани, то общее число граней будет равно как минимум К(Р) + 1, то есть

С(Р) >= К(Р) + 1.

Так как r(Р) не может быть больше, чем число элементов множества {3, 4, 5, К(Р)}, то

r(Р) = < К(Р) — 2.

На основании вышеприведенных неравенств для С(Р) и r(Р) имеем:

С(Р) — r(Р) >= К(Р) + 1 — (К(Р) — 2) = 3.

Если бы все грани многогранника были бы различны, то выполнялось бы равенство С(Р) = r(Р) + 3, что невозможно.

* * *

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