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

Материал из Викиконспекты
Версия от 15:18, 19 октября 2010; Vladimir.nesmelov (обсуждение | вклад) (Добавлены категории)
Перейти к: навигация, поиск
Теорема (Формула Эйлера):
Для произвольного плоского связного графа [math]G[/math] с [math]V[/math] вершинами, [math]E[/math] ребрами и [math]F[/math] гранями справедливо следующее соотношение:
[math]V - E + F = 2[/math]
Теорема (Следствие из формулы Эйлера):
Пусть [math]G[/math] произвольный граф с [math]V[/math] вершинами ([math]V \ge 3[/math]), [math]E[/math] ребрами и [math]F[/math] гранями. Тогда [math]E \le 3V - 6[/math]
Доказательство:
[math]\triangleright[/math]
Поскольку [math]G[/math] не содержит петель и кратных ребер, то каждая грань граничит хотя бы с тремя ребрами. Пусть, двигаясь вдоль [math]i[/math]-й грани мы пройдем [math]l_i[/math] ребер. Очевидно, что [math]\sum_{i=1}^{F}l_i = 2E[/math]. Поскольку [math]l_i \ge 3 (i = 1..F)[/math], получаем [math]3F \le 2E[/math]. Из формулы Эйлера [math]3E - 3V + 6 = 3F \le 2E[/math], то есть [math]E \le 3V - 6[/math].
[math]\triangleleft[/math]

Литература

  • Асанов М,, Баранский В., Расин В. - Дискретная математика - Графы, матроиды, алгоритмы