Страница:
<< 2 3 4 5 6 7 8 >> [Всего задач: 36]
|
|
Сложность: 5 Классы: 9,10,11
|
В стране несколько городов, некоторые пары городов соединены дорогами, причём
между каждыми двумя городами существует единственный несамопересекающийся путь
по дорогам. Известно, что в стране ровно 100 городов, из которых выходит
по одной дороге. Докажите, что можно построить 50 новых дорог так, что после этого даже при закрытии любой дороги можно будет из каждого города попасть в любой другой.
|
|
Сложность: 3 Классы: 6,7,8
|
Доказать, что
а) из связного графа можно выкинуть несколько рёбер так, чтобы осталось дерево;
б) в дереве с n вершинами ровно n – 1 ребро;
в) в дереве не меньше двух висячих вершин;
г) в связном графа из n вершин не меньше n – 1 ребра;
д) если в связном графе n вершин и n – 1 ребро, то он – дерево.
В некотором королевстве было 32 рыцаря. Некоторые из них были вассалами
других (вассал может иметь только одного сюзерена, причём сюзерен всегда богаче
своего вассала). Рыцарь, имевший не менее четырёх вассалов, носил титул барона.
Какое наибольшее число баронов могло быть при этих условиях?
(В королевстве действовал закон: "вассал моего вассала – не мой вассал".)
[Формула Эйлера]
|
|
Сложность: 3+ Классы: 7,8,9
|
Пусть связный плоский граф с V вершинами и E рёбрами разрезает плоскость на F кусков. Докажите формулу Эйлера: V – E + F = 2.
У Царя Гвидона было 5 сыновей. Среди его потомков 100 имели каждый ровно по 3 сына, а остальные умерли бездетными.
Сколько потомков было у царя Гвидона?
Страница:
<< 2 3 4 5 6 7 8 >> [Всего задач: 36]