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

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

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

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

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

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

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

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

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

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

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

Вершина , для которой

называется внешним центром графа G; и аналогично вершина , для которой

называется внутренним центром графа G.

У графа может быть несколько внешних и внутренних центров. Таким образом, они образуют множества внешних и внутренних центров соответственно.

Число внешнего разделения вершины , являющейся внешним центром, называется внешним радиусом: ; число внутреннего разделения внутреннего центра называется внутренним радиусом: .

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

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

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

Итак, если представляет дугу графа с весом , то точка y, помещаемая на этой дуге, может быть определена посредством задания длины участка причем должно выполняться равенство

Числа разделения и точки y независимо от того, является она вершиной графа G или искусственной точкой дуги графа G определяются следующим образом:

Точка , для которой

называется абсолютным внешним центром графа; и аналогично определяется — абсолютный внутренний центр.

Число внешнего разделения абсолютного внешнего центра называется абсолютным внешним радиусом , и число внутреннего разделения абсолютного внутреннего центра называется абсолютным внутренним радиусом: .

Местоположение «искусственных точек» можно определить с помощью алгоритма Хакими или классическим методом, который можно использовать после генерации «искусственных точек».

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

Понятие центра графа допускает следующее обобщение: можно рассматривать не отдельную точку (центр), а множество из p точек, которые образуют кратный центр (p-центр).

Пусть — подмножество (содержащее p вершин) множества X вершин графа . Через будем обозначать наикратчайшее из расстояний между вершинами множества и вершиной , т.е.

Подобно тому, как определялись числа разделения вершин, определяются числа разделения для множеств вершин:

где и — числа внешнего и внутреннего разделения множества .

Множество , для которого

называется p-кратным внешним центром графа G; аналогично определяется p-кратный внешний центр .

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

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

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

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

MikeMirzayanov → Codeforces Single Account Policy: zh0ukangyang is Removed from the Rating

maomao90 → Editorial for Hello 2024

standoff → Еhis isn’t fair.

CheaterExposer → [UPDATE] Codeforces Cheater IOI Medalist

sarthak1357 → CSES shortest routes 1

mohammed_orkhan → I wnat to be EXPERT!!

maomao90 → I am top 1 contributor. AMA!

Некропост

Pyqe → Codeforces Round #831 (Div. 1 + Div. 2, based on COMPFEST 14 Final) Editorial

Некропост

arham_doshi → cses graph session editorial(incomplete)

SAD_IN_NIGHTMARE → 2024 OIs

parth_1818 → Know Some Sorting Techniques

stefdasca → Easy and Quick Video Tutorials for the CSES Problem Set

I_am_Polish_Girl → Dijkstra Algorithgm

atcoder_official → AtCoder Beginner Contest 335 (Sponsored by Mynavi) Announcement

awoo → Разбор Educational Codeforces Round 149

Vectrizz → Золотой расчет: оптимизация ценности в рюкзаке с умением раздробить слитки!

Hexagons → [OFF TOPIC] Hollow Knight radiant tutorial for bossfight «Markoth»

pajenegod → The Ultimate Reroot Template

triumphh → What rating on codeforces should I aim for to crack ZCO and INOI?

Некропост

sahal → CSES Problemset Editorials (almost all section editorial collection)

Некропост

Zlobober → Checkers with testlib.h

oversolver → Expert for the first time since 2011, AMA

Algorithms_with_Shayan → How to approach DP problems & DP playlist

Nurali16 → tourist is not noob . he is genius

Некропост

AminAnvari → Segment Tree Problems

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

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

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

Время от времени на 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 отсюда

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

Теги

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

3.2.2. Расстояния в графе. Диаметр, центр, радиус графа

Для графа G, изображенного на рис. 3.16, найти радиус, диаметр и центры.

Рис. 3.16. Граф для примера 82

Чтобы определить центры, радиус, диаметр графа G, найдем матрицу D(G) расстояний между вершинами графа, элементами d_ij которой будут расстояния между вершинами v_i и v_j. Для этого воспользуемся графическим представлением графа. Заметим, что матрица D(G) симметрична относительно главной диагонали.

С помощью полученной матрицы для каждой вершины графа G определим наибольшее удаление из выражения: для i, j = 1, 2, …, 5. В результате получаем: r(v₁) = 3, r(v₂) = 2, r(v₃) = 2, r(v₄) = 2, r(v₅) = 3. Минимальное из полученных чисел является радиусом графа G, максимальное – диаметром графа G. Значит, R(G) = 2 и D(G) = 3, центрами являются вершины v₂, v₃, v₄.

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

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

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

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

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

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

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

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

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

3.2.2. Расстояния в графе. Диаметр, центр, радиус графа

Категории

Свежие записи

Добавить комментарий Отменить ответ