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

Кружок для старшеклассников, не участвовавших ранее в математических кружках

Занятие 8 (7 ноября 2015 года). Домики и колодцы

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

1.

Обозначим через V число вершин графа, через E — число его ребер, а через F — число кусков, на которые граф разбивает плоскость. Докажите, что для связного планарного графа верна формула Эйлера: V − E + F = 2.

Подсказка

Подсказка. Попробуйте применить индукцию.

2.

В стране Озерная 7 озер, соединенных между собой 10 непересекающимися каналами, причем от любого озера можно доплыть до любого другого. Сколько в этой стране островов?

3.

В квадрате отметили 20 точек и соединили их непересекающимися отрезками друг с другом и с вершинами квадрата так, что квадрат разбился на треугольники. Сколько получилось треугольников?

4.

Докажите, что для планарного графа, в котором не менее двух рёбер, справедливо неравенство 2E ≥ 3F.

Подсказка

Подсказка. Какое наименьшее число рёбер может быть у грани?

5.

Пользуясь утверждением предыдущей задачи, покажите, что в плоском связном графе, в котором не менее двух рёбер, E ≤ 3V − 6.

6.

Можно ли построить три дома, вырыть три колодца и соединить тропинками каждый дом с каждым колодцем так, чтобы тропинки не пересекались?