Ответ: всего было сделано 10 рукопожатий.
Задача №3. Гарри Поттер умеет превращать жабу в принцессу, гриб в жабу и грушу, грушу в яблоко, огрызок от яблока в котёнка и ёжика, котёнка в грушу или яблоко, ёжика в грушу, а яблоко – только в огрызок. Сейчас у него есть яблоко. Сможет ли он превратить его в принцессу?
Решение. Поставив в соответствие каждому объекту точку и соединив точки, связанные отношением «превращение» линией, получим граф, в котором объекты «яблоко» и «принцесса» не связаны между собой.
Ответ: нет, нельзя.
Задача №4. В стране Цифра есть девять городов с названиями 1, 2, 3, 4, 5, 6, 7, 8, 9. Два города соединены авиалинией только в том случае, если двузначное число, составленное из цифр-названий этих городов, делиться на 3. Можно ли добраться из города 1 в город 9?
Решение. Построим граф: города изобразим вершинами графа, а авиалинии – ребрами. Вершины 3, 5, 9 связаны между собой, но не связаны с остальными. Значит, долететь из города 1 в город 9 нельзя.
Ответ: нет, нельзя.
Задача №5. На концерте каждую песню исполняли двое артистов, и никакая пара не выступала вместе более одного раза. Всего было 12 артистов, каждый выступил по 5 раз. Сколько было песен?
Решение. Рассмотрим граф, вершинами которого являются выступавшие артисты. Соединим пару артистов ребром, если они вместе пели. Получим граф с 12 вершинами степени 5, каждой песне соответствует ребро. Аналогично предыдущему примеру, в графе (12 · 5) : 2 = 30 рёбер, то есть было 30 песен.
Ответ: 30 песен.
Дата добавления: 2021-04-15; просмотров: 129; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!