Страница:
<< 1 2 3
4 5 6 7 >> [Всего задач: 67]
Как соединить 50 городов наименьшим числом авиалиний так, чтобы из каждого
города можно было попасть в любой, сделав не более двух пересадок?
Решение
Выделим один город и соединим его авиалинией с каждым из остальных 49 городов. Для этого потребуется 49 авиалиний.
Меньшим числом авиалиний обойтись нельзя. Действительно, согласно задаче 31098 г) в связном графе с 50 вершинами не менее 49 рёбер.
В стране из каждого города выходит 100 дорог и от каждого города можно добраться до любого другого. Одну дорогу закрыли на ремонт.
Докажите, что и теперь от каждого города можно добраться до любого другого.
Решение
Если закрыта дорога AB, то нам достаточно доказать, что и после этого можно добраться из A в B. Если это не так, то в компоненте связности, содержащей A, все вершины, кроме A, – чётные. Но наличие ровно одной нечётной вершины противоречит задаче 87972 б).
|
|
|
Сложность: 3+
Классы: 6,7,8
|
Из полного 100-вершинного графа выкинули 98 рёбер. Доказать, что он остался связным.
Решение
Предположим, что полученный граф оказался несвязным, и в одной из компонент связности n вершин. Тогда было выкинуто по крайней мере
n(100 – n) рёбер, соединявших вершины этой компоненты с вершинами других компонент. Но n(100 – n) = 50² – (n – 50)² ≥ 50² – 49² = 1·99 > 98. Противоречие.
|
|
|
Сложность: 3+
Классы: 9,10,11
|
В стране n городов. Между каждыми двумя городами установлено воздушное сообщение одной из двух авиакомпаний. Докажите, из этих двух авиакомпаний хотя бы одна такова, что что из любого города можно попасть в любой другой рейсами только этой авиакомпании.
Решение
См. задачу 30814 а).
|
|
|
Сложность: 3+
Классы: 9,10,11
|
Какое наименьшее число соединений требуется для организации проводной сети связи из 10 узлов, чтобы при выходе из строя любых двух узлов связи сохранялась возможность передачи информации между любыми двумя оставшимися (хотя бы по цепочке через другие узлы)?
Решение
Оценка. Для того, чтобы сохранилась связь при выходе из строя любых двух узлов, необходимо, чтобы в каждый узел входило не менее трёх линий связи (если узел А соединён с двумя узлами В и С, то при выходе из строя узлов В и С узел А становится недоступным). Таким образом, всего линий связи должно быть не менее 10·3 : 2 = 15.
Пример: каркас пятиугольной призмы (10 вершин – узлы, а рёбра – линии связи). Если вышли из строя два узла на одном пятиугольнике – основании призмы, то связь сохранится через другой пятиугольник. Если вышли из строя по одному узлу на разных пятиугольниках, то связь тоже сохранится.
Страница:
<< 1 2 3
4 5 6 7 >> [Всего задач: 67]
Фильтр
