Формула Эйлера
Версия от 05:14, 19 октября 2010; Lebedeva.anestezia (обсуждение | вклад)
Теорема (Формула Эйлера): |
Для произвольного плоского связного графа с вершинами, ребрами и гранями справедливо следующее соотношение:
|
Теорема (Следствие из формулы Эйлера): |
Пусть произвольный граф с вершинами ( ), ребрами и гранями. Тогда |
Доказательство: |
Поскольку | не содержит петель и кратных ребер, то каждая грань граничит хотя бы с тремя ребрами. Пусть, двигаясь вдоль -й грани мы пройдем ребер. Очевидно, что . Поскольку , получаем . Из формулы Эйлера , то есть .
Литература
- Асанов М,, Баранский В., Расин В. - Дискретная математика - Графы, матроиды, алгоритмы