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

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

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

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

Занятие 16. Деревья(11.03.2006)


Циклом называется замкнутый путь.
Деревом называется связный граф без циклов.
1.
Обязательно ли является ли деревом граф из задачи 15.2, 15.7, 15.8, графы из задачи 15.4?
2.
Улитка хочет навестить свою бабушку, которая живёт на дереве высотой 10 метров. За день она поднимается на 4 метра, а за ночь сползает на 3. Когда она доползёт до цели, если начнёт своё путешествие утром в понедельник?
Ответ. Улитка доползет до цели в воскресенье вечером.
Решение. Заметим, что утром во вторник улитка окажется на высоте 1 метр, утром в среду — на высоте 2 метра, и так далее; утром в воскресенье улитка окажется на высоте 6 метров. До вершины дерева в этот момент останется 4 метра, а значит, в воскресенье вечером улитка достигнет своей цели.
Вершина, из которой выходит одно ребро, называется висячей.
3.
Докажите, что в любом дереве существует хотя бы одна висячая вершина.
4.
Существует ли дерево, в котором все вершины имеют одинаковую степень? Сколько вершин может быть в таком дереве? Приведите все варианты.
5.
В старой усадьбе 6 беседок, которые соединяются тропинками. Известно, что если выйдешь из любой беседки, то вернуться в неё можно, только пройдя дважды хотя бы по одной тропинке. Сколько тропинок в усадьбе?
6.
Пусть в дереве В вершин. Сколько в этом дереве рёбер?
7.
В старой усадьбе дом обсажен по кругу высокими деревьями — елями, соснами и березами. Всего деревьев 96. Эти деревья обладают странным свойством: из двух деревьев, растущих через одно от любого хвойного — одно хвойное, а другое лиственное, и из двух деревьев, растущих через три от любого хвойного — тоже одно хвойное, а другое лиственное. Сколько берез посажено вокруг дома?
Ответ. 32 берёзы.
8.
В архипелаге 15 островов, каждый из которых соединён мостами не менее, чем с семью другими. Докажите, что с любого острова можно попасть на любой другой.


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