⚙️ Алгоритмы · 20 вопросов · ~45 мин · ⏱ Таймер 45:00 · Сложный ·

Остовные деревья и связность

Минимальный остов соединяет все вершины с минимальной общей стоимостью, но не заменяет дерево кратчайших путей. Тест просит проверять кандидатов на цикл, вести компоненты DSU, расширять область Прима и распознавать рёбра, без которых граф распадается.

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

⏱ --:--

💡 Инструкция: Выбери один ответ из четырёх. В тесте 20 вопросов и 45 минут. После завершения откроются общий процент, четыре тематические шкалы, правильные ответы и пояснения.

Вопрос 1 из 20

Сколько рёбер в остовном дереве связного графа из 8 вершин?

|E_T|=|V|-1

V = 8
print(V - 1)

8 6 7 9

Вопрос 2 из 20

Что минимизирует минимальное остовное дерево?

Число вершин графа Расстояние от выбранного источника до каждой вершины отдельно Суммарный вес рёбер, соединяющих все вершины без циклов Максимальную степень корня

Вопрос 3 из 20

Какое ребро можно безопасно взять по свойству разреза?

S = {0, 1, 4}
crossing_edges = [
    (4, 1, 2),
    (7, 4, 3),
    (9, 0, 5),
]

# Кортеж: (вес, вершина из S, вершина вне S).

Вес 4 Вес 7 Вес 9 Любое из трёх независимо от веса

Вопрос 4 из 20

Если все веса рёбер различны, что можно сказать о минимальном остовном дереве связного графа?

В остов входят все рёбра, которые легче медианного ребра графа Минимальный остов единственен Остов существует только тогда, когда исходный граф уже является деревом Минимальных остовов может быть несколько

Вопрос 5 из 20

Является ли набор остовом?

V = 5
chosen_edges = [(0, 1), (1, 2), (2, 0), (3, 4)]
parent = list(range(V))
cycle_found = False
for u, v in chosen_edges:
    if find(parent, u) == find(parent, v):
        cycle_found = True
    else:
        union(parent, u, v)
components = len({find(parent, v) for v in range(V)})

Да, потому что все вершины встречаются Нет только из-за отсутствия весов Нет: есть цикл и две компоненты Да, потому что рёбер V−1

Вопрос 6 из 20

Какой суммарный вес выберет Краскал?

def find(parent, x):
    if parent[x] != x:
        parent[x] = find(parent, parent[x])
    return parent[x]

def union(parent, a, b):
    ra, rb = find(parent, a), find(parent, b)
    if ra != rb:
        parent[rb] = ra

edges = [(1, 0, 1), (2, 1, 2), (2, 0, 2), (3, 2, 3), (4, 1, 3)]
parent = list(range(4))
total = 0
for weight, u, v in edges:
    if find(parent, u) != find(parent, v):
        union(parent, u, v)
        total += weight
print(total)

7 5 8 6

Вопрос 7 из 20

Что проверяет условие find(u) != find(v)?

if find(u) != find(v):
    union(u, v)
    take(edge)

У вершин u и v разные степени в текущем лесу Ребро легче всех остальных рёбер графа Концы уже связаны путём, поэтому ребро замкнёт цикл Концы лежат в разных компонентах, поэтому ребро не создаст цикл

Вопрос 8 из 20

Зачем DSU использует сжатие путей?

Чтобы хранить для каждой вершины полный список соседей и быстро строить обход Чтобы удалять циклические рёбра из графа сразу после объединения компонент Чтобы при каждом find дополнительно сортировать веса рёбер внутри текущей компоненты Чтобы последующие find быстрее приводили вершины прямо к представителю

Вопрос 9 из 20

Какие компоненты останутся после объединений?

def find(parent, x):
    if parent[x] != x:
        parent[x] = find(parent, parent[x])
    return parent[x]

def union(parent, a, b):
    ra, rb = find(parent, a), find(parent, b)
    if ra != rb:
        parent[rb] = ra

parent = list(range(6))
for a, b in [(0, 1), (2, 3), (1, 2), (4, 5)]:
    union(parent, a, b)
components = {}
for vertex in range(6):
    root = find(parent, vertex)
    components.setdefault(root, set()).add(vertex)
print(list(components.values()))

{0,1,2}, {3,4,5} {0,1}, {2,3}, {4,5} {0,1,2,3} и {4,5} Одна компонента из шести

Вопрос 10 из 20

Когда Краскал особенно удобен?

Когда граф плотный и дан матрицей, а строить полный список рёбер невыгодно Когда требуется найти расстояния от одной вершины до всех остальных Когда граф разрежен и уже задан списком взвешенных рёбер Когда нужно поддерживать связность после произвольных удалений рёбер в реальном времени

Вопрос 11 из 20

Какое ребро выберет Прим следующим?

used = {0, 1}
frontier = [
    (6, 0, 2),
    (2, 1, 2),
    (5, 1, 3),
]

# Кортеж: (вес, вершина в дереве, новая вершина).
# На следующем шаге Прим выбирает одно ребро frontier.

1-3 вес 5 0-2 вес 6 Ребро внутри S 1-2 вес 2

Вопрос 12 из 20

Почему запись из кучи пропускается?

while heap:
    weight, vertex, parent = heappop(heap)
    if used[vertex]:
        continue
    break

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

Вопрос 13 из 20

Чем Прим отличается от Краскала по росту решения?

Прим поддерживает одно связное дерево, Краскал — лес компонент, который постепенно сливается Прим поддерживает лес компонент, а Краскал всегда расширяет одно дерево от стартовой вершины Прим рассматривает только рёбра внутри текущего дерева, а Краскал — только рёбра внутри компонент Оба алгоритма всё время поддерживают одно дерево; различается лишь устройство очереди

Вопрос 14 из 20

Какой суммарный вес получится?

from heapq import heappush, heappop

graph = {
    0: [(1, 4), (2, 1)],
    1: [(0, 4), (2, 2), (3, 1)],
    2: [(0, 1), (1, 2), (3, 5)],
    3: [(1, 1), (2, 5)],
}

# Алгоритм Прима стартует из вершины 0
# и каждый раз берёт минимальное граничное ребро.

6 4 5 7

Вопрос 15 из 20

Какая реализация Прима часто лучше для очень плотного графа в матрице?

E\approx V^2

Простая O(V²) без кучи BFS без весов Полный перебор всех деревьев Обязательно список рёбер и DSU

Вопрос 16 из 20

Что ответит DSU после операций?

def find(parent, x):
    if parent[x] != x:
        parent[x] = find(parent, parent[x])
    return parent[x]

def union(parent, a, b):
    ra, rb = find(parent, a), find(parent, b)
    if ra != rb:
        parent[rb] = ra

parent = list(range(5))
for a, b in [(0, 1), (1, 2), (3, 4)]:
    union(parent, a, b)
print(find(parent, 0) == find(parent, 2),
      find(parent, 0) == find(parent, 4))

False True False False True True True False

Вопрос 17 из 20

Является ли ребро 1-3 мостом?

graph = {
    0: {1, 2},
    1: {0, 2, 3},
    2: {0, 1},
    3: {1},
}

edge = (1, 3)
# Проверяется, изменится ли число компонент
# после удаления edge из обеих множеств смежности.

Нет: после удаления остаётся путь 3→2→1 через треугольник Да только в том случае, если вес 1–3 меньше весов рёбер треугольника Да: после удаления вершина 3 отделится от остальных Нет: раз вершина 1 входит в цикл, каждое её ребро имеет обходной путь

Вопрос 18 из 20

Как характеризуется мост в неориентированном графе?

Его удаление увеличивает длину некоторых путей, но не меняет число компонент Оно принадлежит хотя бы одному циклу, который исчезает после удаления Оно не входит ни в один минимальный остов связного графа Его удаление увеличивает число компонент связности

Вопрос 19 из 20

Какое условие указывает на мост в DFS-дереве?

DFS(v, parent):
    tin[v] = low[v] = timer++
    for u in graph[v]:
        if u == parent: continue
        if visited[u]:
            low[v] = min(low[v], tin[u])
        else:
            DFS(u, v)
            low[v] = min(low[v], low[u])
            if [условие для ребра v-u]:
                bridges.add((v, u))

low[u] > tin[v] low[u] <= tin[v] tin[u] == 0 low[v] > tin[u]

Вопрос 20 из 20

Почему DSU не подходит напрямую для произвольных удалений рёбер в ходе работы?

find/union\approx O(\alpha(n))

После union структура теряет представителей, и операция find перестаёт различать вершины DSU хранит число компонент, но не может получить идентификатор удаляемого ребра Удаление можно обратить операцией union в обратную сторону, но только без сжатия путей Он хорошо сливает компоненты, но обычная структура не умеет разделять уже объединённое множество

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

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

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

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