Актуальность темы. Любые сложные системы, такие как информационные, энергетические, управленческие, претерпевают с течением времени определенные, вызванные внешними причинами, изменения. Довольно часто структуры таких систем уместно представлять в виде графа. В работах F. Harari (1973), C. Berge (1962), В.А. Емеличева (1990) и других рассматриваются операции над графами, такие как объединение, соединение, произведение, композиция, стягивание дуги и пр. С помощью этих операций можно описать изменения, происходящие в структурах сложных систем. Структуры систем могут претерпевать как разовые, так и регулярные изменения. Обобщением случая регулярных изменений является понятие структурной динамики.
Общеизвестным сценарием структурной динамики является рост структуры — регулярное появление элементов и связей в структуре системы. В некоторых случаях для описания роста структуры используется перечень правил, причем такие правила могут допускать элемент случайности.
В настоящей работе рассматривается правило, задающее структурную динамику сложных систем. Результатом применения этого правила являются так называемые самоподобные (self-similar graphs) или фрактальные графы.
Фрактальный граф — это сложная абстрактная структура, обладающая свойствами фракталов и «простых» графов. В разных научных школах применяются различные правила построения структурной динамики, что в результате приводит к различным, по строению, самоподобным графам. По данной тематике написано множество статей в российских и зарубежных научных журналах. В статье F.G. Arenas, M.A. Sanchez-Granero (2000) исследуются графы, построенные на множестве точек отрезка [0,1] . В работах
E. Teufl, S. Wagner (2000); B. Kron (2002); B. Kron, E. Teufl (2004);
L. Malozemov, A. Teplyaev (2003); D. D'Angeli, A. Donno (2010) изучаются
свойства графов, каждый из которых состоит из множества изоморфных подграфов, причем последние могут иметь ровно одну общую вершину. Свойства графов, полученных «дискретизацией» фрактальных множеств, описали в своих трудах V. Nekrashevych (2007); D. Guido, T. Isola, M. Lapidus (2009). Самоподобные графы древовидной структуры исследованы в статье
J. Neunhauserer (2007).
Другие способы построения самоподобных графов, а также вопросы практического применения фрактальных множеств рассмотрены в работах
F. Comellas, A. Miralles (2009); C. Lee, P-S. Loh, B. Sudakov (2012);
В.А. Бондаренко, В.Л. Дольникова (1994).
Понятие фрактал, введенное Бенуа Мандельбротом, объединило объекты, обладающие особым свойством — свойством самоподобия (self-similar). Работы, связанные с исследованием фрактальных объектов, фрактальных множеств, долгое время считались интересными, но не имеющими серьезных практических приложений. Мнения в мировой научной среде изменились после издания книги «Фракталы в физике». В настоящее время о перспективности и значимости исследований можно судить по регулярно проводимым конференциям и периодическим изданиям, полностью посвященным соответствующей тематике, и большому количеству книг, учебников и монографий. Это позволяет говорить о сформировавшемся круге прикладных физических задач на основе фрактальных множеств. Среди них выделяются задачи и модели, в которых фрактальные множества представлены как самоподобные, масштабно-инвариантные графы большой размерности, т.е. с большим количеством вершин. К ним относятся, например задачи о броуновском движении, диффузии и просачиваемости. Кроме того, самоподобные графы нередко выступают в качестве моделей структур сложных многоэлементных систем, таких как коммуникационные сети.
Изучение фрактальных графов и их приложений ведется под руководством профессора А.М. Кочкарова. Наиболее активно прорабатываются задачи многокритериальной оптимизации в системах с фрактальной структурой и вопросы выявления свойств и характеристик графов. Метрические свойства исследуются в работах А.М. Кочкарова.
В работе Д.А. Павлова построены оценки метрическим характеристикам предфрактального графа с затравкой простая цепь, в монографии Кочкарова А.А. получены оценки диаметра и радиуса произвольных предфрактальных графов и некоторых классов графов при сохранении смежности старых ребер.
Другим направлением исследования является распознавание фрактальных (предфрактальных) графов. Предфрактальные графы состоят из конечного количества элементов (вершин и ребер), поэтому любая задача распознавания таких графов допускает переборное решение. Для практических задач важен не факт существования алгоритма распознавания, а важно наличие эффективного алгоритма решения поставленной задачи. Наиболее «быстрыми» являются, как известно, полиномиальные алгоритмы. Разработка таких алгоритмов является одной из целей данной работы.
В частности, А.М. Кочкаровым (1998) разработаны полиномиальные алгоритмы распознавания предфрактальных графов с полными затравками, некоторых предфрактальных деревьев, некоторых предфрактальных графов с регулярными затравками. Вопросы распознавания предфрактальных графов также исследуются в работах Е.В. Бобылевой (2005); Е.М. Киселевой, Е.В. Бобылевой (2005); И.Х. Утакаевой (2007); Л.Х. Хапаевой, А.М. Кочкарова (2011).
Цели и задачи исследования.
1. Исследование структуры предфрактальных графов.
2. Выявление свойств и характеристик предфрактальных графов с различными затравками.
3. Разработка алгоритмов распознавания предфрактальных графов.
Купить