Привет, CodeForces!

Время от времени на CodeForces появляются вопросы о центре, радиусе и диаметре графа (смог нагуглить только о дереве, хотя было больше). В этом топике даны определения этим понятиям а также описаны алгоритмы для их нахождения.

Задача: дан не взвешенный неориентированный граф G = (V, E), где V это множество вершин, а E — множество ребер. Необходимо найти его радиус, диаметр и центр.

Определим d_i, j как кратчайшее расстояние между парой вершин . Тогда диаметр графа определяется как максимально возможное среди всех кратчайших расстояний между парой вершин:

Также введем понятие эксцентриситета вершины как максимальное расстояние от вершины до какой-либо другой:

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

Сразу можно заметить, что диаметр графа это максимальный эксцентриситет в графе, т.е:

Центром графа назовем все вершины с эксцентриситетом, равным радиусу графа:

Определения даны и в голову приходит тривиальный алгоритм для нахождения центра, радиуса и диаметра для произвольного графа при помощи алгоритма Флойда-Уоршелла:

const int   N = ...; // Количество вершин в графе
const int   INF = ...; // Бесконечность
int         d[N][N]; // Дистанции в графе
int         e[N]; // Эксцентриситет вершин
set <int>   c; // Центр графа
int         rad = INF; // Радиус графа
int         diam; // Диаметр графа

// Алгоритм Флойда-Уоршелла
for (int k = 0; k < N; k++) {
    for (int j = 0; j < N; j++) {
        for (int i = 0; i < N; i++) {
            d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
        }
    }
}

// Нахождение эксцентриситета
for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
        e[i] = max(e[i], d[i][j]);
    }
}

// Нахождение диаметра и радиуса
for (int i = 0; i < n; i++) {
    rad = min(rad, e[i]);
    diam = max(diam, e[i]);
}

for (int i = 0; i < n; i++) {
    if (e[i] == rad) {
        c.insert(i);
    }
}

Теперь немного изменим постановку задачи: допустим, что граф G является деревом. Для дерева несложно доказать следующий факт: количество вершин в центре дерева равно одному или двум.

На CodeForces когда-то слышал следующий алгоритм для нахождения центра дерева: с помощью BFS-а из любой вершины (обозначим ее как v1) найти самую удаленную от v1 вершину (обозначим как v2), затем запустить BFS из v2, выбрать любую самую удаленную от v2 вершину (пусть будет v3). Вершина(-ы) на середине пути между v2 и v3 образуют центр графа, расстояние между ними — диаметр. Радиусом же будет половина диаметра, округленная вверх: (diam(G) + 1) / 2. Реализацию этого алгоритма здесь приводить не буду, так как она мне показалась несколько громоздкой. Вместо этого приведу другой алгоритм, который мне показался проще в реализации.

Теорема: Пусть L — множество всех листьев графа. Если |V| ≤ 2, то L является центром графа, иначе можно удалить все листья и центр графа не изменится:

Эта теорема приводит нас к следующему алгоритму: будем удалять листья дерева, слой за слоем, пока не останется  ≤ 2 вершин. Эти вершины и будут центром графа. Реализация данного алгоритма очень похожа на поиск в ширину:

const int   N = ...; // Количество вершин в графе
int         maxlevel = 0; // Уровень, на котором будет расположен центр графа
int         level[N]; // Уровень вершины
int         degree[N]; // Степень вершины
int         g[N][N]; // Матрица смежности
set <int>   c; // Центр графа
queue <int> q; // Очередь для алгоритма

// Начинаем с листьев
for (int i = 0; i < N; i++) {
    if (degree[i] == 1) {
        q.push(i);
    }
}

while (!q.empty()) {
    int v = q.front();
    q.pop();

    // Удаляем лист и пытаемся добавить его предка
    for (int i = 0; i < N; i++) {
        if (g[v][i]) {
            degree[i]--;
            
            if (degree[i] == 1) {
                q.push(i);
                level[i] = level[v] + 1;
                maxlevel = max(maxlevel, level[i]);
            }
        }
    }
}

for (int i = 0; i < N; i++) {
    if (level[i] == maxlevel) {
        c.insert(i);
    }
}

Нетрудно доказать, что после исполнения данного алгоритма, центр дерева будет во множестве c, и rad(G) = (diam(G) + 1) / 2.

Задачек на порешать сходу не нашел, так что если знаете — ждем в комментах.

Задачки по теме:

• IOI2013 Dreaming
• 456E - Цивилизация
• 592D - Супер М
• Задача F отсюда

Спасибо за внимание, насчет опечаток просьба писать в личку.