Как найти центр графа

Центр и радиус графа

Вершина , для которой , называется внешним центром графа G; и аналогично вершина , для которой , называется внутренним центром графа G. У графа может быть несколько внешних и внутренних центров. Таким образом, они образуют множества внешних и внутренних центров соответственно. Число внешнего разделения вершины , являющейся внешним центром, называется внешним радиусом: ; число внутреннего разделения внутреннего центра называется внутренним радиусом: . У графа изображенного на рис. 2.1, с матрицей расстояний, приведенный выше, имеются только один внешний и один внутренний центры. Внешний радиус графа равен 15, а внутренний 27.

Абсолютный центр графа

Соотношения и определяют числа разделения для любой вершины в графе . Это определение можно обобщить на случай «искусственных точек», которые можно помещать на дугах. Итак, если представляет дугу графа с весом , то точка y, помещаемая на этой дуге, может быть определена посредством задания длины участка причем должно выполняться равенство . Числа разделения и точки y независимо от того, является она вершиной графа G или искусственной точкой дуги графа G определяются следующим образом: , . Точка , для которой , называется абсолютным внешним центром графа; и аналогично определяется — абсолютный внутренний центр. Число внешнего разделения абсолютного внешнего центра называется абсолютным внешним радиусом , и число внутреннего разделения абсолютного внутреннего центра называется абсолютным внутренним радиусом: . Местоположение «искусственных точек» можно определить с помощью алгоритма Хакими или классическим методом, который можно использовать после генерации «искусственных точек».

Кратные центры (р-центры) графа

Понятие центра графа допускает следующее обобщение: можно рассматривать не отдельную точку (центр), а множество из p точек, которые образуют кратный центр (p-центр). Пусть — подмножество (содержащее p вершин) множества X вершин графа . Через будем обозначать наикратчайшее из расстояний между вершинами множества и вершиной , т.е. Аналогично . Подобно тому, как определялись числа разделения вершин, определяются числа разделения для множеств вершин: , , где и — числа внешнего и внутреннего разделения множества . Множество , для которого , называется p-кратным внешним центром графа G; аналогично определяется p-кратный внешний центр . Для нахождения p-центра надо построить всевозможные множества вершин , содержащие p вершин, а затем, непосредственно найти множества и , образующие p-центры. Однако находить таким же способом p-центр целесообразно лишь для небольших графов и для небольших значений величины p.

Практическое применение задачи размещения центров

В практической деятельности постоянно возникают задачи «наилучшего» размещения оборудования или средств обслуживания в сложных системах. В частности, если граф представляет сеть дорог, и вершины соответствуют отдельным районам, то можно поставить задачу оптимального размещения больниц, пожарных частей и других необходимых предприятий и сервисных служб. В таком случае критерий оптимальности может состоять в минимизации расстояния (или времени проезда) от пункта обслуживания до самой удаленной вершины графа, т.е. в оптимизации «наихудшего варианта». В более общей задаче требуется разместить несколько таких пунктов обслуживания. При этом самая отдаленная вершина графа должна находиться, по крайней мере, от одного пункта обслуживания на минимально возможном расстоянии. К таким задачам относятся задачи размещения аварийных служб, и поэтому объективным требованием здесь является минимизация наибольшего расстояния от произвольной вершины графа до ближайшего к ней пункта обслуживания. Задачи такого типа называются минимаксными задачами размещения и полученные при решении этих задач места размещения пунктов обслуживания называются центрами графа.

Как найти центр графа

-kirito- → TheForces Round #25 Editorial

elshiko → Квалификационный раунд Yandex Cup 2023

plourde27 → California Informatics Competition (CALICO) Fall ’23

Yhlas_Y → Favourite problem

islamicTerrorist69 → Facing problem in dynamic programming

SilverSurge → CSES Range Queries: Polynomial Queries

127.0.0.1 → Codeforces Round 907 (Div. 2)

_thor__ → Codeloop 2023: A Knockout Tournament Based Coding Contest

Yhlas_Y → IDE for cp

MikeMirzayanov → Please, read this

Imakf → Codeforces Round 906 Editorial

noomaK → IEEEXtreme 17.0 Problems Discussion

chenjb → Rescheduling of World Finals 22&23

anmolsainiii23 → Confused Regarding Cses 2nd DP Question

stdfloat → Is CF enough for IZHO, IOI?

DeadPixel99 → Help needed!

Vladosiya → Codeforces Command Lines (2023-10-06)

-kirito- → Invitation to TheForces #25 (5^2-Forces, TheForces-Rated, Prizes!)

one_autum_leaf → Find the number of rectangles of same color in a matrix

ryuukumar → What to learn to solve 1300 rated questions?

Imakf → Codeforces Round 906 (Div. 1, Div. 2)

74TrAkToR → Codeforces Round #904 (Div. 2) Editorial

whynesspower → Reverse check the questions: ChatGPT

aryang22 → Perhaps you should wait a little before giving up.

Alpha_Info → Listen to music?

Блог пользователя BekzhanKassenov

Центр графа и его нахождение

Автор BekzhanKassenov, 8 лет назад ,

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

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

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

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

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

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

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

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

const int N = . ; // Количество вершин в графе const int INF = . ; // Бесконечность int d[N][N]; // Дистанции в графе int e[N]; // Эксцентриситет вершин set 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 c; // Центр графа queue 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 отсюда

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

диаметр, радиус, дерево, граф, центр дерева

Поиск радиуса и диаметра графа

Эксцентриситетом вершины называется расстояние до самой дальней вершины графа.

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

Диаметром графа — это наибольшее расстояние между всеми парами вершин графа

Центральной вершиной графа является вершина чей эксцентриситет равен радиусу графа.

Периферийной вершиной графа является вершина чей эксцентриситет равен диаметру графа.

Поиск радиуса и диаметра

Сервис граф онлайн позволит вам найти радиус и диаметр, а также укажет центральные и периферийные вершины. Для этого выберете пункт меню Алгоритмы -> Поиск радиуса и диаметра графа.

© Граф Online — создание и визуализация графа в два клика или по матрице смежности и поиск кратчайшего пути, поиск компоненты связности, поиск Эйлеровго цикла. Поделиться: Twitter, Facebook, В Контакте. 2016. (Edit — History — Print — Recent Changes — Search)

Описание алгоритма поиска центра графа

Центром является любая вершина х с наименьшим значением МВВ(х) (максимальное расстояние вершина-вершина), т. е. центр — это любая вершина х, такая, что расстояние от нее до наиболее отдаленной вершины минимально.

Центр отыскивается как один из элементов матрицы DN, значение i, j-го элемента которой — di,j есть кратчайшее расстояние от вершины i к вершине j. Элементы матрицы могут быть вычислены с помощью алгоритма Флойда или алгоритма Данцига.

Алгоритм Флойда является одним из методов поиска кратчайших путей в графе. В отличии от алгоритма Дейкстры, который позволяет при доведении до конца построить ориентированное дерево кратчайших путей от некоторой вершины, метод Флойда позволяет найти длины всех кратчайших путей в графе. Конечно эта задача может быть решена и многократным применением алгоритма Дейкстры (каждый раз последовательно выбираем вершину от первой до N-ной, пока не получим кратчайшие пути от всех вершин графа), однако реализация подобной процедуры потребовала бы значительных вычислительных затрат.

Алгоритм Данцига — этот алгоритм отличается от алгоритма Флойда последовательностью выполнения действий. Перенумеруем все вершины графа от 1 до n целыми числами и обозначим через di,jm длину пройденного пути из i в j где в качестве промежуточных использованы первые m вершин графа. Матрица Dm длин кратчайших путей имеет здесь размерность m*m.

Вернемся теперь к описанию алгоритма поиска центра графа:

Максимальное расстояние МВВ(i) от вершины i до любой вершины графа является элементом i-й строки матрицы DN, имеющим максимальное значение. Центром является произвольная вершина х с наименьшим среди всех вершин графа значением МВВ(х), т. е. центр — это произвольная вершина х, которой соответствует строка матрицы DN, содержащая элемент с наименьшим максимальным значением.

Если описать алгоритм поиска центра коротко, то он будет выглядеть следующим образом

• 1. находим D0 — матрицу, элементами которой являются ai,j — длины кратчайших дуг.
• 2. Ищем DN — матрицу длин кратчайших расстояний по Флойду или Данцегу.
• 3. Определяем МВВ(i) для каждой вершины графа.
• 4. Из всех МВВ(i) выбираем минимальное соответствующая вершина и будет центром.

Допустим нам необходимо найти центр графа представленного на рисунке:

Рис 1. Исходный граф

Составим матрицу длин кратчайших дуг между каждой парой вершин — D0, в случае, если дуги между вершиной i и j не существует, элементу ai,j матрицы присваивается значение ?. Матрица D0:

C помощью алгоритма Флойда или Данцега получаем матрицу длин кратчайших путей между каждой парой вершин графа:

Теперь, основываясь на полученной нами матрице длин кратчайших путей, найдем МВВ(i) для каждой вершины графа

Центром графа является такая вершина x, для которой МВВ(x)=min. Минимальное значение имеет МВВ(7)=104, а это значит, что вершина 7 является центром графа.

Описание исходного кода программы

В практической части рассмотрена задача нахождения центра, согласно описанному выше алгоритму. В качестве ребер используется расстояния между элементами графа, а в качестве вершин элементы матрицы. Матрица исходных вершин обязательно должна быть квадратной, так как задача должна решаться и для ориентированных графов. Все исходные расстояния записываются в эту матрицу, а затем уже над ней выполняются операции. Расстояние из одной вершины в ту же самую отмечается как 0, если же между вершинами нет прямого пути, то это расстояние описывается как большое число, так чтобы сумма остальных чисел точно не была больше него. Это сделано из-за того, что в языках программирования нельзя дать значение бесконечности как обычного числе.

Кроме созданных самостоятельно классов были использованы также классы, находящиеся в стандартной библиотеке, среди которых:

java.io.* — который содержит классы для работы с потоком ввода/вывода

java.util.Scanner — который содержит классы для работы с вводом/выводом чтением из файла и работы с ним.

Приведем весь исходный код программы:

файл GraphCenterFinder.java

public class GraphCenterFinder

//Метод должен принимать в качестве параметра имя файла

//с матрицей расстояний исходного графа

//вызов: java GraphCenterFinder имя_файла.txt

public static void main(String[] args)

//Проверка правильности указания параметров

System.out.println(«Ошибка! Не указано имя файла.»);

default: граф множество вершина код

System.out.println(«Неверно указаны параметры для запуска программы.»);

String fileName = args[0];

Graph graph = new Graph(«Graph», fileName);

файл Graph.java

public class Graph

//Имя файла, содержащего граф

private String fileName;

private String name;

private int vertexCount; //Количество вершин в графе

private int[][] graph; // Матрица с исходным графом

private int[][] shortcut; //Матрица кратчайших расстояний

/*eccentricity — Массив эксцентриситетов.

* в этом одномерном массиве опеределено значение от наиболее удаленной вершины графа

* до текущей вершины

* Сама удаленная вершина не так важна, неоходимо знать только расстояние

private int eccentricity[];

/*переменная minEccentricity собственно и является искомой

* величиной обозначающей радиус графа. Вершины, значение которых совпадает с данной переменной

• * являются центрами графа.
• * */

private int minEccentricity;

Graph (String nameParam, String fileNameParam)

public void findGraph()

try (Scanner fileScanner = new Scanner(new File(fileName)))

//Создание массива и его обнуление

graph = new int[vertexCount][vertexCount];

//Чтение матрицы графа из файла

graph[i][j] = Integer.MAX_VALUE/100;//Примем бесконечность за сотую долю максимального значения, чтоб не иметь проблем при сложении максимальных чисел

> catch (FileNotFoundException e)

System.err.println(«Ошибка! Данный файл не найден»);

public void getGraph()

if (graph[i][j] == Integer.MAX_VALUE/100)

//Алгоритм Флойда-Уоршера для нахождения минимального расстояния между всеми вершинами

public void floydAlgorithm()

shortcut = new int[vertexCount][vertexCount];

if (shortcut[i][k] != 0 && shortcut[k][j] != 0 && i != j)

shortcut[i][j] = shortcut[i][k] + shortcut[k][j];

System.out.println(» Таблица кратчайших расстояний между вершинами, найденная согласно алгоритму Флойда-Уоршера»);

//Функция нахождения наибольших расстояний от вершин

public void CenterFinder()

eccentricity = new int[vertexCount];

System.out.println(» Расстояние от каждой из вершин до другой наиболее удаленной(ых) вершин(ы)»);

if (shortcut[i][j] > max)

System.out.println(«MBB(» + (i+1) + «) Расстояние от центра графа до наиболее удаленных(ой) вершин(ы) — » + minEccentricity);

/*Минимальный эксцентриситет может быть не у одной вершины, а у нескольких.

• * В таком случае все вершины, которые имеют такое же значение являются центрами графа
• * */

System.out.print(» Центром графа явля(ю)тся вершина(ы): «);

if (eccentricity[i] == minEccentricity)

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

В первой строке буква, которая определяет, что за ней действительно следует число. Во второй строке должно находится число, обозначающее количество вершин в матрице.

Далее по порядку должны находится значения матрицы расстояний между вершинами матрица должна быть квадратной, то есть в ней должно содержаться одинаковое количество строк и столбцов. Диагональные элементы матрицы должны быть равны нулю, ну а вершины, не имеющие прямого пути должны обозначаться через дефис (-). Элементы матрицы должны располагаться последовательно и разделяться пробелом друг от друга. Если же определяются ребра следующей вершины, то необходимо осуществить перевод строки.

Для того чтобы указать файл, содержащий исходную матрицу, необходимо передать имя этого файла в качестве параметра при вызове главной функции. При этом если файл указан неверно или если он вообще не был указан, то программа сообщит об этом и выдаст предупреждение.