On the full diversity of balls for graphs.pdf В случае дискретных метрических пространств шары заданного радиуса с центрами в различных вершинах не всегда различны, а могут совпадать. Данный эффект, когда шар имеет несколько центров, наблюдается в графах. О проблеме характериза-ции графов с заданным вектором числа различных шаров можно посмотреть в [1], а о связи свойств структуры шаров в графах и вложениями дискретных метрических пространств - в [2, 3]. Заметим также, что наличие в графе шаров с несколькими центрами позволяет, например, передавать управление с одного центра на другой, оставаясь при этом в зоне контроля или достижимости, определяемой шаром, в случае, например, «отказа» некоторого центра. Постановка подобных вопросов надёжности информационного взаимодействия и обмена данными в пределах заданных областей (окрестностях центров) приводит к задачам исследования взаимосвязей свойств структур или сетей с наличием в них окрестностей с «множественным центром», их числе, возможностей покрытия такими областями всего пространства и т. п. Далее связный конечный граф рассматривается как дискретное метрическое пространство с обычной метрикой пути [4]. Простейший пример графа с отмеченным эффектом даёт так называемый волан. Определение 1 [5]. Граф Vk (u,v), изображённый на рис.1, а, называется воланом на вершинах u, v. Граф G имеет волан, если в G есть подграф Vk(u, v) и degG u = = degG v = k + 1 (рис. 1, б). Рис. 1. Волан Если граф G имеет волан (рис. 1, б), то все шары с различными центрами u, v Е Е V(G) совпадают для любого радиуса i ^ 1 [5]. Пусть Ti(G) -число всех различных шаров радиуса i в метрическом пространстве конечного связного графа G. Определение 2 [6]. Вектор т(G) = (t0(G), t1(G), ..., Td(G)), где d = d(G) -диаметр графа G, называется вектором разнообразия шаров графа G. Определение 3 [7]. Граф G обладает локальным t-разнообразием шаров, если |V(G)| = To(G) = Ti(G) = ... = Tt(G), 0 ^ t < d(G). Граф G с локальным t-разнообра-зием шаров при t = d(G) - 1 называется графом полного разнообразия шаров. Таким образом, вектор разнообразия шаров графа G с полным разнообразием шаров имеет вид (|V(G)|,... , |V(G)|, 1). В настоящей работе изучаются свойства конечных связных обыкновенных (т. е. не имеющих кратных рёбер и петель) графов с полным разнообразием шаров. Теорема 1. Пусть G - граф диаметра d(G) ^ 3 с полным разнообразием шаров. Тогда в графе G либо нет мостов, либо имеется единственный мост, один из концов которого является висячей вершиной. Теорема 2. В классе n-вершинных графов диаметра d существует граф с полным разнообразием шаров тогда и только тогда, когда n ^ 2d > 0 или n = d +1 = 3. Как следствие из найденных свойств получено описание графов с полным разнообразием шаров для кактусов - связных графов, в которых нет рёбер, принадлежащих более чем одному простому циклу. Теорема 3. Цикл и звезда - все с точностью до изоморфизма кактусы с полным разнообразием шаров.

Скачать электронную версию публикации