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

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

Руководитель Варвара Алексеевна Косоротова
2010/2011 учебный год

Занятие 23. Графы

Граф — это набор точек (вершин), некоторые из которых соединены линиями (ребрами).
Граф называется связным, если от каждой его вершины можно «дойти» до любой другой по ребрам.
Цикл — замкнутый путь, образованный некоторыми ребрами графа.
Дерево — это связный граф без циклов.
1.
Доказать, что в любом дереве число вершин на единицу больше числа ребер.
Обозначим через B число вершин, а через P — число ребер графа.
2.
Воспользовавшись предыдущей задачей, докажите, что для любого связного графа справедливо неравенство P + 1 ≥ B.
Граф называется планарным, если его можно изобразить на плоскости так, чтобы его ребра не имели общих точек, кроме вершин.
На рисунке изображены два непланарных графа:

Непланарные графы

Грань планарного графа — многоугольник, образованный ребрами графа, диагонали которого не являются ребрами графа (то есть циклы, не распадающиеся на более короткие циклы). Особый случай — внешняя грань графа: это часть плоскости, являющаяся дополнением к объединению всех вершин, ребер и обычных граней графа.
Обозначим через Г общее количество граней в графе (считая и внешнюю грань).
3.
Докажите формулу Эйлера: для любого связного планарного графа выполняется равенство В - Р + Г = 2.
4.
a)
Есть два дома и два колодца. Можно ли их соедининть тропинками так, чтобы любой дом был связан тропинкой с любым колодцем напрямую?
b)
А если домов три?
c)
А если есть три дома и три колодца?
5.
На материке есть пять стран. Каждая страна такова, что из любой ее точки можно добраться до столицы, не пересекая при этом государственную границу. Докажите, что какие-то две страны не граничат друг с другом.
6.
Придумайте свои примеры непланарных графов (кроме тех, что на рисунке).
7.
В стране Озерная семь озер, соединенных между собой десятью каналами. От каждого озера можно доплыть по каналам и озерам до любого другого озера. Каналы не пересекаются. Сколько в этой стране островов?
8.
Докажите, что для любого планарного графа справедливо неравенство 2P ≥ 3Г - 3.
9.
Восьмиклассник отметил на плоскости несколько точек, а затем соединил некоторые из них непересекающимися отрезками. Докажите, что найдется точка, принадлежащая не более чем пяти отрезкам.