Диаметр и радиус взвешенного предфрактального графа, порожденного полной двудольной затравкой

Размещено на http://www.allbest.ru/

УДК 519.1

01.00.00 Физико-математические науки

Департамент анализа данных, принятия решений и финансовых технологий Финансового университета при Правительстве РФ,

ДИАМЕТР И РАДИУС ВЗВЕШЕННОГО ПРЕДФРАКТАЛЬНОГО ГРАФА, ПОРОЖДЕННОГО ПОЛНОЙ ДВУДОЛЬНОЙ ЗАТРАВКОЙ

Кочкаров А.А.

Москва, Россия

Исследование выполнено при финансовой поддержке РФФИ в рамках научного проекта № 16 - 07 - 00231а.

Исследования метрических [1] характеристик на предфрактальных [2-5] графах являются известными графовыми задачами. Такого рода задачи возникают при определении оценок длины, глубины, ширины графа [6,7]. Также эти вопросы возникают при определении результатов оптимизационных задач на предфрактальных графах [9]. Свойства метрических характеристик зависят от траектории [2,8] порождения предфрактального графа и от характеристики затравок.

Значительная часть структурных и топологических характеристик «невзвешенных» предфрактальных графов отражены в работах [3-5].

Взвешенные графы уже давно составляют фундаментальную основу для моделирования экономических процессов [9] и формализации многокритериальных задач дискретной оптимизации [9,10].

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

Пусть есть - вершинный связный граф [6,7]. Длина кратчайшей цепи, соединяющей пару вершин , называется расстоянием между вершинами [1] и обозначается через . Заметим, что введенное таким образом расстояние удовлетворяет известным аксиомам Евклидовой метрики.

Для фиксированной вершины величина называется эксцентриситетом вершины .

Максимальный среди всех эксцентриситетов вершин графа называется диаметром [1] графа и обозначается через , т.е. .

Если пара вершин соединяется кратчайшей цепью длины , то эта цепь называется диаметральной.

Радиус графа обозначается через и вычисляется по формуле .

Вершина называется периферийной, если .

Пусть дан взвешенный предфрактальный граф [2,5] ранга , который порожден двудольной затравкой , причем берется взвешенная подграф-затравка. При замещении вершин на затравке на шаге траектории построения предфрактального графа веса меняются последовательно по шагам следующим образом. Ребрам предфрактального графа ранга , , приписаны веса , где ранг ребра, и - коэффициент пропорциональности, влияющий на изменение веса ребра (коэффициент масштабирования) и каждой вершине приписан вес . где ранг ребра и .

Доказаны следующие утверждения.

Теорема 1. Для всякого взвешенного предфрактального графа

, , порожденного полной двудольной взвешенной n-вершинной затравкой , , смежность старых ребер которого в траектории не нарушается, величина диаметра удовлетворяет условию:

где - диаметр затравки , -коэффициент масштабирования.

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

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

Сначала подграф -затравка первого ранга склеивается в каждой своей вершине с подграф-затравками второго ранга, . Далее, каждый порожденный таким образом на - м, , шаге предфрактальный граф склеивается в каждой своей вершине с подграф-затравками . В итоге на l - м, , шаге получаем предфрактальный граф, порожденный полной двудольной затравкой , смежность старых ребер которого не нарушается. Заметим, что при переходе от - графа к - графу вес ребра затравки изменяется в раз, где - коэффициент масштабирования [2], так как , то .

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

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

Через обозначим кратчайшую цепь, соединяющую выделенную пару вершин q,u . Длина этой цепи в графе равна суммарному весу ребер в маршруте. Обозначим длину цепи через . Все цепи, в том числе и кратчайшие, соединяющие вершины двух смежных подграф- затравок, «проходят» через вершину, по средствам которой и обеспечивается их смежность. Это вершина, в которой были склеены подграф-затравки.

Рассмотрим несколько случаев взаимного расположения вершин на предфрактальном графе .

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

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

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

Рассмотрим случай, когда вершины предфрактального графа

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

Заметим, что при переходе от - графа к - графу вес ребра затравки изменяется в раз, где - коэффициент масштабирования [2], так как , то .

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

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

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

Тогда с учетом (2), (3) и (4) длина цепи удовлетворяет условию:

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

Таким образом, длина цепи равна:

При переходе от графа к графу веса ребер подграф-затравок , , l-го ранга изменяются в раз по отношению к весам ребер подграф-затравок l-1 -го ранга, а значит изменяются в раз по отношению к весам ребер l-2-го ранга, а значит в раз по отношению к весам ребер подграф-затравки , причем диаметральная цепь подграф- затравки будет иметь наибольшую длину, равную , тогда длины ,… цепей,,… удовлетворяют условиям:

, , …

С учетом (5), (6) длина , , цепи , , удовлетворяет условию:

Цепь , , наибольшей длины будет диаметральной цепью на графе

, . Длина диаметральной цепи равна диаметру предфрактального графа , . Тогда с учетом (7), диаметр ,

, предфрактального графа , , удовлетворяет условию:

Теорема 1 доказана.

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

где радиус затравки , -коэффициент масштабирования.

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

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

Напомним, что для взвешенного предфрактального графа ,, под расстоянием между вершинами будем понимать суммарный вес ребер кратчайшей цепи, соединяющей вершины u, v. Любая цепь, соединяющая вершины и состоящая из отрезков, целиком принадлежащих тем или иным подграф-затравкам предфрактального графа является кратчайшей, если каждый отрезок, из которых она состоит, также является кратчайшим среди всех возможных цепей, соединяющих ее концы. Тогда длина цепи , т.е. расстояние между вершинами и , будет меньше либо равна эксцентриситету вершины , то есть . Если же цепь является частью диаметральной цепи предфрактального графа ,, то ее длина может быть равна эксцентриситету .

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

Напомним, что при переходе от графа к графу веса ребер подграф-затравок , , l-го ранга изменяются в раз по отношению к весам ребер подграф-затравок l-1 -го ранга, а значит изменяются в раз по отношению к весам ребер l-2-го ранга, а значит в раз по отношению к весам ребер подграф-затравки .

Тогда если вершина принадлежит подграф-затравке первого ранга , то расстояние от вершины u до периферийной вершины v будет удовлетворять условию:

где радиус затравки .

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

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

Теорема 2 доказана.

Используя теоремы 1, 2 получены следующие оценки для диаметра и радиуса взвешенного фрактального графа.

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

где - диаметр затравки , -коэффициент масштабирования.

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

где радиус затравки , -коэффициент масштабирования.

Список литературы

1. Лекции по теории графов: учебник / В.А. Емеличев, О.И. Мельников, В.И. Сарванов, Р.И. Тышкевич. - М.: Наука, 1990. - 392с.

2. Кочкаров А.М. Распознавание фрактальных графов. Алгоритмический подход. Нижний Архыз: РАН САО, 1998.

3. Кочкаров А.А. О планарности и других топологических свойствах фрактальных графов. / А.А. Кочкаров, Р.А. Кочкаров. // Препринт. - М.: ИПМ им. М.В. Келдыша РАН, - 2003. - №83. - С. 10-13.

4. Павлов Д.А. Нахождение диаметральной простой цепи на фрактальном и предфрактальном графах / Д.А. Павлов // Математические методы в технике и технологиях: сборник трудов XVI Международной научной конференции. - С.- Пб.: СПбГТИ, 2004-. С. 115-117.

5. Кочкаров А.А. Топологические характеристики предфрактальных графов и предупреждение кризисов сложных систем. / А.А. Кочкаров, Р.А. Кочкаров // Проблемы управления безопасностью сложных систем: труды X Международной конференции Часть 1. - Москва: РГГУ, 2002. - С. 116 - 119.

6. Оре О. Теория графов: учебник / О. Оре М.: Наука, 1968. -352с.

7. Харари Ф. Теория графов. / Ф. Харари. - М.: Мир, 1973. - 300с.

8. Кочкаров А.А. Структурная динамика: свойства и количественные характеристики предфракальных графов: монография / А.А. Кочкаров. - М.: Вега: Инфо, 2012. - 120с.

9. Кочкаров Р.А. Целевые программы: инструментальная поддержка: книга / Р.А. Кочкаров. - М.:Экономика, 2007. -222с.

Аннотация

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

Ключевые слова: ГРАФ, ПРЕДФРАКТАЛЬНЫЙ ГРАФ, ВЗВЕШЕННЫЙ ГРАФ, РАДИУС И ДИАМЕТР ГРАФА, ЗАТРАВКА

Researches of metric characteristics on prefractal graphs are known tasks. Such tasks arise when determining estimates of length, of depth, of width of the graph. Also these questions arise when determining results of optimization of these tasks of the prefractal graphs. Properties of metric characteristics depend on a trajectory of generation of the prefractal graph and on the characteristic of primings. In this work, metric characteristics on prefractal weighed graphs are investigated, dependence of metric characteristics on a trajectory of a priming and prefractal graphs is revealed.

Estimates are obtained for the diameter and radius of the weighted prefractal and fractal graphss

Keywords: COUNT, PREFRACTAL GRAPH, WEIGHTED GRAPH, RADIUS AND DIAMETER OF THE GRAPH, SEED.

Размещено на Allbest.ru