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

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

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

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

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

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

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

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

3.: Сколько рёбер в графе K_n?

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

4.: Планарен ли граф K₄?

Обозначения. Пусть дан граф на плоскости. Тогда В — число вершин, Р — число рёбер, а Г — число граней, т.е. частей, на которые рёбра графа разбивают плоскость.

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

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

10.: Каждое ребро полного графа с 11 вершинами покрашено в один из двух цветов: красный или синий. Докажите, что либо „красный“, либо „синий“ граф не является плоским.

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

11.: Докажите, что в плоском графе есть вершина, степень которой не превосходит 5.
12.: Докажите теорему о пяти красках: вершины любого плоского графа можно раскрасить в не более, чем 5 цветов так, что любые две соединённые ребром вершины будут разного цвета.

Верна более сильная теорема о четырёх красках. Её доказали К. Аппель и В. Хакен при помощи ЭВМ в 1976 году.

Вы видите ошибку? Выделите её и нажмите Ctrl+Enter!