1632
правки
Изменения
м
Формула формула Эйлера
Следствие из формулы формула Эйлерадля многогранников
Пусть <tex>G</tex> произвольный граф с Для любого выпуклого многогранника имеет место равенство <tex>V- E + F = 2</tex> вершинами (, где <tex>V \ge 3</tex>){{---}} число вершин, <tex>E</tex> ребрами {{---}} число ребер и <tex>F</tex> гранями{{---}} число граней данного многогранника. Тогда <tex>E \le 3V - 6</tex>
Поскольку [[Файл:Hypercube.gif|350px|thumb|right|Пример невыпуклого многоугольника для которого <texdpi = 100>GV - E + F = 0</tex> не содержит петель . Многоугольник получен путем вырезания куба внутри куба.]]Для доказательства соотношения Эйлера представим поверхность выпуклого многогранника сделанной из эластичного материала. Удалим (вырежем) одну из его граней и кратных ребер, то каждая грань граничит хотя бы с тремя ребрамиоставшуюся поверхность растянем на плоскости. ПустьПолучим планарный граф, двигаясь вдоль содержащий <tex>iF' = F - 1</tex>-й грани мы пройдем внутренних граней, <tex>l_iV</tex> ребер. Очевидно, что вершин и <tex>\sum_{i=1}^{F}l_i = 2EE</tex>ребер. Поскольку Тогда справедливо уже доказанное соотношение: <tex>l_i \ge 3 (i V - E + F ' = 1..F)</tex>, получаем . Подставляем <tex>3F \le 2EF' = F - 1</tex>. Из формулы Эйлера и получаем <tex>3E V - 3V E + 6 F = 3F \le 2E</tex>, то есть <tex>E \le 3V - 62</tex>.
rollbackEdits.php mass rollback
==Двумерный случай==
{{Теорема
|about=
|statement=
Для произвольного [[Укладка графа на плоскости|плоского ]] связного графа <tex>G</tex> с <tex>V</tex> вершинами, <tex>E</tex> ребрами и <tex>F</tex> [[Укладка графа на плоскости|гранями ]] справедливо следующее соотношение:
<br/><tex>V - E + F = 2</tex>
|proof=
Воспользуемся методом математической индукции по количеству граней графа.
<br />
'''База индукции''': <br />
<tex>F = 2</tex>. Граф <tex>G</tex> представляет собой многоугольник с <tex>n</tex> вершинами (рис. 1). Тогда <tex>V = E = n</tex>, значит, равенство <tex>V - E + F = 2</tex> выполняется.
<br />
'''Индукционный переход''':
<br />
Покажем, что если теорема верна для графов с <tex>F</tex> гранями, то она будет верна и для графов с <tex>F + 1</tex> гранями. Пусть <tex>G</tex> {{---}} плоский граф, имеющий <tex>V</tex> вершин, <tex>E</tex> ребер и <tex>F</tex> граней, и для него справедлива формула Эйлера. Добавим новую грань (пунктирная линия на рис.2), проводя по внешней грани <tex>F_{\infty}</tex> некоторую элементарную цепь, соединяющую две вершины максимального цикла графа <tex>G</tex>. Если эта цепь имеет <tex>r</tex> ребер, то необходимо добавить <tex>r - 1</tex> новых вершин и одну новую грань. Ясно, что формула Эйлера останется справедливой и для нового графа, так как <tex>V' - E' + F' = (V + r - 1) - (E + r) + (F + 1) = V - E + F = 2</tex>
}}
{|align="center"
|-valign="top"
|[[Файл:Eulerformul1.png|300px|thumb|рис. 1]]
|[[Файл:Eulerformul2.png|300px|thumb|рис. 2]]
|}
{{Теорема
|id=EulerFormulaCons
|about=
следствие из формулы Эйлера
|statement=
Пусть <tex>G</tex> связный [[Укладка графа на плоскости|планарный]] обыкновенный граф с <tex>V</tex> вершинами (<tex>V \geqslant 3</tex>), <tex>E</tex> ребрами и <tex>F</tex> гранями. Тогда <tex>E \leqslant 3V - 6</tex>
|proof=
Поскольку <tex>G</tex> не содержит петель и кратных ребер, то каждая грань граничит хотя бы с тремя ребрами. Пусть, двигаясь вдоль <tex>i</tex>-й грани мы пройдем <tex>l_i</tex> ребер. Очевидно, что <tex>\sum \limits_{i=1}^{F}l_i = 2E</tex>. Поскольку <tex>l_i \geqslant 3 \hspace{3pt} (i = 1..F)</tex>, получаем <tex>3F \leqslant 2E</tex>. Из формулы Эйлера <tex>3E - 3V + 6 = 3F \leqslant 2E</tex>, то есть <tex>E \leqslant 3V - 6</tex>.
}}
==Трехмерный случай==
Покажем, что в трехмерном случае так же имеет место формула Эйлера.
{{Теорема
|about=
|statement=
|proof=
}}
{{Теорема|about=следствие из формулы Эйлера для многогранников|statement=В любом выпуклом многограннике имеется или треугольная грань, или трехгранный угол. Более того, число треугольных граней плюс число трехгранных углов больше или равно восьми.|proof=Обозначим через <tex>V_{i}</tex> число вершин выпуклого многогранника, в которых сходится <tex>i</tex> ребер. Тогда для общего числа вершин <tex>V</tex> имеет место равенство <tex>V = V_{3} + V_{4} + V_{5} + \dots</tex> Аналогично, обозначим через <tex>F_{i}</tex> число граней выпуклого многогранника, у которых имеется <tex>i</tex> ребер. Тогда для общего числа граней <tex>F</tex> имеет место равенство <tex>F = F_{3} + F_{4} + F_{5} + \dots</tex> Посчитаем число ребер <tex>E</tex> многогранника. Имеем: <tex>3V_{3} + 4V_{4} + 5V_{5} + \dots = 2E</tex>, <tex>3F_{3} + 4F_{4} + 5F_{5} + \dots = 2E</tex>. По теореме Эйлера выполняется равенство <tex>4V - 4E + 4F = 8</tex>. Подставляя вместо <tex>V</tex>, <tex>E</tex> и <tex>F</tex> их выражения, получим: <tex>4V_{3} + 4V_{4} + 4V_{5} + \dots - (3V_{3} + 4V_{4} + 5V_{5} + \dots) - (3F_{3} + 4F_{4} + 5F_{5} + \dots) + 4F_{3} + 4F_{4} + 4F_{5} + \dots =8</tex>.Следовательно, <tex>V_{3} + F_{3} =Литература8 + V_{5} + \dots + F_{5} + \dots </tex>, значит, число треугольных граней плюс число трехгранных углов больше или равно восьми.}} ==Источники информации==* Асанов М,, Баранский В., Расин В. {{- --}} Дискретная математика {{- --}} Графы, матроиды, алгоритмы(стр. 104-107)* О.Оре {{---}} Графы и их применение (стр. 131-135)*[https://ru.wikipedia.org/wiki/%D0%A2%D0%B5%D0%BE%D1%80%D0%B5%D0%BC%D0%B0_%D0%AD%D0%B9%D0%BB%D0%B5%D1%80%D0%B0_%D0%B4%D0%BB%D1%8F_%D0%BC%D0%BD%D0%BE%D0%B3%D0%BE%D0%B3%D1%80%D0%B0%D0%BD%D0%BD%D0%B8%D0%BA%D0%BE%D0%B2 Википедия {{---}} Теорема Эйлера для многоугольников]* [http://www.geometry2006.narod.ru/Lecture/Mnogogr/Mnogogr.htm Выпуклые многогранники] [[Категория: Алгоритмы и структуры данных]][[Категория: Укладки графов ]]
