Формула Эйлера

#АПО_математика #Эйлер #ФормулаЭйлера

 

Сейчас мы рассмотрим одну из важнейших формул в теории графов, доказанную великим математиком (большую часть жизни, кстати, жившим в России, и похороненным в Санкт-Петребурге) Леонардом Эйлером в 1736 году. Он получил соотношение при изучении свойств выпуклых многогранников, но оказалось, что оно имеет гораздо большую общность.

 

Формула Эйлера:

 

Пусть дан связный планарный (его можно нарисовать на плоскости (или на сфере) так, чтобы рёбра не пересекались) граф G. Обозначим через V число его вершин, E - рёбер, F - граней (включая внешнюю, "бесконечную"). Тогда будет выполняться соотношение

 

V-E+F = 2.

 

Доказательство:

 

Подграф графа G, содержащий все вершины графа, называется остовным. Если оставный подграф является деревом, то он называется остовным деревом.

 

Рассмотрим какое-нибудь остовное дерево Т графа G. Очевидно, что граф Т имеет n вершин и одну грань (внешнюю). Поскольку Т – дерево, то число ребер Т равно (n-1) (это утверждение несложно доказывается, например, методом математической индукции по n). Поэтому для графа Т доказываемая формула верна.

 

Теперь будем поочеред­но добавлять к Т недостающие ребра графа G. При добавлении одного ребра число вершин не меняется, а число как ребер, так и граней увеличивается на единицу. Это значит, что доказываемая формула будет верна для всякого графа, получаемого в результате операций добавления ребер, а, значит, и для исходного графа.

 

Доказано.

 

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