Формула Эйлера — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Новая страница: «{{Теорема |about= Формула Эйлера |statement= Для произвольного плоского связного графа <tex>G</tex> с <tex>…»)
 
Строка 9: Строка 9:
 
{{Теорема
 
{{Теорема
 
|about=
 
|about=
Следствие
+
Следствие из формулы Эйлера
 
|statement=
 
|statement=
 
Пусть <tex>G</tex> произвольный граф с <tex>V</tex> вершинами (<tex>V \ge 3</tex>), <tex>E</tex> ребрами и <tex>F</tex> гранями. Тогда <tex>E \le 3V - 6</tex>
 
Пусть <tex>G</tex> произвольный граф с <tex>V</tex> вершинами (<tex>V \ge 3</tex>), <tex>E</tex> ребрами и <tex>F</tex> гранями. Тогда <tex>E \le 3V - 6</tex>
Строка 15: Строка 15:
 
Поскольку <tex>G</tex> не содержит петель и кратных ребер, то каждая грань граничит хотя бы с тремя ребрами. Пусть, двигаясь вдоль <tex>i</tex>-й грани мы пройдем <tex>l_i</tex> ребер. Очевидно, что <tex>\sum_{i=1}^{F}l_i = 2E</tex>. Поскольку <tex>l_i \ge 3 (i = 1..F)</tex>, получаем <tex>3F \le 2E</tex>. Из формулы Эйлера <tex>3E - 3V + 6 = 3F \le 2E</tex>, то есть <tex>E \le 3V - 6</tex>.
 
Поскольку <tex>G</tex> не содержит петель и кратных ребер, то каждая грань граничит хотя бы с тремя ребрами. Пусть, двигаясь вдоль <tex>i</tex>-й грани мы пройдем <tex>l_i</tex> ребер. Очевидно, что <tex>\sum_{i=1}^{F}l_i = 2E</tex>. Поскольку <tex>l_i \ge 3 (i = 1..F)</tex>, получаем <tex>3F \le 2E</tex>. Из формулы Эйлера <tex>3E - 3V + 6 = 3F \le 2E</tex>, то есть <tex>E \le 3V - 6</tex>.
 
}}
 
}}
 +
 +
==Литература==
 +
* Асанов М,, Баранский В., Расин В. - Дискретная математика - Графы, матроиды, алгоритмы

Версия 05:14, 19 октября 2010

Теорема (Формула Эйлера):
Для произвольного плоского связного графа [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]

Литература

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