Страница:
<< 1 2 3 4 5 6 7 >> [Всего задач: 67]
В стране Семёрка 15 городов, каждый из которых соединён дорогами не менее, чем с семью другими.
Докажите, что из каждого города можно добраться до любого другого (возможно, проезжая через другие города).
Решение
Рассмотрим два произвольных города и предположим, что они не соединены путем, то есть такой последовательностью дорог, в которой начало очередной дороги совпадает с концом предыдущей. Каждый из этих двух городов по условию соединен не менее, чем с семью другими; при этом все упомянутые города различны – ведь если какие-то два из них совпадают, то есть путь, соединяющий исходные города.
Таким образом, мы насчитали не менее 16 городов. Противоречие.
Докажите, что граф с n вершинами, степень каждой из которых не менее n–1/2, связен.
Решение
Рассмотрим две произвольных вершины и предположим, что они не соединены путем, то есть такой последовательностью ребер, в которой начало очередного ребра совпадает с концом предыдущего. Каждая из этих двух вершин по условию соединена не менее, чем с n–1/2 другими; при этом все упомянутые вершины различны – ведь если какие-то две из них совпадают, то есть путь, соединяющий исходные вершины.
Таким образом, в графе не менее n–1/2 + n–1/2 + 2 = n + 1 вершин. Противоречие.
В Тридевятом царстве лишь один вид транспорта – ковер-самолет. Из столицы выходит 21 ковролиния, из города Дальний – одна, а из всех остальных городов – по 20. Докажите, что из столицы можно долететь в Дальний (возможно, с пересадками).
Решение
Рассмотрим компоненту связности графа ковролиний, содержащую столицу. Предположим, что она не содержит город Дальний. Тогда в этой компоненте связности из одной вершины (столицы) выходит 21 ребро, а из всех остальных вершин – по 20 рёбер. Таким образом в этом подграфе ровно одна нечётная вершина. Противоречие с задачей 87972 б).
|
|
|
Сложность: 3
Классы: 6,7,8
|
В некоторой стране из столицы выходит 89 дорог, из города Дальний – одна дорога, из остальных 1988 городов – по 20 дорог.
Доказать, что из столицы можно проехать в Дальний.
Решение
См. задачу 30429.
|
|
|
Сложность: 3
Классы: 6,7,8
|
В графе 100 вершин, причём степень каждой из них не меньше 50. Доказать, что граф связен.
Решение
См. задачу 30428.
Страница:
<< 1 2 3 4 5 6 7 >> [Всего задач: 67]
Фильтр
