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

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

Версия для печати

Занятие 17. Плоские графы (18.03.2006)

1.

Являются ли плоскими графы, изображенные на рисунке?

Ответ Решение

Ответ. Являются.

Решение. Эти графы можно перерисовать так, чтобы их ребра не пересекались.

2.

а) Нарисуйте правильно плоский граф, вершины которого соответствуют вершинам куба, а ребра — ребрам куба.
б) Нарисуйте плоский граф для октаэдра (многогранника, у которого 6 вершин, 8 граней и 12 ребер). Для любого ли правильного или полуправильного многогранника можно нарисовать плоский граф?

Решение

Решение. Плоский граф можно нарисовать для любого многогранника. Для этого нужно достаточно сильно «растянуть» ребра одной из его граней так, чтобы площадь этой грани стала больше, чем сумма площадей всех остальных. Затем нужно спроецировать в плоскость этой «большой» грани все вершины многогранника вместе с ребрами (кроме вершин самой этой грани, так как они и так в ней лежат), изменив при этом конфигурацию некоторых ребер, если это нужно.
Понятно, что приведенное доказательство не является строгим — мы просто хотели подсказать красивую идею, которая помогает понять, как это сделать. Строгое доказательство для произвольного многогранника требует еще некоторых не совсем простых рассуждений. Но нетрудно убедиться в том, что для правильного или полуправильного многогранника утверждение задачи верно.

3.

Докажите, что В — Р + Г = 2 для произвольного дерева.

Решение

Решение. Как известно, в дереве количество вершин на единицу больше количества ребер, то есть, В — Р = 1. Кроме того, так как в дереве нет циклов, то количество частей (граней), на которые оно разбивает плоскость, равно единице: эта грань вся плоскость. То есть Г = 1. Тогда получается, что для любого дерева выполняется соотношение В — Р + Г = 1 + 1 = 2, что и требовалось доказать.

4.

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

Решение

Решение. Если связный граф не является деревом, то это означает, что в нем есть циклы (дерево по определению — это связный граф без циклов). Возьмем любой из циклов и удалим в нем произвольное ребро. Понятно, что граф останется связным. Если после удаления одного ребра циклов не осталось, то исходный граф стал деревом — мы получили то, что нужно. Если циклы остались, то опять берем любой из них и удаляем в нем произвольное ребро. В графе конечное число циклов (так как ребер конечное число), поэтому рано или поздно с помощью проведения указанной операции мы добьемся того, что циклов не останется и граф превратится в дерево.

5.

Докажите, что В — Р + Г = 2 для плоского правильного нарисованного графа. (Формула Эйлера.)

Решение

Решение. Если граф является деревом, то утверждение для него уже доказано в задаче ?3.
Если же граф имеет циклы, то повторим рассуждение из решения задачи ?3: будем удалять в этом графе по одному ребру до тех пор, пока все циклы не исчезнут. При удалении очередного ребра разрушается один цикл, поэтому количество граней уменьшается на 1. Количество вершин не изменяется, количество ребер тоже уменьшается на 1. Получается, что при удалении каждого ребра значение выражения В — Р + Г не изменяется, так как и Р, и Г уменьшаются на 1, но перед Р стоит знак «минус», а перед Г — «плюс». Когда в графе не останется циклов (то есть он станет деревом), то, как мы доказали ранее, значение выражения В — Р + Г будет равно 2, а так как при выполнении указанных операций оно не менялось, то и изначально оно было равно 2.

6.

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

Ответ Решение

Ответ. 4 острова.

Решение. Рассмотрим граф, в котором вершины соответствуют островам, а ребра — каналам. Понятно, что полученный граф будет плоским и связным, значит, для него выполняется формула Эйлера: В — Р + Г = 2. Для нашего графа В = 7, Р = 10. Подставляя в формулу, получаем 7 — 10 + Г = 2. Отсюда следует, что Г = 5, то есть, ребра графа разбивают плоскость на 5 частей. Островам соответствуют все грани, кроме внешней (она бесконечно большая во все стороны и острову соответствовать не может), значит, их 4.

7.

Задача про футбольный мяч. В многограннике черные грани — правильные пятиугольники, а белые — правильные шестиугольники. В каждой вершине сходится по три грани. Сколько в этом многограннике черных граней?

Ответ Решение

Ответ. 12 черных граней.

Решение. Так как любому многограннику соответствует плоский связный граф (см. решение задачи ?2), то для многогранников также верна формула Эйлера: В — Р + Г = 2.
Будем считать, что поверхность данного многогранника состоит из П пятиугольников и Ш шестиугольников. То есть Г = П + Ш.
Подсчитаем для каждой грани, сколько вершин многогранника ей принадлежит, и сложим полученные числа. Каждому пятиугольнику принадлежит 5 вершин, а каждому шестиугольнику 6. Так как пятиугольников П, шестиугольников Ш, то в итоге после суммирования получится число 5П + 6Ш. При этом в полученной сумме каждая вершина посчитана по 3 раза, так как к каждой вершине прилегает 3 грани. Поэтому выполняется соотношение:

5П + 6Ш = 3В

или

В =	5П + 6Ш
	3

Теперь получим соотношение для ребер. У каждого пятиугольника 5 сторон, а у шестиугольника — шесть, поэтому если для каждой грани подсчитать количество прилегающих к ней ребер, а затем полученные числа сложить, то каждое ребро будет посчитано ровно два раза, так как любое из них прилегает ровно к двум сторонам. Тогда выполняется соотношение:

5П + 6Ш = 2Р

или

Р =	5П + 6Ш
	2

Подставим полученные выражения в формулу Эйлера.

5П + 6Ш	-	5П + 6Ш	+ (П + Ш) = 2
3		2

Откуда

10П + 12Ш - 15П - 18Ш + 6П + 6Ш = 12

П = 12

8.

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

Ответ Указание

Ответ. 42 треугольника.

Указание. Рассмотрите граф, в котором 24 вершины и все грани, кроме внешней, треугольные.

9.

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