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

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

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

Занятие 4 (19 октября 2013 года). Формула Эйлера

Планарный граф (или плоский граф) — граф, который можно нарисовать на плоскости так, чтобы ребра не пересекались.

Формула Эйлера: для планарного связного графа В − Р + Г = 2 (В — число вершин, Р — число ребер, Г — число граней).

1.

Нарисуйте куб, тетраэдр, октаэдр как плоский граф на плоскости.

2.

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

3.

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

4.

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

5.

Пусть есть планарный граф в котором N компонент связности. Как изменится для него формула Эйлера?

6.

Докажите, что полный граф на пяти вершинах не планарен.

7.

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

8.

Футбольный мяч сшит из 32 лоскутков: белых шестиугольников и черных пятиугольников. Каждый черный лоскут граничит только с белыми, а каждый белый - с тремя черными и тремя белыми. Сколько лоскутков белого цвета?