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

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

Занятие 7 (19 ноября 2016 года). Плоские графы

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

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

1.

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

2.

Пусть у плоского связного графа число вершин равно В, число рёбер — Р; пусть число граней, на которые граф разбивает плоскость, равно Г; пусть Э = В − Р + Г.

а)

Из графа убрали висячую вершину (т.е. вершину степени 1) и ведущее к ней ребро (рисунок 1). Как изменились значения В, Р, Г, Э?

б)

Из графа убрали ребро, разделяющее две грани (рисунок 2). Как изменились значения В, Р, Г, Э?

в)

Формула Эйлера. Чему может быть равно значение Э для плоского связного графа?

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

3.

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

4.

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

5.

а)

Пусть у плоского связного графа Г ≥ 2 и в этом графе нет петель и кратных рёбер. Докажите, что Р ≥ ³/₂ Г.

б)

В тех же условиях докажите, что Р ≤ 3В − 6.

в)

В графе K₅ пять вершин, и каждая вершина соединена с каждой (рисунок 3). Докажите, что K₅ — не плоский граф.

Рисунок 3. K₅

6.

а)

Постройте плоский граф (без петель и кратных рёбер), степени всех вершин которого в точности равны 5.

б)

Могут ли в плоском графе степени всех вершин быть больше 5?

в)

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

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

7.

Докажите, что граф, имеющий 10 вершин, степень каждой из которых равна 5, — не плоский.

8.

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

9.

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