Графы: дороги и пути — тренажёр
Тренировка по теме «Графы: дороги и пути»: задачи с меняющимися числами, мгновенная проверка, подсказка и подробный разбор к каждой. Ниже — шпаргалка по теме, разобранные примеры и ответы на частые вопросы.
Тренировка
0/81 Из города П выходят 7 двусторонних дорог. Сколько чисел стоит в строке П таблицы дорог?
Выбери ответ и нажми «Проверить». Подсказка рядом — пользоваться не стыдно.
Разбор примеров из тренажёра
17 задач из пула этого тренажёра с полной логикой решения: условие, подсказка, как решать и ответ. В самом тренажёре числа в каждой задаче обновляются от раунда к раунду — принцип решения остаётся тем же.
Пример 1. Из города П выходят 5 двусторонних дорог. Сколько чисел стоит в строке П таблицы дорог?
Подсказка. Считай числа в строке, не трогая пустую диагональ.
Как решать. Каждая дорога города П появляется в его строке ровно один раз: 5 дорог — 5 чисел.
Ответ: 5
Пример 2. Между каждой парой из 4 городов проложена дорога. Сколько всего дорог?
Подсказка. Каждый город даёт 4 − 1 дорогу, но каждую дорогу ты посчитаешь дважды.
Как решать. Каждый из 4 городов соединён с 4 − 1 остальными; посчитанное дважды число делим на 2: 4 · (4 − 1) : 2.
Ответ: 6
Пример 3. Прямая дорога из A в C имеет длину 12, а путь через B складывается из дорог A-B = 3 и B-C = 3. Какова длина кратчайшего пути из A в C?
Подсказка. Сравни два маршрута: прямой и через B.
Как решать. Маршрута два: прямой длиной 12 и через B длиной 3 + 3. Через B короче — это и есть ответ.
Ответ: 6
Пример 4. В графе 7 дорог. Чему равна сумма степеней всех вершин?
Подсказка. Каждая дорога касается двух городов.
Как решать. Каждая из 7 дорог добавляет по единице степеням двух городов, поэтому сумма степеней равна удвоенному числу дорог.
Ответ: 14
Пример 5. Из города П выходят 2 двусторонних дорог. Сколько чисел стоит в строке П таблицы дорог?
Подсказка. Считай числа в строке, не трогая пустую диагональ.
Как решать. Каждая дорога города П появляется в его строке ровно один раз: 2 дорог — 2 чисел.
Ответ: 2
Пример 6. Между каждой парой из 7 городов проложена дорога. Сколько всего дорог?
Подсказка. Каждый город даёт 7 − 1 дорогу, но каждую дорогу ты посчитаешь дважды.
Как решать. Каждый из 7 городов соединён с 7 − 1 остальными; посчитанное дважды число делим на 2: 7 · (7 − 1) : 2.
Ответ: 21
Пример 7. Прямая дорога из A в C имеет длину 13, а путь через B складывается из дорог A-B = 2 и B-C = 2. Какова длина кратчайшего пути из A в C?
Подсказка. Сравни два маршрута: прямой и через B.
Как решать. Маршрута два: прямой длиной 13 и через B длиной 2 + 2. Через B короче — это и есть ответ.
Ответ: 4
Пример 8. В графе 6 дорог. Чему равна сумма степеней всех вершин?
Подсказка. Каждая дорога касается двух городов.
Как решать. Каждая из 6 дорог добавляет по единице степеням двух городов, поэтому сумма степеней равна удвоенному числу дорог.
Ответ: 12
Пример 9. Из города П выходят 4 двусторонних дорог. Сколько чисел стоит в строке П таблицы дорог?
Подсказка. Считай числа в строке, не трогая пустую диагональ.
Как решать. Каждая дорога города П появляется в его строке ровно один раз: 4 дорог — 4 чисел.
Ответ: 4
Пример 10. Между каждой парой из 6 городов проложена дорога. Сколько всего дорог?
Подсказка. Каждый город даёт 6 − 1 дорогу, но каждую дорогу ты посчитаешь дважды.
Как решать. Каждый из 6 городов соединён с 6 − 1 остальными; посчитанное дважды число делим на 2: 6 · (6 − 1) : 2.
Ответ: 15
Пример 11. Прямая дорога из A в C имеет длину 9, а путь через B складывается из дорог A-B = 3 и B-C = 3. Какова длина кратчайшего пути из A в C?
Подсказка. Сравни два маршрута: прямой и через B.
Как решать. Маршрута два: прямой длиной 9 и через B длиной 3 + 3. Через B короче — это и есть ответ.
Ответ: 6
Пример 12. В графе 5 дорог. Чему равна сумма степеней всех вершин?
Подсказка. Каждая дорога касается двух городов.
Как решать. Каждая из 5 дорог добавляет по единице степеням двух городов, поэтому сумма степеней равна удвоенному числу дорог.
Ответ: 10
Пример 13. Из города П выходят 6 двусторонних дорог. Сколько чисел стоит в строке П таблицы дорог?
Подсказка. Считай числа в строке, не трогая пустую диагональ.
Как решать. Каждая дорога города П появляется в его строке ровно один раз: 6 дорог — 6 чисел.
Ответ: 6
Пример 14. Между каждой парой из 8 городов проложена дорога. Сколько всего дорог?
Подсказка. Каждый город даёт 8 − 1 дорогу, но каждую дорогу ты посчитаешь дважды.
Как решать. Каждый из 8 городов соединён с 8 − 1 остальными; посчитанное дважды число делим на 2: 8 · (8 − 1) : 2.
Ответ: 28
Пример 15. Прямая дорога из A в C имеет длину 11, а путь через B складывается из дорог A-B = 4 и B-C = 4. Какова длина кратчайшего пути из A в C?
Подсказка. Сравни два маршрута: прямой и через B.
Как решать. Маршрута два: прямой длиной 11 и через B длиной 4 + 4. Через B короче — это и есть ответ.
Ответ: 8
Пример 16. В графе 3 дорог. Чему равна сумма степеней всех вершин?
Подсказка. Каждая дорога касается двух городов.
Как решать. Каждая из 3 дорог добавляет по единице степеням двух городов, поэтому сумма степеней равна удвоенному числу дорог.
Ответ: 6
Пример 17. Прямая дорога из A в C имеет длину 15, а путь через B складывается из дорог A-B = 2 и B-C = 4. Какова длина кратчайшего пути из A в C?
Подсказка. Сравни два маршрута: прямой и через B.
Как решать. Маршрута два: прямой длиной 15 и через B длиной 2 + 4. Через B короче — это и есть ответ.
Ответ: 6
Вопросы для повторения темы
Контрольные вопросы по «Графы: дороги и пути» с верными ответами и пояснениями — проверь себя до запуска тренажёра.
Вопрос 1. Дороги: A-B, A-C, B-D, C-D, D-E. Из какого города выходит больше всего дорог?
Ответ: D
Пояснение. У A две дороги, у B и C по две, а у D три: B-D, C-D и D-E. Степень D равна 3 — это максимум.
Вопрос 2. Дороги: A-B = 3, B-C = 1, C-D = 3, A-C = 5, B-D = 6. Какова длина кратчайшего пути из A в D?
Ответ: 7
Пояснение. Маршруты: A-B-D = 9, A-C-D = 8, A-B-C-D = 3 + 1 + 3 = 7, A-C-B-D = 12. Кратчайший — 7.
Вопрос 3. В таблице двусторонних дорог заполненные клетки симметричны зеркально относительно диагонали.
Ответ: Верно
Пояснение. Верно: дорога A-B длиной 3 стоит и в строке A, и в строке B — таблица симметрична, ведь дороги двусторонние.
Вопрос 4. Что верно про пути и графы?
Ответ: Длина пути — сумма длин дорог по маршруту; Цикл начинается и заканчивается в одной вершине; В связном графе из любого города можно доехать до любого
Пояснение. Длина пути — сумма весов, цикл замкнут, связный граф соединяет все вершины. А школьный путь вершины не повторяет.
Вопрос 5. Расставь шаги решения задания 1 в правильном порядке.
Ответ: Посчитать степень каждого города по таблице → Соотнести города со схемой по числам дорог → Перебрать все маршруты между нужными городами → Сложить длины дорог по каждому маршруту
Пояснение. Порядок такой: степени по таблице, соотнесение со схемой, перебор маршрутов, и лишь затем сложение весов.
Вопрос 6. Сопоставь понятие и его определение.
Пояснение. Вершины и рёбра — строительные блоки графа, степень считает рёбра вершины, цикл — замкнутый путь.
Вопрос 7. В таблице двусторонних дорог вне диагонали заполнено 10 клеток. Сколько дорог в графе?
Ответ: 5
Пояснение. Каждая дорога появляется в таблице дважды: в строке одного города и в строке другого. 10 : 2 = 5 дорог.
Настройте ритм перед экзаменом: задание дня по информатике — новое каждый день.