Статья

Название статьи МНОГОКРИТЕРИАЛЬНАЯ ЗАДАЧА РАЗМЕЩЕНИЯ ЦЕНТРА НА М-ВЗВЕШЕННОМ ПРЕДФРАКТАЛЬНОМ ГРАФЕ
Автор Р.А. Кочкаров, А.Н. Кочкарова
Рубрика РАЗДЕЛ IV. ВЫЧИСЛИТЕЛЬНАЯ ТЕХНИКА И ИНФОРМАТИКА
Месяц, год 04, 2015
Индекс УДК 519.1, 519.7
DOI
Аннотация Современные исследования сложных систем таких, как информационные, электро-энергетические, Интернет, коммуникационные системы показывают, что структуры этих систем по истечении времени претерпевает определенные изменения, вызываемые различными внешними обстоятельствами. Структуру системы, произвольной (социальной, социально-экономической, технической, химико-биологической и т.п.) можно представить в виде графа. Граф – это абстрактный объект, как правило, вершины графа соответствуют элементам системы, а ребра – связям между элементами этой системы. Изменения структуры системы могут быть разовыми, а могут быть постоянными. Для второго случая, вводится понятие структурной динамики – изменение структуры системы с течением времени. Несомненно, для описания структурной динамики лучше всего подходит аппарат предфрактальных графов. Одним из наиболее распространенных сценариев структурной динамики является рост структуры. Рост структуры – это регулярное появление новых элементов и связей в структуре системы. Рост структуры может происходит по строго сформулированным правилам, не исключая наличие в них фактора случайности. Рассматривается одно из возможных правил задающих структурную динамику сложных систем. Формальным представлением изменения структур систем по этому правилу являются самоподобные графы большой размерности, называемые фрактальными (предфрактальными). В формулировке задач планирования и проектирования (конструирования) содержатся требования и критерии искомой (оптимальной) конструкции или искомого плана. Зачастую эти критерии и требования являются противоречащими друг другу. Что приводит к появлению многокритериальной постановки оптимизационной задачи. Рассмотрен класс предфрактальных графов и многокритериальная постановка задачи размещения центра на М-взвешенном предфрактальном графе. Рассчитана оценка радиального критерия предфрактальных графов, предложен алгоритм размещения центра предфрактального графа при сохранении смежности старых ребер. Решение задачи может быть применено при в оптимизации размещения авиа и железнодорожных узлов, распределения и маршрутизации потоков, в исследовании распространения инфекционных заболеваний на посевах, в создании информационно-коммуникационных сетей с заданными характеристиками надежности и устойчивости.

Скачать в PDF

Ключевые слова Предфрактальный граф; многокритериальная постановка; М-взвешенный граф; алгоритм размещения центра.
Библиографический список 1. Емеличев В.А., Мельников О.И., Сарванов В.И., Тышкевич Р.И. Лекции по теории графов. – М.: Наука, 1990. – 383 c.
2. Kigami J. Analysis on fractals / Volume 143 of Cambridge Tracts in Mathematics. Cambridge University Press, Cambridge, 2001.
3. Kochkarov A., Perepelitsa V. Fractal Graphs and Their Properties // ICM 1998 Berlin, International Congress of Mathematicians, Abstracts of Short Communications and Posters. – P. 347.
4. Barlow M.T. Diffusions on fractals // Lectures on probability theory and statistics. Springer Verlag, Berlin, 1998. – P. 1-121.
5. Салпагаров С.И., Кочкаров А.М. Распознавание предфрактального графа с полной двудольной затравкой // Деп. ВИНИТИ № 2322-В2003.
6. Перепелица В.А. Многокритериальные модели и методы для задач оптимизации на графах. LAP LAMBERT Academic Publication, 2013. – 330 c.
7. Pareto V. Manuel d’economie politique. – Paris: Giard, 1909.
8. Демидович Б.П., Марон И.А. Основы вычислительной математики. – М.: Наука, 1970. – 664 c.
9. Riehl J., Hespanha J.P. Fractal graph optimization algorithms // Proc. of the 44th Conf. on Decision and Contr., 2005. – P. 2188-2193.
10. Кочкаров А.А., Салпагаров С.И., Кочкаров Р.А. О количественных оценках топологических характеристик предфрактальных графов // Известия ЮФУ. Технические науки. – 2004. – № 8 (43). – С. 298-301.
11. Ehrgott M., Gandibleux X. A survey and annotated bibliography of multiobjective combinatorial optimization // OR Spektrum, 2000. – № 22. – P. 425-460.
12. Krцn B. Green functions on self-similar graphs and bounds for the spectrum of the Laplacian // Ann. Inst. Fourier (Grenoble). – 2002. – No. 52(6). – P. 1875-1900.
13. Dorogovtsev S.N., Mendes J.F.F. Evolution of networks: From Biological Nets to the Internet and WWW. – Oxford: Oxford University Press, 2003.
14. Albert R., Barabasi A. Statistical mechanics of complex networks // Reviews of Modern Physics. – 2002. – No. 74. – P. 47-97.
15. Bollt E.M., ben-Avraham D. What is Special about Diffusion on Scale-Free Nets? // New J. Phys. – 2005. – Vol. 7, No. 26. – P. 1-21.

Comments are closed.