Главная страница Случайная страница КАТЕГОРИИ: АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника |
Диаметр, радиус и центр графа
Для связного графа определим расстояние между двумя его вершинами и как длину самой короткой цепи, соединяющей эти вершины, и обозначим через . Длина цепи – это количество ребер, составляющих цепь. Нетрудно проверить, что введенное расстояние удовлетворяет аксиомам метрики: 1) 2) ; 3) . Определим расстояние от каждой вершины графа до самой далекой от нее вершины , которое называется эксцентриситетом. Очевидно, что эксцентриситет для всех вершин в полного графа равен единице, а для вершин простого цикла – . Максимальный эксцентриситет носит название диаметра графа, а минимальный – радиуса графа . В полном графе имеем , а в простом цикле – . Вершина называется центральной, если . Граф может иметь несколько таких вершин, а в некоторых графах все вершины являются центральными. В простой цепи при нечетном числе вершин только одна является центральной, а при четном их числе таких вершин две. В полном графе и для простого цикла центральными являются все вершины. Множество центральных вершин называется центром графа. Пример 1. Найти диаметр, радиус и центр графа, приведенного на рис. 4.
° ° ° ° °
° °
° ° Рис. 4.
Для решения этой задачи удобно предварительно вычислить матрицу расстояний между вершинами графа. В данном случае это будет матрица размером , в которой на месте стоит расстояние от вершины до вершины : Для каждой строки матрицы находим наибольший элемент и записываем его справа от черточки. Наибольшее из этих чисел равно диаметру графа , наименьшее – радиусу графа . Центр графа составляют центральные вершины и . Понятия центральной вершины и центра графа появились в связи с задачами оптимального размещения пунктов массового обслуживания, таких как больницы, пожарные части, пункты охраны общественного порядка и т. п., когда важно минимизировать наибольшее расстояние от любой точки некоторой сети до ближайшего пункта обслуживания.
|