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

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

1.

Обязательно ли является ли деревом граф из задачи 15.2, 15.7, 15.8, графы из задачи 15.4?

2.

Улитка хочет навестить свою бабушку, которая живёт на дереве высотой 10 метров. За день она поднимается на 4 метра, а за ночь сползает на 3. Когда она доползёт до цели, если начнёт своё путешествие утром в понедельник?

3.

Докажите, что в любом дереве существует хотя бы одна висячая вершина.

4.

Существует ли дерево, в котором все вершины имеют одинаковую степень? Сколько вершин может быть в таком дереве? Приведите все варианты.

5.

В старой усадьбе 6 беседок, которые соединяются тропинками. Известно, что если выйдешь из любой беседки, то вернуться в неё можно, только пройдя дважды хотя бы по одной тропинке. Сколько тропинок в усадьбе?

6.

Пусть в дереве В вершин. Сколько в этом дереве рёбер?

7.

В старой усадьбе дом обсажен по кругу высокими деревьями — елями, соснами и березами. Всего деревьев 96. Эти деревья обладают странным свойством: из двух деревьев, растущих через одно от любого хвойного — одно хвойное, а другое лиственное, и из двух деревьев, растущих через три от любого хвойного — тоже одно хвойное, а другое лиственное. Сколько берез посажено вокруг дома?

8.

В архипелаге 15 островов, каждый из которых соединён мостами не менее, чем с семью другими. Докажите, что с любого острова можно попасть на любой другой.