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

Кружок 9-10 класса

Руководители Иван Александрович Дорофеев и Степан Львович Кузнецов
2006/2007 учебный год

Листок 6. Графы 2

1.
Дан кусок проволоки длиной 120 см. Можно ли, не ломая проволоки, изготовить из него каркас куба с ребром 10 см?
2.
Можно ли, сделав несколько ходов конями из исходного положения (рис. 1), расположить их так, как показано на рис. 2? (Выходить за пределы поля 3×3 не разрешается.)

Определение. Граф называется связным, если для любых двух вершин существует путь, их соединяющий.

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

3.
Волейбольная сетка имеет вид прямоугольника размером 50×600 клеток. Какое наибольшее число верёвочек можно перерезать так, чтобы сетка не распалась на куски?
4.
(Формула Эйлера) Докажите, что В − Р + Г = 2.
5.
В квадрате отметили 20 точек и соединили их непересекающимися отрезками друг с другом и с вершинами квадрата так, что квадрат разбился на треугольники. Сколько получилось треугольников?
6.
Докажите, что а) для графа на плоскости 2Р ≥ 3Г, б) для связного графа на плоскости Р ≤ 3В − 6, в) последнее неравенство справедливо для произвольного графа на плоскости.
7.
Докажите, что граф, имеющий пять вершин, каждая из которых соединена ребром с любой другой (полный граф с пятью вершинами), не является плоским (т.е. его нельзя изобразить на плоскости так, чтобы рёбра не пересекались).
Определения. Граф на плоскости называется многоугольным, если каждая его грань есть многоугольник (возможно, с кривыми сторонами). Многоугольный граф называется правильным, если каждая его грань ограничена одним и тем же числом (обозначим его ρ*) рёбер и к каждой вершине сходится одно и то же число (обозначим это число ρ) рёбер.
8.
а)
Докажите, что для правильного графа В·(2ρ + 2ρ* − ρρ*) = 4ρ*.
б)
Перечислите все правильные графы.
в)
Существуют ли правильные многогранники, кроме тетраэдра, куба, октаэдра, додекаэдра и икосаэдра?
Определения. Паросочетанием называется такое подмножество M множества рёбер графа, что из любой вершины исходит не более одного ребра из M.
Вершинным покрытием называется такое подмножество C множества вершин графа, что хотя бы один из концов любого ребра лежит в C.
9.
Докажите, что число рёбер в любом паросочетании не превосходит числа вершин в любом вершинном покрытии.
10*.
(теорема Кёнига – Эгервари) Докажите, что в двудольном графе число рёбер в максимальном (по числу элементов) паросочетании в точности равно числу вершин в минимальном вершинном покрытии.
11.
Приведите пример графа (не двудольного), для которого утверждение теоремы Кёнига – Эгервари не имеет места (то есть число рёбер в любом паросочетании строго меньше числа вершин в любом вершинном покрытии).
12.
(лемма о девушках = лемма Холла) Есть n юношей и n девушек. Каждый юноша знаком с некоторыми девушками. Для любого 0 < k < n + 1 любые k юношей знают не менее k девушек. Назовём множество из k юношей критическим, если они знают ровно k девушек. а) Докажите, что пересечение критических множеств — критическое. б) Докажите, что в этих условиях компанию можно переженить по знакомствам.