Шрифт:
Закладка:
Предположим, что 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 двудольный, путь, который начинается и заканчивается в одной и той же вершине, должен иметь четное число ребер. Поэтому в нем не может быть также граней с тремя сторонами.
В общем случае справедлива следующая теорема.
Граф Kn не является планарным для n ≥ 5, а граф Km n не является планарным, когда одновременно m ≥ 3 и n ≥ 3.
Оказывается, что в некотором смысле K5 и K3,3 — единственные препятствия, мешающие графу быть планарным. Знаменитая теорема Куратовского-Понтрягина утверждает, что граф может быть непланарным, только если он содержит в качестве подграфа K5 или K3,3. Например, граф на рис. 13.9 непланарный, потому что содержит копию K5.
Рис. 13.9. Пример непланарного графа, содержащего K5
Далее мы приведем еще одно интересное применение формулы Эйлера, называемое теоремой Пика. Ее доказал Георг Александр Пик (1859-ок. 1943) в 1899 году105. Пик был австрийским математиком, большую часть жизни прожил в Праге. Он погиб в концлагере Терезиенштадт в Чехословакии.
Для формулировки теоремы Пика обратимся к математическому планшету — популярному средству обучения, изобретенному Калебом Гаттеньо (1911–1988), который прекрасно помогает детям изучать основы геометрии. Математический планшет можно изготовить самостоятельно — нужно только вбить в доску гвозди, так чтобы они образовывали квадратную сетку. Учащиеся натягивают на гвозди резинки, формируя разные многоугольники (рис. 13.10). С помощью планшета учитель может обсуждать такие геометрические понятия, как периметр, угол, площадь и теорему Пифагора.
Рис. 13.10. Многоугольник на математическом планшете
Теорема Пика дает простой способ вычисления площадей даже очень сложных невыпуклых многоугольников (мы, однако, требуем, чтобы резинка не пересекала самое себя).
Теорема Пика
Если на границе многоугольника находится B гвоздей, а внутри многоугольника I гвоздей, то его площадь равна A = I + B/2 — 1.
Например, поскольку для многоугольника на рис. 13.10 B = 12 и I = 5, то его площадь равна 5 + 12/2 — 1 = 10.
Оказалось, что один лесник в Орегоне использовал приближение к теореме Пика для оценки площади леса106. Лесник взял прозрачную пластинку с нанесенной на нее решеткой точек и наложил ее на многоугольную карту своего участка. Для оценки площади он сложил число точек во внутренней области с половиной числа точек на границе (очень близко к теореме Пика!) и умножил на подходящий масштабный коэффициент.
Теорема Пика с легкостью вытекает из формулы Эйлера, при условии что нам известна площадь примитивного треугольника. Треугольник называется примитивным, если внутри него нет гвоздей, а единственные гвозди на границе находятся в вершинах (например, треугольник на рис. 13.11). Иными словами, треугольник примитивный, если B = 3 и I = 0. Удивительно, но площадь любого примитивного треугольника равна 1/2.
Рис. 13.11. Параллелограмм, построенный по примитивному треугольнику на плоскости
К сожалению, доказать этот факт довольно трудно. Вместо полного доказательства мы поясним, почему это должно быть верно. Легко видеть, что плоскость (бесконечный математический планшет) можно замостить квадратами 1*1. Такое замощение обладает тем свойством, что если сдвинуть любую плитку на единицу вверх, вниз, вправо или влево, то она совпадет с другой плиткой. Аналогично возьмем примитивный треугольник и достроим его до параллелограмма, имеющего вдвое большую площадь. Параллелограммами тоже можно замостить плоскость, сдвигая их на единицу вверх, вниз, вправо или влево. Поэтому параллелограмм, как и квадрат, должен иметь площадь 1. А значит, площадь треугольника равна 1/2.
Теперь мы можем доказать теорему Пика. Сначала построим триангуляцию многоугольника — разобьем его на T примитивных треугольников (как показано на рис. 13.12). Если считать неограниченную область гранью, то F = T + 1. Поскольку площадь каждой треугольной грани равна 1/2, то полная площадь многоугольника A = (1/2)T.
Рис. 13.12. Многоугольник разбит на примитивные треугольники
У каждой ограниченной грани три стороны, поэтому в величине 3T каждое ребро учтено дважды, за исключением граничных ребер, которые учитываются один раз. Поскольку число граничных ребер равно числу расположенных на границе вершин, имеем
3T = 2E — B,
или
Количество вершин V = I + B. Применяя формулу Эйлера, получаем
2 = V — Е + F;
Поэтому число треугольных граней равно
T = 2I + B — 2,
а полная площадь равна
что и требовалось доказать.
И в заключение опишем две игры с карандашом и бумагой. Несмотря на сходство, одна является интеллектуальным вызовом, а другая — насмешкой над игроками, поскольку исход известен еще до того, как сделан первый ход.
По словам Мартина Гарднера (1914–2010), который долгое время вел математическую колонку в журнале «Scientific American», игру «Рассада» придумали за чашкой чая одним февральским утром 1967 года Джон Хортон Конвей (1937–2020) и Майкл Патерсон из Кембриджского университета. Она стала сенсацией. Конвей писал Гарднеру, что «на следующий день после того, как рассада проросла, в нее, казалось, играли все. Во время перерыва на чай или кофе собирались группки
