Kat&Pop - Рефераты - Программа ВМШ - Теорема Эйлера

Лекция.

Теорема Эйлера и классификация правильных многогранников.

Часть 1. Теорема Эйлера.

~Опр. Граф - множество точек на плоскости, некоторые из которых соединены ребрами.

Опр. Степенью вершины графа называется число ребер, выходящих из этой вершины.

Опр. Граф называется связным, если от любой его вершины можно дойти до другой по ребрам.

Опр. Связная часть графа, несвязанная со всем остальным, называется компонентой связности графа.

Зам. Считают, что у связного графа одна компонента связности.

~Опр. Путем в графе называется путешествие по графу, при котором одно ребро не проходят два раза подряд (туда и обратно).

Зам. Заметим, что если между двумя вершинами есть какая-то дорога, то есть и путь.

Опр. Циклом в графе называется замкнутый путь, не проходящий дважды через одну точку. (Упр. Найдите циклы на графах, изображенных на рисунке.)



Опр. Связный граф без циклов называется деревом.



Лемма 1. В дереве от любой вершины можно дойти до любой другой, причем по единственному пути.



Доказательство Леммы 1. Дерево - связный граф => от любой вершины можно дойти до любой другой. Проведем доказательство единственности от противного. Предположим, что от вершины 1 можно дойти до вершины 2 двумя различными способами. Первый путь: 1-А1-А2-…Аn-2 (где А - вершины, по которым проходит путь). Второй путь 1-B1-B2-…Bm-2. Рассмотрим концы двух путей и пусть 2' - вершина, после которой эти пути одинаковы, а в 2' первый и второй путь приходят из разных вершин. Не ограничивая общности, можно считать, что 2=2'. Рассмотрим путь 1-А1-…Аn-2-Bm-…-B1-1. Теперь читаем вершины подряд. Как только встретили первый раз одинаковые вершины, то получили замкнутый путь не проходящий через одну вершину дважды, т.е. мы нашли в графе цикл. А граф дерево. => возникло противоречие. => путь действительно единственный.

Лемма 2. Если в дереве больше одной вершины, то в нем есть хотя бы одна вершина степени 1.

Доказательство Леммы 2. Будем ходить по дереву по пути, т.е. ходить без возвратов. Рассмотрим любую вершину дерева. От нее куда-то отходит ребро. Пойдем туда. Т.к. мы ходим по пути => мы уже не попадем в начальную вершину (иначе от той вершины, где мы сейчас, было бы два пути к начальной вершине). Если вершина в которую мы пришли степени 1 => все хорошо. Иначе есть ребро, отличное от того, по которому мы пришли. Идем по этому ребру. Заметим, что в пройденную вершину мы уже не вернемся (аналогично тому, как не вернемся в начальную). Если вершина, в которую мы пришли, степени 1 => все доказано, иначе идем не туда, откуда пришли. И т.д. т.к. вершин конечное число, а мы не возвращаемся в уже пройденные вершины => когда-нибудь мы закончим. А закончить мы можем только в вершине степени 1. => вершина степени 1 существует.

Опр. Вершина степени 1 в дереве называется листом. (Упр. Найдите листья на рисунке, изображающем дерево.)

Зам. В дереве как минимум два листа.

Доказательство Замечания: В доказательстве Леммы 2 начнем с листа, а он существует. Таким образом придем в лист, отличный от начального.

Задачи на дом:

  1. Посчитать, сколько ребер в дереве с n вершинами.

  2. Доказать, что из произвольного связного графа можно выкинуть несколько ребер так, чтобы получилось дерево.

Опр. Граф называется плоским, если его можно расположить на плоскости так, чтобы ребра пересекались только в вершинах.

Бывают и неплоские графы. См. рис

Опр. Рассмотрим плоский связный граф, нарисованный так, что ребра пересекаются только в вершинах. Внешней гранью графа называется часть плоскости вне графа.

~Опр. Внутренней гранью графа называется часть плоскости, ограниченная циклом, которая не пересекается насквозь. Или часть плоскости, которая отпадает при разрезании по графу.

Зам. Вся плоскость распадается на грани. Грани не пересекаются между собой. У графа ровно одна внешняя грань и сколько угодно внутренних.

Количество всех вершин графа обозначим В, количество всех ребер - Р, а количество всех граней (как внутренних, так и внешних) - Г.

Упр. Для плоского графа, изображенного на рисунке посчитать число вершин, число ребер и число граней.

Теорема Эйлера. В связном плоском графе В+Г-Р=2.

Доказательство теоремы Эйлера: Если в графе есть цикл => есть внутренняя грань. Возьмем цикл, ограничивающий внутреннюю грань. Выкинем из него одно ребро. Граф остался связным, плоским. Число Р уменьшилось на один, но и число Г уменьшилось на один, т.к. две грани, которые были по разные стороны от стертого ребра стерлись. Таким образом, число В+Г-Р не изменилось. Если в графе опять есть цикл => поступаем так же. Т.к. ребер в графе конечное число, а количество ребер постепенно уменьшается => когда-нибудь это закончится. Т.е. мы придем к ситуации, что число В+Г-Р не изменилось по сравнению с первоначальным, граф остался связным, плоским и циклов в графе нет. => граф стал деревом, а грань осталась одна - внешняя. Мы знаем по лемме 2, что у дерева есть лист. Стираем лист и ребро, которое из него выходит. Число Р уменьшается на один, число В уменьшается на один, число В+Г-Р не меняется. Полученный граф снова дерево, он плоский и связный, а число вершин у него уменьшилось => поступаем так, пока не останется две вершины, соединенные ребром. Тут уже не сложно посчитать, что В+Г-Р=2+1-1=2, а число В+Г-Р не менялось => для начального графа оно тоже 2.

Теорема Эйлера для многогранников. Эйлер доказывал свою теорему для многогранников, а не для графов. Т.е. у любого выпуклого многогранника В+Г-Р=2. Это легко показать. Берем многогранник и надуваем. Получаем шарик и на нем граф. Одну грань графа вырезаем и растягиваем шарик на плоскость, при этом у многогранника была грань, которую мы вырезали (но ее надо учитывать), а у полученного графа есть внешняя грань (вот ее то мы и учтем вместо вырезанной грани). => теорема Эйлера верна для выпуклых многогранников.

Упр. Нарисуйте граф, в который преобразуется куб при таком преобразовании. А Тетраэдр? А октаедр? А другие тела?

Часть 2. Классификация правильных многогранников.

~Опр. Многогранник называется правильным, если его грани - правильные многоугольники, причем в каждой его вершине сходится равное число таких многоугольников.

Заметим, что число многоугольников, сходящихся в одной вершине - 3 или больше. Возьмем три пятиугольника - они действительно образуют уголок "шапочку". Три шестиугольника уже лежат в плоскости, а вот три семиугольника - не влезут. => грани правильных многогранников не более, чем шести угольны. Т.е. правильный многогранник может быть с гранями треугольными, квадратными и пятиугольными. Причем в одной вершине может сходиться три квадрата или три пятиугольника, или три, четыре или пять треугольников.

Вариант первый. Грани многогранника - квадраты (в каждой вершине сходится три квадрата). Пусть число вершин такого многогранника - В. => число граней 3В/4. Заметим, что в каждой вершине ребер сходится столько же, сколько и граней. Число ребер такого многогранника 3В/2. Мы знаем, что В+Г-Р=2. Составим уравнение: В+3/4 В-3/2 В=2. В=8. Т.е. у такого многогранника 8 вершин, 6 граней и 12 ребер. Т.е. это куб.

Вариант второй. Грани многогранника правильные пятиугольники (в каждой вершине сходится по три пятиугольника). Г=3В/5. Р=3В/2. В+Г-Р=2. В=20. Г=12. Р=30. Это додекаэдр.

Вариант третий. Треугольники, по три. Г=3В/3=В. Р=3В/2. =>В=4=Г, Р=6. Это тетраэдр.

Вариант четвертый. Треугольники, по четыре. Г=4В/3, Р=4В/2=2В. => В=6, Г=8, Р=12. Это октаэдр.

Вариант пятый. Треугольники, по пять. Г=5В/3, Р=5В/2 => В=12, Г=20, Р=30. Это икосаэдр.

Других правильных многогранников нет.