Задачи
1. Между 9 планетами Солнечной системы введено космическое сообщение. Ракеты летают по следующим маршрутам: Земля – Меркурий, Плутон – Венера, Земля – Плутон, Плутон – Меркурий, Меркурий – Венера, Уран – Нептун, Нептун – Сатурн, Сатурн – Юпитер, Юпитер – Марс и Марс – Уран. Можно ли добраться с Земли до Марса? В ответе запишите 1, если это возможно, или 0, если невозможно.
Решение.
Нарисуем схему: планетами будут соответствовать точки, а соединяющим их маршрутам — непересекающиеся между собой линии (см. рис.). Теперь видно, что долететь от Земли до Марса нельзя.
Ответ: 0.
2.В городе Маленьком 15 телефонов. Можно ли их соединить проводами так, чтобы каждый телефон был соединен ровно с пятью другими?
Решение. Предположим, что это возможно. Рассмотрим тогда граф, вершины которого соответствуют телефонам, а ребра — соединяющим их проводам.
В этом графе 15 вершин, степень каждой из которых равна пяти. Подсчитаем количество ребер в этом графе.
Для этого сначала просуммируем степени всех его вершин.
Ясно, что при таком подсчете каждое ребро учтено дважды (оно ведь соединяет две вершины).
Поэтому число ребер графа должно быть равно
Но это число нецелое!
Следовательно, такого графа не существует, а значит, и соединить телефоны требуемым образом невозможно.
Ответ: нельзя
3.В стране Семерка 15 городов, каждый из которых соединен дорогами не менее, чем с семью другими. Верно ли, что из любого города можно ли добраться до любого другого, возможно, проезжая через другие города?
Решение.
Предположим, что есть два города, между которыми нет пути.
Каждый из этих двух городов по условию соединен не менее, чем с семью другими городами, при этом все эти города различны — ведь если какие-то два из них совпадают, то существует путь, соединяющий исходные города (см. рис.).
Но тогда в стране семерка не менее 16 городов, что противоречит условию. Следовательно, наше предположение неверно, и любые два города связывает какой-то путь.
Ответ: нет
4.В Тридевятом царстве лишь один вид транспорта — ковер-самолет. Из столицы выходит 21 ковролиния, из города Дальний — одна, а из всех остальных городов — по 20. Можно ли из столицы долететь в Дальний (возможно, с пересадками). В ответе запишите 1, если это возможно, или 0, если невозможно.
Решение.
Предположим, из столицы невозможно добраться до города Дальний. Рассмотрим граф, вершинами которого являются все города, кроме города Дальний, а ребрами — ковролинии, соединяющие эти города между собой. В этом графе из одной вершины (столицы) выходит 21 ребро, а из всех остальных вершин — по 20 ребер. Таким образом, в этом графе ровно одна нечетная вершина. Но это невозможно, ведь в любом графе сумма степеней всех вершин равна удвоенному числу ребер, поэтому сумма степеней всех вершин четна.
Ответ: 1.
P.S.:Вы можете связаться со мной, если хотите понять математику, улучшить свои навыки или подготовиться к экзаменам.
Телеграмм: Волоснова Дарья !
!Ссылка на следующий урок ↩️