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

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

Руководители Дмитрий Александрович Коробицын и Дмитрий Викторович Шелаев
2013/2014 учебный год

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

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

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

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

1.
Нарисуйте куб, тетраэдр, октаэдр как плоский граф на плоскости.
2.
В стране Озерная 7 озер, соединенных между собой 10 непересекающимися каналами, причем от любого озера можно доплыть до любого другого. Островом считается часть суши, окруженная водой. Сколько в этой стране островов?
3.
Внутри квадрата отметили 20 точек и соединили их непересекающимися отрезками друг с другом и вершинами квадрата, так что квадрат разбился на треугольники. Сколько получилось треугольников?
4.
Можно ли построить три дома, вырыть три колодца и соединить тропинками каждый дом с каждым колодцем так, чтобы тропинки не пересекались?
5.
Пусть есть планарный граф в котором N компонент связности. Как изменится для него формула Эйлера?
6.
Докажите, что полный граф на пяти вершинах не планарен.
7.
Докажите, что любой многогранник можно представить в виде плоского графа.
8.
Футбольный мяч сшит из 32 лоскутков: белых шестиугольников и чёрных пятиугольников. Каждый чёрный лоскут граничит только с белыми, а каждый белый — с тремя чёрными и тремя белыми. Сколько лоскутков белого цвета?

Вы видите ошибку? Выделите её и нажмите Ctrl+Enter! Rambler's Top100
liveinternet.ru
Apache
PHP
HTML 4.01
CSS