Графы

1 ВОПРОС · 1 БАЛЛ

1. Чтение направленного ребра

Выберите верное утверждение о записи A → B в ориентированном графе.

• Из A можно перейти в B, а обратный переход по этому ребру не предполагается.
• Из B можно перейти в A, а из A в B перейти нельзя.
• Из A в B можно перейти только после возврата в A по другому ребру.
• Стрелка означает, что вершины A и B не соединены.

1 ПУТЬ · 1 БАЛЛ

2. Сложение весов рёбер

Найдите длину пути A → B → C. Вес ребра A → B равен 4, а вес ребра B → C равен 7.

3 ПРОПУСКА · 1 БАЛЛ

3. Обозначения весовой матрицы

Заполните пропуски, используя обозначения весовой матрицы ориентированного графа.

В клетке матрицы $a_{ij}$ записывают вес ребра из вершины в вершину . Если такого ребра нет, записывают .

2 ПУТИ · 2 БАЛЛА

4. Сравнение длин маршрутов

Вычислите длины двух направленных путей и сравните их. Путь P: A → B → D имеет веса 6 и 5. Путь Q: A → C → D имеет веса 4 и 9.

4 УТВЕРЖДЕНИЯ · 2 БАЛЛА

5. Свойства графа и пути

Определите истинность каждого утверждения, опираясь только на определения ориентированного графа, веса ребра и длины пути.

1. Длина пути равна сумме весов входящих в него рёбер.ИстинаЛожь
2. Если существует ребро A → B, то в графе обязательно существует ребро B → A.ИстинаЛожь
3. В весовой матрице строка обычно соответствует вершине, из которой выходит ребро.ИстинаЛожь
4. В ациклическом графе обязательно есть путь между любыми двумя вершинами.ИстинаЛожь

4 ПАРЫ · 2 БАЛЛА

6. Связь вершины с числом путей

Соедините обозначение с его смыслом при подсчёте количества путей в направленном ациклическом графе.

5 ШАГОВ · 3 БАЛЛА

7. Алгоритм подсчёта маршрутов

Восстановите порядок действий для подсчёта количества путей из S в T в направленном ациклическом графе.

1. Положить N(S) = 1.
2. Рассматривать вершины в порядке от начальной к конечной, не возвращаясь по циклам.
3. Для каждой следующей вершины сложить значения числа путей по всем входящим рёбрам.
4. Записать ответ как значение N(T).
5. Если у вершины нет входящего пути из S, принять её значение равным 0.

4 ВАРИАНТА · 4 БАЛЛА

8. Поиск лишнего маршрута

В ориентированном графе заданы рёбра S → A, S → B, A → C, B → C, C → T. Найдите запись, которая не является направленным путём из S в T.

1. S → A → C → T
2. S → B → C → T
3. S → A → B → C → T
4. S → B → C → T

3 ВЕРШИНЫ · 5 БАЛЛОВ

9. Подсчёт маршрутов в ациклическом графе

В направленном ациклическом графе заданы рёбра S → A, S → B, A → C, B → C, A → T, C → T. Сколько различных направленных путей ведёт из S в T? Используйте значения N(V): для начальной вершины положите N(S) = 1.

6 ПАР · 5 БАЛЛОВ

10. Расчёты по весовой матрице и направленному графу

Сопоставь каждый граф или фрагмент весовой матрицы с результатом вычисления. Для путей учитывай направление рёбер; если указано «кратчайший путь», выбери его минимальную длину.