Диссертация (1143658), страница 9

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

Текст из файла (страница 9)

Пусть имеется граф-затравка H. Выделим ребро q1 иприменим операцию B с образованием вершины e1 (рис. 3.2а). Выделим ребро q2и применим операцию B с образованием вершины e2, связав ее так же с e1 (рис.3.2б). Наконец, выделим ребро q3 и применим операцию B с образованиемвершины e3 связав ее так же с e1 и e2 (рис. 3.2в).Из рисунка видно, чтопроведенные действия эквивалентны операции ЗВЗ над левой верхней вершинойH.А)e1Б)e1e2В)e1e3e2Рисунок 3.2 – Операция ЗВЗ с использованием разбиения ребраТаким образом, существует два способа проведения ЗВЗ без явногоудаления вершины. Существенным различием двух приведенных способовявляется то, что, применяя ЗВЗ(А) инициирован рост предфрактального графа«наружу», а при использовании ЗВЗ(В) граф растет «внутрь».С точки зрения формального описания графов эти различия можно описатьследующим образом: если после ЗВЗ у вершин первоначального графа не61изменились степени связности, то граф вырос «внутрь», иначе – граф вырос«наружу».При использовании операции В необходимо учитывать важный момент –какое именно ребро разбивается.

Пусть дан граф, приведенный на рисунке 3.3, иразбивается ребро BE.Рисунок 3.3 – Исходный графТогда, далее необходимо разбить ребра DF, CG и образовать новые ребратак, чтобы граф соответствовал затравке (полносвязный квадрат). Получитсяслучай, изображенный на рисунке 3.4.Рисунок 3.4 – Исходный граф после выполнения операций подразбиения реберМожно увидеть, что для графа ABCD произошел случай, аналогичный ЗВЗс операцией А, но если рассматривать весь граф целиком, то произошел случай,аналогичный ЗВЗ с операцией B. Таким образом понятия роста «внутрь» и«наружу» относительны.

Тем не менее, в данном случае корректнее говорить о62росте «внутрь», т.к. выполняется основное условие: ни одна «старая» вершина неизменила показатель связности.3.1.2Разработка подхода к адресации вершин предфрактальныхграфов на основе принципа самоподобияВ рамках исследования рассматриваются только предфрактальные графы отполносвязных затравок, однако описанная ниже система адресации применима кпредфрактальным графам от любой затравки.Идея адресации (индексации) предфрактальных графов состоит ввозможностиприсвоениякаждойвершинезатравкиуникальногоадреса(идентификатора); далее, используя свойство самоподобия фрактальных графов,возможно присвоить каждому подграфу-затравке предфрактального графа второгопорядка те же идентификаторы; используя предфрактактальный граф второгопорядка как новую затравку мы можем присвоить идентификаторы подграфампредфрактального графа следующего порядка фрактальности и так далее.

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

Согласно принципу построения предфрактальных графов,можно мысленно стянуть все четыре подграфа затравки в четыре вершины ипроиндексировать их аналогичным образом (рисунок 3.6).Рисунок 3.6 – Предфрактальный граф второго порядкаВ результате добавления слева к индексу каждой вершины подграфа индексвсего подграфа с рисунка 6 получим проиндексированный граф, изображенный нарисунке 3.7.64Рисунок 3.7 – Проиндексированный предфрактальный граф второго порядкаЕсли теперь взять еще три таких же графа и образовать предфрактальныйграф третьего порядка, то можно проделать все то же самое и получить такую жесистему индексов, только размер индекса увеличится на символ, а количествоиндексов возрастет вчетверо.Рассмотренный случай является частным.

При выполнении операции ЗВЗграф не обязательно увеличивает порядок фрактальности. Тем не менее в такомслучае система индексации тоже работает, но необходимо ввести дополнительныйидентификатор «0», который будет означать, что более данная вершинараскрываться в подграф-затравку не будет. На основе этого можно дать новоеопределение фрактального графа:Фрактальный граф – это самоподобный граф, в котором индексы вершин несодержат идентификатора «0» и содержат в индексе бесконечное число разрядов.Это означает, что данный узел всегда можно развернуть в подграф-затравку.И сразу можно ввести правило: после идентификатора «0» в индексе неможет быть других идентификаторов кроме таких же «0».

При этом, стоитоговорить, что «после» в данном случае означает «справа от».Введем так же оперделение:Идеальный предфрактальный граф n-го порядка – это предфрактальныйграф, в котором число подграфов-затравок равно kn-1, где k – число вершин взатравке.65При этом если стянуть все подграфы-затравки в узлы, то получитсяидеальный предфрактальный граф (n-1)-го порядка.Теперь можно сказать, что рассмотренный выше случай индексации(рисунок 7) – это индексация идеального предфрактального графа. Рассмотримслучай, когда граф не идеальный.Допустим, имеется граф, аналогичный приведенному на рисунке 6, но снебольшими изменениями (рисунок 3.8):Рисунок 3.8 – Исходный графОчевидно, на уровне «синего» графа-затравки, система индексов действует,однако если перейти на уровень «черного» - т.е. перейти ко второму порядкуфрактальности, то возникают трудности.

Для начала проиндексируем все вершины,кроме той, что находится в правом верхнем углу (рисунок 3.9).Рисунок 3.9 – Частично проиндексированный граф66Учитывая предыдущие рассуждения, первым идентификатором в индексеоставшейся вершины должно быть “b”. А далее воспользуемся введенным нулем.Нуль в индексе означает, что более вершина в подграф не раскрывается – здесьименно такой случай.

Значит, индекс оставшейся вершины – «b0» (рисунок 3.10).Рисунок 3.10 – Результат индексации графаЕсли рассматривать предфрактальный граф первого порядка, т.е. затравку,то каждая вершина (подграф стянутый в вершину) будет иметь свой индекс,согласно нашей системе; при переходе к рассмотрению предфрактального графавторого порядка, аналогично, каждый узел будет содержать двузначный индекс, ив случае с вершиной b0, подразумевается, что данная вершина вписывается вофрактальный граф, но в переходе к следующему (следующим) порядкуфрактальности не участвует. Тем не менее, на рисунке 10 изображена затравка, ккоторой трижды применили ЗВЗ, а значит, по определению в [1] наш граф являетсяпредфрактальным.Еще один пример индексации приведен на рисунке 3.11.67Рисунок 3.11 – Проиндексированный неидеальный предфрактальный граф3.1.3Разработка алгоритма маршрутизации для предфрактальныхграфовВ данном разделе описывается принцип маршрутизации в графах спредфрактальной топологией, для которых выполняются следующие условия:1) Используемая затравка является полносвязным графом;2) Минимальное число инцидентных ребер для вершины равно (k – 1), амаксимальное – k, где k – Число вершин в графе-затравке.Предфрактальные графы, построенные и проиндексированные согласноправилам описанным ранее обладают рядом полезных свойств.Первым свойством является то, что каждый подграф определенного порядкаимеет ровно одну связь с каждым подграфом (сегментом) того же порядка.Вторымсвойствомявляетсято,чтоиндексугловойвершиныпредфрактального графа n-го порядка всегда имеет вид «aaa…», «bbb…», «ccc…»68или «ddd…», а количество разрядов в индексе совпадает с порядком фрактальностиn.

При этом угловые вершины графов n-1-го порядка имеют вид:«aaa…», «abb…», «acc…», «add…»;«baa…», «bbb…», «bcc…», «bdd…»;«caa…», «cbb…», «ccc…», «cdd…»;«daa…», «dbb…», «dcc…», «ddd…»;При этом, связаны друг с другом напрямую следующие вершины:«abb…» и «baa…»;«acc…» и «caa…»;«add…» и «daa…»;«bcc…» и «cbb…»;«bdd…» и «dbb…»;«cdd…» и «dcc…».Другим свойством является то, что если имеется связь между подграфамизатравками, то положение, которое занимает каждый из связующих узлов в своемподграфе-затравке совпадает c положением второго подграфа-затравки в графеследующего порядка фрактальности (рисунок 3.12). Другими словами, последнийразряд индекса одного связующего узла будет равен первому разряду индексавторого связующего узла.

Это утверждение верно не только для соседнихподграфов-затравок, но и для подграфов-соседей любого другого порядка.Формально это утверждение можно описать с использованием индексов:Если имеется связь между подграфами-затравками, то каждый узел, имеяиндекс «*XY» всегда имеет связь с узлом, индекс которого «*YX».Учитывая второе и первое правила, мы можем дополнить сказанное выше:Каждый узел, имея индекс «*XY» всегда имеет связь со всеми узлами синдексами «*Х?» и, если у него имеется связь с другим подграфом-затравкой, тоон связан с узлом «*YX», либо «*Y0». Назовем это правилом преобразованияиндекса.69aaabbaaacbaddacacdРисунок 3.12 – Проиндексированный граф второго порядка фрактальностиПод метрикой принимаются ребра, т.е. расстояние между вершинами А и Вравно числу пройденных ребер от А до В.Учитывая, что максимально близкие вершины в графе – это смежныевершины, и быть ближе, чем смежными, вершины не могут, то минимальновозможное расстояние между двумя вершинами равно 1.

Характеристики

Список файлов диссертации