💻 Информатика 9 класс · 20 вопросов · ~20 мин · ⏱ Таймер 20:00 · Средний · 👥 2 прошли

Графы и поиск маршрута

Граф превращает дороги, ссылки, знакомства и передачи сигнала в вершины и рёбра. Но рисунок помогает только тому, кто различает направление, вес, путь и цикл. В этом тесте нужно читать графы без картинок по спискам связей, работать с матрицами, считать длину маршрута и находить кратчайший путь, не попадаясь на ближайшее ребро, которое ведёт к плохому итогу.

Отвечено: 0 из 20

⏱ --:--

💡 Инструкция: Записывайте маршрут по вершинам и отдельно складывайте веса рёбер. В ориентированном графе каждый раз проверяйте направление стрелки: обратный переход может отсутствовать.

Вопрос 1 из 20

Что в графе обычно называют вершиной?

Числовая характеристика связи между объектами. Связь между двумя объектами графа. Объект, между которым и другими объектами задаются связи. Последовательность связанных объектов от начала до конца.

Вопрос 2 из 20

В неориентированном графе есть рёбра AB, AC, AD и BC. Какова степень вершины A?

4. 2. 1. 3.

Вопрос 3 из 20

Даны рёбра AB, BC и CD. Какая последовательность является путём из A в D?

A — B — C — D. A — D — C. B — D — A. A — C — B — D.

Вопрос 4 из 20

Что означает, что неориентированный граф связный?

Из любой вершины можно добраться до любой другой по рёбрам. Каждая вершина имеет прямое ребро со всеми остальными. В каждой вершине степень больше нуля, даже если граф распадается на части. Граф имеет одну компоненту, но отдельные вершины могут быть недостижимы.

Вопрос 5 из 20

В графе есть рёбра AB, BC, CA и CD. Какая последовательность образует цикл?

A — B — C — D. A — C — D — C. A — B — C — A. D — C — B.

Вопрос 6 из 20

Что означает дуга A → B?

Переход разрешён в обе стороны, потому что вершины соединены одной стрелкой. A считают вершиной назначения, а B — отправления, поэтому запись читают справа налево. Переход разрешён из A в B; для пути назад нужна отдельная дуга. Дуга показывает равенство весов A и B, но не задаёт направление перехода.

Вопрос 7 из 20

Даны дуги A → B, B → C и C → A. Какой путь ведёт из B в A?

B → A. B → C → A. B → C → B. A → C → B.

Вопрос 8 из 20

В вершину C входят дуги A → C и B → C, а выходит C → D. Какова входящая степень C?

0. 1. 2. 3.

Вопрос 9 из 20

На сайте страницы связаны так: Главная → Новости, Новости → Архив. Какой вывод точен?

Из Архива можно вернуться на Главную по тем же ссылкам в обратном порядке. Из Главной можно попасть в Архив через Новости; обратный путь не задан. Из Новости можно перейти в Главную, а из Главной — сразу в Архив. Главная и Архив связаны прямой ссылкой, поскольку между ними есть путь.

Вопрос 10 из 20

Когда ориентированный граф называют сильно связным?

Из каждой вершины по направлениям можно добраться до любой другой. Если не учитывать направления, граф остаётся связным. Для каждой пары вершин достаточно пути хотя бы в одном из двух направлений. Из каждой вершины выходит хотя бы одна дуга.

Вопрос 11 из 20

В принятой в задаче весовой матрице строка задаёт начало, а столбец — конец перехода. Что означает число 7 в строке B и столбце D?

В графе всего семь вершин. Вес ребра или дуги из B в D равен 7. Степень вершины B равна 7. Из D в B существует семь разных путей.

Вопрос 12 из 20

Какое свойство имеет весовая матрица неориентированного графа с одинаковым весом в обе стороны?

Она симметрична относительно главной диагонали. Симметрия зависит от равенства весов разных рёбер, а не от направления. Она симметрична, если степени соединённых вершин совпадают. В каждой паре зеркальных ячеек стоит сумма весов двух направлений.

Вопрос 13 из 20

В принятой в задаче весовой матрице строка задаёт начало перехода. В строке D и столбце B стоит 7. Что можно утверждать?

Вершина B имеет номер 7. Путь D → B состоит из семи рёбер. У вершины D семь соседей. Связь из D в B имеет вес 7.

Вопрос 14 из 20

Почему на главной диагонали простой матрицы смежности обычно стоят нули?

В графе отсутствуют любые рёбра. Ноль показывает, что вершина не имеет исходящих рёбер к другим вершинам. Петли из вершины в неё же не заданы. Нули обозначают самые тяжёлые рёбра.

Вопрос 15 из 20

Веса: A–B = 4, B–C = 6, прямого ребра A–C нет. Каков вес пути A–B–C?

24. 10. 6. 4.

Вопрос 16 из 20

Есть маршруты A–B–D весом 4 + 3 и A–C–D весом 2 + 8. Какой короче?

A–C–D, потому что первое ребро легче. Оба маршрута имеют вес 10. Нельзя сравнить маршруты с двумя рёбрами. A–B–D, его вес равен 7.

Вопрос 17 из 20

Веса: A–B = 2, A–C = 5, B–D = 6, C–D = 1. Какой путь из A в D кратчайший?

A–C–D с весом 6. A–B–A–C–D с весом 10. A–B–D с весом 8. Оба пути имеют вес 7.

Вопрос 18 из 20

Почему правило «всегда идти по самому лёгкому следующему ребру» может дать неверный кратчайший путь?

Вес пути определяется числом рёбер, а не суммой их весов. При положительных весах минимальное следующее ребро сохраняет оптимальность всего пути. После первого шага можно сравнивать число рёбер до цели вместо их суммарного веса. Лёгкий первый шаг может привести к дорогому продолжению.

Вопрос 19 из 20

В ориентированном графе A → B = 1, B → C = 1, C → D = 2, A → D = 7. Каков кратчайший путь A → D?

D → C → B → A с весом 4. A → B → A → D с весом 9. A → B → C → D с весом 4. A → D с весом 7.

Вопрос 20 из 20

Путь A–B–D имел вес 3 + 4, а A–C–D — 5 + 3. Вес B–D увеличили до 7. Что стало кратчайшим?

A–B–D с прежним весом 7. Ответ не меняется при изменении одного ребра. Оба пути с весом 10. A–C–D с весом 8.

Ответьте на все 20 вопросов, чтобы получить результат

🔗 Встроить тест на свой сайт (iframe) ▼

Скопируйте код и вставьте в любое место на вашем сайте:

Также доступна прямая ссылка на embed-страницу