|
Кружок 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 девушек. а) Докажите, что
пересечение критических множеств — критическое. б) Докажите, что в
этих условиях компанию можно переженить по знакомствам.
|