МАЛЫЙ МЕХМАТ МГУ

Кружок 9-11 классов

Руководители Андрей Леонидович Канунников и Степан Львович Кузнецов
2008/2009 учебный год

Тема 7.2. Графы-2. Плоские графы, формула Эйлера

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

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

1.
Докажите, что в любом дереве число вершин на единицу больше числа рёбер.
2.
Докажите, что из любого связного графа можно удалить часть рёбер так, что останется дерево.

Определение. Полным графом называется граф, в котором любые две вершины соединены ребром. Полный граф с n вершинами обозначается Kn.

3.
Сколько рёбер в графе Kn?
Определение. Граф называется плоским (планарным), если его можно изобразить на плоскости так, чтобы рёбра не пересекались.
4.
Планарен ли граф K4?
Обозначения. Пусть дан граф на плоскости. Тогда В — число вершин, Р — число рёбер, а Г — число граней, т.е. частей, на которые рёбра графа разбивают плоскость.
5.
Докажите формулу Эйлера для связного графа на плоскости: В − Р + Г = 2.
6.
В квадрате отметили 20 точек и соединили их непересекающимися отрезками друг с другом и с вершинами квадрата так, что квадрат разбился на треугольники. Сколько получилось треугольников?
7.
Докажите, что а) для связного графа на плоскости 2Р ≥ 3Г, б) для связного графа на плоскости Р ≤ 3В − 6, в) последнее неравенство верно для произвольного графа на плоскости. [Во всех пунктах предполагается, что у графа хотя бы три вершины (В ≥ 3). В вырожденных случаях K1 и K2 эти неравенства неверны.]
8.
Докажите, что граф K5 не является планарным.
9.
Есть три домика и три колодца. Можно ли соединить каждый домик с каждым колодцем тропинкой так, чтобы тропинки не пересекались?

Граф, возникающий в задаче 9, называется K3,3. Графы K5 и K3,3 в некотором смысле исчерпывают все возможные непланарные графы. А именно, верна теорема Понтрягина – Куратовского: граф не является планарным тогда и только тогда, когда он содержит в качестве подграфа или K5, или K3,3, возможно, с дополнительными вершинами на рёбрах.

10.
Каждое ребро полного графа с 11 вершинами покрашено в один из двух цветов: красный или синий. Докажите, что либо „красный“, либо „синий“ граф не является плоским.
Определение. Степенью вершины графа называется количество входящих в неё рёбер.
11.
Докажите, что в плоском графе есть вершина, степень которой не превосходит 5.
12.
Докажите теорему о пяти красках: вершины любого плоского графа можно раскрасить в не более, чем 5 цветов так, что любые две соединённые ребром вершины будут разного цвета.
Верна более сильная теорема о четырёх красках. Её доказали К. Аппель и В. Хакен при помощи ЭВМ в 1976 году.