Таблицы Брадиса

Чему равно В Г Р?

Чему равно В Г Р?

Элементы математики в задачах - Г. А. Мерзон

Задача 30. Чему равно В + Г — Р для несвязного неориентированного плоского графа?

Решение. Поскольку для каждой компоненты связности по отдельно­сти В + Г — Р = 2, и одна грань у всех общая, имеем для всего графа В+Г — Р = 1 + К, где К—число компонент связности.

& Число В + Г — Р для связного графа, нарисованного на поверхно­сти, зависит только от самой поверхности и не зависит от конкрет­ного графа. Это число называют эйлеровой характеристикой поверх­ности. Например, для сферы с g ручками эйлерова характеристика равна 2 — 2^. Понятие эйлеровой характеристики обобщается и на многомерный случай.

Задача 31. Пусть В, Р и Г — количества вершин, ребер и граней мно­гогранника соответственно. Чему равно В + Г — Р?

Ответ. В + Г— Р= 2.

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

Первое решение состоит в следующем: накачаем многогранник воздухом изнутри так, чтобы он превратился в сферу. Тогда сетка из вершин и ребер превратится в какой-то связный граф на поверхности сферы. Выкинем произвольную грань. Тогда та часть сферы, которая осталась, является (с точностью до деформации) диском. Если поло­жить этот диск на плоскость, то возникнет обычный планарный граф, для которого все уже доказано выше.

Второе решение не использует растяжений и геометрических де­формаций. Будем рассматривать пересечения многогранника в трех­мерном пространстве с координатами Оху% с полупространствами вида 2 ^ с. Сначала, при с, близких к — оо, пересечение совпада­ет с самим многогранником. Затем плоскость 2 = с проходит через самую нижнюю вершину, и многогранник как-то меняется (нужно проследить, что величина В + Г — Р остается неизменной). Вообще, многогранник меняется только при прохождении плоскости через какие-то вершины, и в этом случае нужно отслеживать изменение величины В + Г— Р.