Радиус графа какой лучше всего

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

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

1)

2) ;

3) .

Определим расстояние от каждой вершины графа до самой далекой от нее вершины

,

которое называется эксцентриситетом. Очевидно, что эксцентриситет для всех вершин в полного графа равен единице, а для вершин простого цикла – .

Максимальный эксцентриситет носит название диаметра графа, а минимальный – радиуса графа . В полном графе имеем , а в простом цикле – .

Вершина называется центральной, если . Граф может иметь несколько таких вершин, а в некоторых графах все вершины являются центральными. В простой цепи при нечетном числе вершин только одна является центральной, а при четном их числе таких вершин две. В полном графе и для простого цикла центральными являются все вершины. Множество центральных вершин называется центром графа.

Пример 1. Найти диаметр, радиус и центр графа, приведенного на рис. 4.

° °

° ° °

° °

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

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

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

Матрицы достижимостей и контрадостижимостей

Матрица достижимостей определяется следующим образом:

Множество вершин графа , достижимых из заданной вершины , состоит из таких элементов , для которых -й элемент в матрице равен 1. Это множество можно представить в виде

.

Матрица контрадостижимостей (обратных достижимостей) определяется следующим образом:

Аналогично построению достижимого множества можно сформировать множество , используя следующее выражение:

.

Из определений следует, что -й столбец матрицы совпадает с -й строкой матрицы , т. е. , где – матрица, транспонированная к матрице .

Пример 2. Найти матрицы достижимостей и контрадостижимостей для графа, приведенного на рис. 5.

°

°

°

°

°

°

°

Определим множества достижимостей для вершин графа:

,

,

,

,

,

,

.

Следовательно, матрицы достижимостей и контрадостижимостей имеют вид:

, .

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

Можно определить также матрицы ограниченных достижимостей и контрдостижимостей, если потребовать, чтобы длины путей не превышали некоторого заданного числа. Тогда будет верхней границей длины допустимых путей.

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

Теория графов – Основные свойства

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

Расстояние между двумя вершинами

Это число ребер в кратчайшем пути между вершиной U и вершиной V. Если существует несколько путей, соединяющих две вершины, то кратчайший путь рассматривается как расстояние между двумя вершинами.

Обозначение – d (U, V)

Может быть любое количество путей из одной вершины в другую. Среди них вам нужно выбрать только самый короткий.

пример

Посмотрите на следующий график –

Здесь расстояние от вершины ‘d’ до вершины ‘e’ или просто ‘de’ равно 1, поскольку между ними есть одно ребро. Существует много путей от вершины ‘d’ до вершины ‘e’ –

• да, а, бе
• дф, фг, гэ
• де (считается для расстояния между вершинами)
• дф, фц, ca, ab, be
• да, ac, cf, fg, ge

Эксцентриситет вершины

Максимальное расстояние между вершиной и всеми остальными вершинами рассматривается как эксцентриситет вершины.

Обозначение – e (V)

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

пример

На приведенном выше графике эксцентриситет «а» равен 3.

Расстояние от «a» до «b» равно 1 («ab»),

от «а» до «d» равно 1 («объявление»),

Таким образом, эксцентриситет равен 3, что является максимумом от вершины «а» от расстояния между «ag», которое является максимальным.

Радиус связного графа

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

Обозначение – r (G)

Из всех эксцентриситетов вершин графа радиус связного графа является минимумом всех этих эксцентриситетов.

Пример – На приведенном выше графике r (G) = 2, что является минимальным эксцентриситетом для «d».

Диаметр графика

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

Обозначение – d (G)

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

Пример. На приведенном выше графике d (G) = 3; что является максимальным эксцентриситетом.

Центральная точка

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

тогда «V» является центральной точкой графа «G».

Пример – в примере графика ‘d’ является центральной точкой графика.

Центр

Множество всех центральных точек «G» называется центром графа.

Пример. В примере графика <‘d’>является центром графика.

Длина окружности

Число ребер в самом длинном цикле «G» называется окружностью «G».

Пример. На графике примера длина окружности равна 6, что мы получили из самого длинного цикла acfgeba или acfdeba.

обхват

Число ребер в кратчайшем цикле G называется его обхват.

Обозначения – g (G).

Пример – в примере графика обхват графа равен 4, который мы получили из кратчайшего цикла acfda или dfged или abeda.

Теорема о сумме степеней вершин

Если G = (V, E) ненаправленный граф с вершинами V = 1 , V ₂ ,… V _n >, то

Следствие 1

Если G = (V, E) ориентированный граф с вершинами V = 1 , V ₂ ,… V _n >, то

Следствие 2

В любом неориентированном графе число вершин с нечетной степенью является четным.

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

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

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

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

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

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

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

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

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

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₄.