Материал из Викиконспекты
| Теорема (Формула Эйлера): |
Для произвольного плоского связного графа [math]G[/math] с [math]V[/math] вершинами, [math]E[/math] ребрами и [math]F[/math] гранями справедливо следующее соотношение:
[math]V - E + F = 2[/math] |
| Доказательство: |
| [math]\triangleright[/math] |
|
Воспользуемся методом математической индукции по количеству граней графа.
База индукции:
[math]F = 2[/math]. Граф [math]G[/math] представляет собой многоугольник с [math]n[/math] вершинами (рис. 1). Тогда [math]V = E = n[/math], значит, равенство [math]V - E + F = 2[/math] выполняется.
Индукционный переход:
Покажем, что если теорема верна для графов с [math]F[/math] гранями, то она будет верна и для графов с [math]F + 1[/math] гранями. Пусть [math]G[/math] - плоский граф, имеющий [math]V[/math] вершин, [math]E[/math] ребер и [math]F[/math] граней, и для него справедлива формула Эйлера. Добавим новую грань (пунктирная линия на рис.2), проводя по внешней грани [math]F_{\infty}[/math] некоторую элементарную цепь, соединяющую две вершины максимального цикла графа [math]G[/math]. Если эта цепь имеет [math]r[/math] ребер, то необходимо добавить [math]r - 1[/math] новых вершин и одну новую грань. Ясно, что формула Эйлера останется справедливой и для нового графа, так как [math]V' - E' + F' = (V + r - 1) - (E + r) + (F + 1) = V - E + F[/math] |
| [math]\triangleleft[/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] |
Литература
- Асанов М,, Баранский В., Расин В. - Дискретная математика - Графы, матроиды, алгоритмы
- О.Оре - Графы и их применение
