Жемчужина Эйлера
- Автор: Ричесон Дэвид С.
- Год: 2021
- Язык: русский
- Жанр: Прочее научное
Электронная книга - «Жемчужина Эйлера». Краткое содержание книги:
В 1750 году Эйлер заметил, что любой многогранник, имеющий V вершин, E ребер и F граней, удовлетворяет соотношению V – E + F = 2. Из книги вы узнаете, что греки совсем не заметили эту формулу, что Декарт был в шаге от ее открытия, что математики XIX века обобщили ее в направлениях, о которых Эйлер и не подозревал, а в XX веке было доказано, что у любого тела есть своя формула Эйлера. На тщательно подобранных примерах представлены многие элегантные и неожиданные применения этой формулы, например: почему на Земле всегда существует точка, где нет ветра, как измерить площадь лесного участка, посчитав деревья на нем, и сколько разноцветных карандашей необходимо для раскрашивания любой карты.
Издание предназначено для широкого круга любителей математики.
Рис. 13.6. Полные графы K1, K2, K3, K4 и K5
С полным графом тесно связан полный двудольный граф. Он обладает тем свойством, что множество вершин можно разделить на два подмножества U и V, так что никакие две вершины, принадлежащие U, и никакие две вершины, принадлежащие V, не соединены ребром, а каждая вершина из U соединена с каждой вершиной из V ровно одним ребром. Если U содержит m вершин, а V— n вершин, то соответствующий полный двудольный граф обозначается Km,n. Графы K3,2 и K3,3 показаны на рис. 13.7. Типичный пример полного двудольного графа, который приводится в любом начальном учебнике по теории графов, — граф ресурсоснабжающих компаний. Множество U состоит из компаний (газовой, водопроводной, электрической и т. д.), а множество V — из клиентов. Поскольку каждый клиент должен получать ресурсы каждого вида, то получающийся граф полный двудольный.
Рис. 13.7. Полные двудольные графы K3,2 и K3,3
Мы хотели бы знать, какие из полных и полных двудольных графов планарные. Легко показать, что графы K1, K2, K3, K4, Km,1 и Km,2 планарные. Например, на рис. 13.8 мы видим, что K4 и K3,2 планарные. Оказывается, что все остальные графы интересующего нас вида непланарные. Воспользуемся формулой Эйлера, чтобы доказать, что K5 и K3,3 непланарные.
Рис. 13.8. K4 и K3,2 — планарные графы
Чтобы доказать, что K5 непланарный, мы воспользуемся техникой доказательства от противного. Предположим, что утверждение, которое мы хотим доказать, неверно (т. е. что граф K5 планарный), и покажем, что это приводит к логическому противоречию. Тогда можно будет заключить, что K5 непланарный. Г. Х. Харди писал: «Метод доказательства reductio ad absurdum, столь любимый Евклидом, — один из самых лучших инструментов математика. Это гораздо более “хитроумный” гамбит, чем любой шахматный гамбит: шахматист может пожертвовать пешку или даже фигуру, но математик жертвует партию»104.
Предположим, что K5 — планарный граф. Тогда мы сможем нарисовать K5 на плоскости, так что никакие два ребра не будут пересекаться. K5 имеет 5 вершин и 10 ребер. Формула Эйлера для планарных графов утверждает, что V – E + F = 2, поэтому в нашем планарном чертеже K5 должно быть 7 граней, включая неограниченную (потому что 2 = F – 10 + 5).
Каждое ребро является общей границей двух граней, поэтому 2E = pF, где p — среднее число сторон по всем граням. K5 — полный граф, поэтому в нем нет ни петель, ни параллельных ребер. Так как нет петель, то не существует граней, ограниченных только одним ребром, а поскольку нет параллельных ребер, то не существует граней, ограниченных двумя ребрами. Следовательно, среднее число ребер на одну грань должно быть не меньше трех. Это значит, что p ≥ 3 и 2E ≥ 3F. Но из того, что F = 7 и E = 10, следует, что 20 ≥ 21, т. е. мы пришли к противоречию. Поэтому K5 должен быть непланарным.
Аналогично можно доказать, что полный двудольный граф K3,3 непланарный (попробуйте сами!). Главное отличие заключается в том, что, поскольку K3,3 двудольный, путь, который начинается и заканчивается в одной и той же вершине, должен иметь четное число ребер. Поэтому в нем не может быть также граней с тремя сторонами.
В общем случае справедлива следующая теорема.
Оказывается, что в некотором смысле K5 и K3,3 — единственные препятствия, мешающие графу быть планарным. Знаменитая теорема Куратовского-Понтрягина утверждает, что граф может быть непланарным, только если он содержит в качестве подграфа K5 или K3,3. Например, граф на рис. 13.9 непланарный, потому что содержит копию K5.
Рис. 13.9. Пример непланарного графа, содержащего K5
Далее мы приведем еще одно интересное применение формулы Эйлера, называемое теоремой Пика. Ее доказал Георг Александр Пик (1859-ок. 1943) в 1899 году105. Пик был австрийским математиком, большую часть жизни прожил в Праге. Он погиб в концлагере Терезиенштадт в Чехословакии.
Для формулировки теоремы Пика обратимся к математическому планшету — популярному средству обучения, изобретенному Калебом Гаттеньо (1911–1988), который прекрасно помогает детям изучать основы геометрии. Математический планшет можно изготовить самостоятельно — нужно только вбить в доску гвозди, так чтобы они образовывали квадратную сетку. Учащиеся натягивают на гвозди резинки, формируя разные многоугольники (рис. 13.10). С помощью планшета учитель может обсуждать такие геометрические понятия, как периметр, угол, площадь и теорему Пифагора.