Задача 2 — Ранг графа

Дан неориентированный граф. Ранг вершины — её степень. Ранг графа = max (rk(u) + rk(v)) по всем рёбрам (u,v). Найти ранг графа.

Определения с иллюстрацией

Степень (ранг) вершины rk(v) — сколько рёбер из неё выходит

Рёбра графа: 0-1, 0-2, 0-3, 3-4

Каждое ребро (u,v) добавляет +1 к степени обоих концов.

вершина	0	1	2	3	4
deg	3	1	1	2	1

У вершины 0 три ребра (к 1, 2, 3); у вершины 3 — два (к 0 и 4).

Ранг графа — максимум суммы степеней концов, по всем рёбрам

ребро	deg u + deg v	сумма
0 – 1	3 + 1	4
0 – 2	3 + 1	4
0 – 3	3 + 2	5 ← max
3 – 4	2 + 1	3

Ранг графа = 5 (жирное ребро 0–3).

⚠ Главная ловушка: максимум берётся по рёбрам, а не по любым парам вершин. Вершины 0 (deg 3) и 4 (deg 1) не соединены ребром → пару (0, 4) брать нельзя, даже если её сумма казалась бы выгодной. Поэтому нельзя «просто найти две вершины с наибольшими степенями» — они обязаны быть соединены.

Ход решения

Наблюдение: сам граф как структуру (список смежности / матрицу) хранить не нужно. Нужны только: массив степеней и список рёбер — а список рёбер уже есть на входе.

Алгоритм — два прохода по рёбрам

Проход 1 — степени. Для каждого ребра (u,v): deg[u] += 1, deg[v] += 1.
Проход 2 — максимум. Снова по всем рёбрам: считаем deg[u] + deg[v], держим максимум.

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

Асимптотика

Время O(|V| + |E|) Память O(|V|)
Два прохода по рёбрам — O(|E|), создание массива степеней — O(|V|).

Код (Python)

def graph_rank(n, edges):
    # n — число вершин (нумерация 0..n-1), edges — список пар (u, v)
    deg = [0] * n

    # проход 1: степени
    for u, v in edges:
        deg[u] += 1
        deg[v] += 1

    # проход 2: максимум суммы степеней концов ребра
    best = 0
    for u, v in edges:
        best = max(best, deg[u] + deg[v])

    return best

Подводные камни (что спросят / на чём падают)

Нет рёбер вообще. Тогда ранг не определён. best = 0 вернёт 0 — уточни у экзаменатора, годится ли это, или нужен особый случай.
Максимум по рёбрам, не по парам. Та самая ловушка из иллюстрации — не бери две вершины с наибольшими степенями, если между ними нет ребра.
Нумерация вершин. С 0 → массив размера n; с 1 → размера n+1. Иначе IndexError.
Петли и кратные рёбра. Петля (v,v) обычно добавляет к степени 2. Кратные рёбра считаются каждое. Если они есть в твоём варианте — спроси, как их учитывать.
Один проход вместо двух. Нельзя совмещать подсчёт степеней и поиск максимума в одном цикле — степени должны быть готовы заранее.

Мини-проверка себя

☐ Понимаю, что rk(v) = степень = число рёбер из v.
☐ Ранг графа — max по рёбрам, а не по любым парам вершин.
☐ Решаю в два прохода: сначала все степени, потом максимум.
☐ Назову асимптотику O(|V|+|E|) и почему.
☐ Знаю, что делать с пустым графом / петлями / нумерацией.