Лист заданий по школьным темам
Выберите тему, решите вопросы самостоятельно и сверьтесь с объяснением. Готовый лист можно распечатать.
Графы и маршруты
Информатика · Вопросов: 10
Имя: ____________________ Дата: __________
Корень DFS имеет трёх соседей в исходном графе, но только одного ребёнка в дереве обхода. Достаточно ли трёх соседей для признания точкой сочленения?
- Да, любые три ребра гарантируют разрыв
- Да, корень любого DFS всегда является точкой сочленения
- Нет, у корня нужен минимум два ребёнка дерева DFS
Есть дуги М→Н веса 7, Н→О веса −4 и М→О веса 8. Других дуг нет. Каково кратчайшее расстояние М→О?
- 8
- Пути нет из-за отрицательной дуги
- 3
Из S в T есть только пути весов−3 и−8. Пустой путь к T не разрешён. Каков максимальный вес?
- 0
- −8
- −3
Увеличивающий путь содержит три невыбранных ребра и два выбранных. Как изменится число пар после переключения?
- Увеличится на 3
- Не изменится, потому что рёбра только переставляются
- Увеличится на 1
В ориентированном DFS ребро ведёт к активному предку текущей ветви. Что это показывает?
- Отсутствие всех циклов
- Наличие направленного цикла
- Обязательную несвязность графа
Какие ёмкости суммируются в сертификате разреза?
- Потоки всех дуг без учёта направления
- Исходные ёмкости дуг из достижимой стороны наружу
- Остаточные ёмкости всех дуг сети
Полный лапласиан треугольника имеет нулевой определитель. Сколько у него остовных деревьев?
- Ноль
- Три
- Определить нельзя
В графе А→Б, Б→В, В→А нет других вершин. Что покажет очередь вершин с нулевой входящей степенью?
- Обязательно начнёт с А, потому что это первая буква
- Сразу будет пустой: допустимого топологического порядка нет
- Выдаст любой алфавитный порядок как правильный
Было шесть отдельных объектов. Объединили 1 с 2, затем 2 с 3, затем снова 1 с 3. Сколько компонент осталось?
- Три
- Четыре
- Пять
Есть рёбра A→B,B→A,B→C,а из C нет выходов. Какие компоненты получаются?
- {A,B}и{C}
- {A,B,C}
- {A}и{B,C}
Ответы и пояснения
- Нет, у корня нужен минимум два ребёнка дерева DFS
Степень в исходном графе не подменяет число независимых поддеревьев DFS. При одном ребёнке удаление корня не разделяет это дерево на несколько таких частей.
- 3
Маршрут М→Н→О весит 7−4=3 и короче прямой дуги. Циклов в этом графе нет, поэтому отрицательный вес не мешает конечному ответу.
- −3
Наибольший из двух допустимых весов равен−3. Ноль не является вариантом, поскольку речь о пути из S в другую вершину T.
- Увеличится на 1
Добавляются три ранее невыбранных ребра и удаляются два выбранных. Разность равна 1; свободные концы обеспечивают допустимость нового паросочетания.
- Наличие направленного цикла
Путь по предкам от этой вершины до текущей уже существует, а найденное ребро замыкает его.
- Исходные ёмкости дуг из достижимой стороны наружу
Теорема о разрезе ограничивает поток исходной пропускной способностью выбранной границы. Остаточная сеть нужна для выбора стороны, а не для замены исходных ёмкостей в сумме.
- Три
Количество получается из кофактора, а не из определителя полного лапласиана. Два оставленных ребра можно выбрать тремя способами.
- Сразу будет пустой: допустимого топологического порядка нет
У каждой вершины есть входящее ребро от другой вершины цикла. Начать без нарушения хотя бы одной зависимости нельзя; алфавитное правило не отменяет рёбра.
- Четыре
Первые два объединения уменьшили число групп с шести до четырёх. В третьем оба объекта уже в группе {1,2,3}, поэтому нового слияния нет.
- {A,B}и{C}
A и B взаимно достижимы. До C можно дойти, но вернуться из неё нельзя, поэтому она не входит в общую компоненту с A и B.
Частые вопросы
Где посмотреть правильные ответы?
Включите «Показать ответы и пояснения» над вопросами. Тогда ответы будут видны на экране и попадут в печатный лист. Без этой отметки печатаются только задания.
Почему вопросов меньше выбранного количества?
Лист использует доступные вопросы выбранной темы и уровня, без повторения одного вопроса внутри набора. Если их меньше, количество не дополняется выдуманными или дублирующими заданиями.