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

Руководитель Елена Анатольевна Чернышева
2005/2006 учебный год

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


Граф, который можно нарисовать так, чтобы его рёбра не пересекались (нигде, кроме вершин) называется плоским. Будем говорить, что плоский граф правильно нарисован, если его рёбра на рисунке не пересекаются. Заметим, что плоский правильно нарисованный граф разбивает плоскость на несколько частей.
1.
Являются ли плоскими графы, изображённые на рисунке?
граф1граф2

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

Для плоского правильно нарисованного графа введём обозначения: В — количество вершин в нём, Р — количество рёбер, Г — количество частей, на которые он разбивает плоскость (количество граней).
3.
Докажите, что В — Р + Г = 2 для произвольного дерева.
4.
Докажите, что в любом связном графе можно удалить некоторое количество рёбер так, что он станет деревом.
5.
Докажите, что В — Р + Г = 2 для плоского правильного нарисованного графа. (Формула Эйлера.)
6.
В стране Озёрная 7 озёр, соединённых между собой 10 каналами, причём от любого озера можно доплыть до любого другого. Сколько в этой стране островов?
7.
Задача про футбольный мяч. В многограннике чёрные грани — правильные пятиугольники, а белые — правильные шестиугольники. В каждой вершине сходится по три грани. Сколько в этом многограннике чёрных граней?
8.
В квадрате отметили 20 точек и соединили их непересекающимися отрезками друг с другом и вершинами квадрата так, что квадрат разбился на треугольники. Сколько получилось треугольников?
9.
Каждое ребро полного графа с 11 вершинами покрашено в один из двух цветов: красный или синий. Докажите, что либо «красный», либо «синий» граф (либо и тот, и другой) не является плоским.