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

Кружок 8 класса

Занятие 8 (26 ноября 2016 года). Графы 3

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

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

Пусть у плоского связного графа число вершин равно В, число рёбер — Р; пусть число граней, на которые граф разбивает плоскость, равно Г. Тогда имеет место формула Эйлера: \[ \mbox{Э} = \mbox{В} - \mbox{Р} + \mbox{Г} = 2. \] Отсюда для плоских графов с \(\mbox{Г} \geqslant 2\), поскольку \(\mbox{P} \geqslant \frac{3}{2} \mbox{Г}\) (каждая грань ограничена как минимум треугольником), имеет место неравенство: \[ \mbox{Р} \leqslant 3 \mbox{В} - 6. \] Это неравенство неверно для графа \(K_5\) (рисунок 1). Значит, этот граф нельзя изобразить на плоскости без пересечений рёбер.

Рисунок 1	Рисунок 2	Рисунок 3

1.

Для графа \(K_{3,3}\) (рисунок 2) неравенство \(\mbox{Р} \leqslant 3 \mbox{В} - 6\) верно. Однако из этого не следует, что этот граф можно изобразить на плоскости без пересечений!

а)

Докажите, что если бы граф \(K_{3,3}\) был плоским, то для него было бы верно не только неравенство \(\mbox{Р} \geqslant \frac{3}{2} \mbox{Г}\), но и \(\mbox{Р} \geqslant 2 \mbox{Г}\). Какое свойство графа \(K_{3,3}\) при этом используется?

б)

Выведите из этого неравенства неравенство \(\mbox{Р} \leqslant 2\mbox{В} - 4\).

в)

Домики и колодцы. Есть три домика и три колодца. Докажите, что нельзя соединить каждый домик с каждым колодцем тропинками так, чтобы тропинки не пересекались. (Иначе говоря, граф \(K_{3,3}\) нельзя изобразить на плоскости без пересечений.)

2.

В Древляндии 101 город, и некоторые из них соединены дорогами (каждая дорога соединяет ровно два города, развилок и тупиков нет); при этом каждые два города соединяет ровно один путь. Сколько в этой стране дорог?

3.

а)

Отметьте на плоскости 8 точек и соедините их отрезками таким образом, чтобы из каждой точки выходили ровно 3 отрезка, чтобы отрезки не пересекались и чтобы из каждой точки, следуя по отрезкам, можно было бы добраться до любой другой.

б)

Отметьте на плоскости 12 точек и соедините их отрезками так, чтобы из каждой точки выходили ровно 5 отрезков и чтобы отрезки не пересекались.

4.

Можно ли, двигаясь по отрезкам на рисунке 3, обойти все кружочки и вернуться в исходную точку, побывав на каждом кружочке ровно один раз?

5.

Известно, что в стране ровно 40 дорог, каждая дорога соединяет ровно два города (тупиков и развилок нет), две разные дороги не могут соединять одну и ту же пару городов. Кроме того, известно, что нет города, в который не ведёт ни одной дороги.

а)

Какое наибольшее число городов может быть в этой стране?

б)

А какое наименьшее?

6.

а)

Докажите, что не существует многогранника, у которого было бы ровно семь рёбер.

б)

Для каждого \(n \geqslant 8\) приведите пример многогранника, у которого ровно \(n\) рёбер.

Дополнительные задачи

7.

В стране 15 городов, некоторые из них соединены авиалиниями, принадлежащими трём авиакомпаниям. Известно, что даже если любая из авиакомпаний прекратит полеты, можно будет добраться из каждого города в любой другой (возможно, с пересадками), пользуясь рейсами оставшихся двух компаний. Какое наименьшее количество авиалиний может быть в стране?

8.

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

9.

Семиугольник разбит на выпуклые пяти- и шестиугольники, причём так, что каждая его вершина является вершиной по крайней мере двух многоугольников разбиения. Докажите, что число пятиугольников разбиения не меньше 13.