Планарные графы

Будем считать отмеченные точки и вершины квадрата вершинами, а соединяющие их отрезки и стороны квадрата — рёбрами планарного графа. Для каждого куска, на которые этот граф разбивает плоскость, подсчитаем число ограничивающих его рёбер, и все полученные числа сложим. Поскольку каждое ребро разделяет два куска, то в итоге получим удвоенное число рёбер. Так как все куски, кроме внешнего — треугольники, а внешний кусок ограничен четырьмя рёбрами, то верно: Заметим, что Поэтому по формуле Эйлера получаем, что:

Решаем это уравнение и получаем Так как есть еще внешняя грань, то треугольников

Пусть не так. Тогда каждая вершина графа имеет степень хотя бы А, значит, сумма степеней всех вершин хотя бы Следовательно, получаем неравенство а из него А это в свою очередь противоречит неравенству

В двудольном графе все циклы четной длины, поэтому в каждом цикле хотя бы ребра. А, значит, и в каждой гране хотя бы ребра. Следовательно, каждой гране соответствует хотя бы ребра, а каждому ребру не более двух граней, то есть верно следующее неравенство: Теперь подставим в формулу Эйлера. Получим, что

А, значит,

Замечание. На самом деле верно более общее утверждение. Если каждый цикл графа имеет длину хотя бы То верны следующие неравенства:

Пусть — многогранник и — его внутренняя точка. Возьмем сферу с центром в настолько большого радиуса, что многогранник будет содержаться полностью внутри нее. Рассмотрим точку на границе многогранника и проведем луч Пусть этот луч пересекает сферу в точке Таким образом можно спроецировать все точки многогранника на сферу. Теперь с помощью стереографической проекции из точки, не принадлежащей ни одному ребру, уложим граф на плоскость. Предположим, что при этом некоторые ребра графа пересекаются. Тогда окажется, что стереографическая проекция небиективна — противоречие. Итак, любой многогранник — плоский граф. Для него работает формула Пусть в каждую вершину входит ребер, и у каждой грани ребер. Тогда Тогда

И теперь

Из геометрических соображений очевидно, что и Простым перебором получаем, что при имеем при имеем и при имеем а при решений нет.

Итак, всего вариантов: тетраэдр ( октаэдр икосаэдр куб додекаэдр

Лемма. Всякий угольник можно триангулировать (то есть разбить диагоналями на треугольники), причём полученный граф (стороны и диагонали являются ребрами) можно покрасить правильно в три цвета, то есть не будет ребра между двумя вершинами одного цвета. Доказательство. Будем доказывать по индукции.

База: — очевидно.

Переход: Для начала найдем угол меньше Такой очевидно есть. Обозначим вершину этого угла за Теперь рассмотрим отрезок, который соединяет соседние вершины, которые мы обозначим за и с вершиной . Если он лежит внутри многоугольника, то отрежем треугольник, который образовался. Остальной многоугольник триангулируется и раскрашивается в 3 цвета по предположению. Поэтому достаточно раскрасить вершину в цвет, в который не раскрашены и Теперь разберемся с случаем, когда отрезок пересекает другие отрезки. Проведём из вершины отрезок к ближайшему концу мешающего отрезка (ближайшему в смысле, что прямая через , которая параллельна лежит ближе к , чем все остальные). Тогда мы получили два меньших многоугольника, которые по предположению раскрашиваются и триангулируются. Цвета в этих многоугольниках переименовываются так, чтобы и в разных многоугольниках имели те же цвета. Лемма доказана.

_________________________________________________________________________________________________________________________________________________________________________________

Следствие. Внутри любого пятиугольника есть точка, из которой "видно"все точки этого пятиугольника.

Доказательство. Используя лемму выше, мы можем его триангулировать и правильно раскрасить в три цвета. Заметим, что вершина какого-то цвета будет всего одна. Тогда рассмотрим точку, которая очень близка к этой вершине, и она подойдет под условие.

_________________________________________________________________________________________________________________________________________________________________________________

Вернемся к доказательству. Будем считать, что наш граф связный. Добавим в него ребра так, чтоб каждая его грань была треугольником (Для этого достаточно рассмотреть максимальный планарный граф). После укладки эти ребра мы удалим. Теперь сделаем индукцию по количеству вершин.

База: представляется треугольником.

Переход: Так как граф планарный найдется вершина степени Докажем, что существует такая вершина, не лежащая на границе внешней грани. Пусть не так. Тогда степень каждой вершины, не лежащей на границе внешней грани степень хотя бы При этом внешняя грань является треугольником. Степень каждой вершины на границе внешней грани хотя бы но у одной из вершин она будет хотя бы иначе весь граф является треугольником. Тогда сумма степеней вершин хотя бы

но как известно противоречие. Значит, такая вершина не лежащая на границе внешней грани всё-таки есть. Удалим эту вершину. На ее месте образуется грань, которую мы триангулируем добавлением ребер. Далее по предположению индукции у нового графа есть укладка отрезками. После удаления ребер из укладки на месте грани, которая образовалась после удаление вершины , остается угольник, где Поэтому по следствию есть точка внутри этого пятиугольника, из которой видны все точки этого пятиугольника. Возьмем ее в качестве вершины укладки и соединим отрезками вершины грани.

Предположим, что раскрасить можно, тогда из неравенства для планарного графа , где рёбра и вершины соответственно, следует, что в каждом из графов на рёбрах первого и второго цветов не более рёбер, то есть всего рёбер в графе не более Но наш граф полный и в нём вершин, а значит ребёр — Противоречие.

Попытаемся удалить из данного наименьшее количество рёбер так, чтобы он стал планарным. Из неравенства понимаем, что в нём после удаления должно быть не более рёбер, а изначально в нём рёбер, значит необходимо удалить хотя бы ребра. С удалением каждого ребра исчезает хотя бы одно пересечение (иначе зачем удалять это ребро?). Таким образом, в исходном графе было хотя бы точки пересечения. Предъявим пример:

Пример (тут присутствуют не все доминошки, но те, которых нет, можно разместить произвольно):

Оценка: Предположим, что имеется хотя бы обворожительных цифр. Введём граф следующим образом: пусть клетки — это вершины, ребром соединим две вершины, если у соответствующих клеток есть общая сторона. Тогда нетрудно понять, что граф на вершинах, в которых находятся обворожительные цифры, является связным и планарным. При этом, компонента с одной обворожительной цифрой обязательно соединена ребром с компонентой с другой обворожительной цифрой, поскольку для любых двух цифр существует доминошка, на которой есть эти цифры. Но тогда на этих пяти компонентах с обворожительными цифрами образуется полный граф на вершинах, а он планарным не является, противоречие.