|Article title||MULTICRITERIA PROBLEM OF LOCATION CENTER ON M-WEIGHTED PREFRACTAL GRAPH|
|Authors||R.A. Kochkarov, A.N. Kochkarova|
|Section||SECTION IV. COMPUTER ENGINEERING AND COMPUTER SCIENCE|
|Month, Year||04, 2015 @en|
|Index UDC||519.1, 519.7|
|Abstract||Modern studies of complex systems such as informational, electrical, Internet, communication systems show that the structure of these systems after the time undergoes certain changes caused by various external circumstances. Structure of the system, an arbitrary (social, socio- economic, technical, chemical, biological, etc.) can be represented as a graph. Graph is an abstract object, as a rule vertexes of graphs correspond to elements of the system, and the edges - relations between the elements of the system. Changes in the structure of the system can be single, and may be permanent. For the second case, we introduce the notion of structural dynamics - changes in the structure of the system over time. Undoubtedly, for the description of structural dynamics is best suited machine prefractal graphs. The growth of structure is one of the most common scripts of structural dynamics is. The growth of structure is a regular appearance of new elements and ties in the structure of the system. The growth of structure can occur on a strictly formulated rules, not excluding the presence of the factor of chance. In this paper, we consider one of the possible rules defining the structural dynamics of complex systems. Formal representation structures change systems according to this rule are self-similar large-scale graphs, called fractal (prefractal). In the formulation of the problems of planning and designing (design constructional) contains requirements and criteria required (optimal) construction or the desired plan. Often these criteria and requirements are contradictory. This leads to staging multicriteria optimization problem. Class of prefractal graphs and multicriteria problem of location center on M-weighted prefractal graph are discussed in the paper. Evaluation radial criterion of prefractal graphs are calculated, algorithm for location center on prefractal graph while preserving contiguity old edgesare proposed. Solution of the problem can be applied by optimizing the placement of air and railway nodes, distributing and routing of streams in the study of infectious diseases of crops in the creation of informational and communicational networks with specified characteristics of reliability and stability.|
|Keywords||Prefractal graph; multicriteria formulation; M-weighted graph; algorithm for location center.|
|References||1. Emelichev V.A., Mel'nikov O.I., Sarvanov V.I., Tyshkevich R.I. Lektsii po teorii grafov [Lectures on graph theory]. Moscow: Nauka, 1990, 383 p.
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, pp. 347.
4. Barlow M.T. Diffusions on fractals, Lectures on probability theory and statistics. Springer Verlag, Berlin, 1998, pp. 1-121.
5. Salpagarov S.I., Kochkarov A.M. Raspoznavanie predfraktal'nogo grafa s polnoy dvudol'noy zatravkoy [Recognition of prefractal graphs with complete bipartite seed], Dep. VINITI No. 2322-V2003.
6. Perepelitsa V.A. Mnogokriterial'nye modeli i metody dlya zadach optimizatsii na grafakh [Multicriteria models and methods for optimization problems on graphs]. LAP LAMBERT Academic Publication, 2013, 330 p.
7. Pareto V. Manuel d’economie politique. Paris: Giard, 1909.
8. Demidovich B.P., Maron I.A. Osnovy vychislitel'noy matematiki [Foundations of computational mathematics]. Moscow: Nauka, 1970, 664 p.
9. Riehl J., Hespanha J.P. Fractal graph optimization algorithms, Proc. of the 44th Conf. on Decision and Contr., 2005, pp. 2188-2193.
10. Kochkarov A.A., Salpagarov S.I., Kochkarov R.A. O kolichestvennykh otsenkakh topologicheskikh kharakteristik predfraktal'nykh grafov [Quantitative estimates of topological characteristics of prefractal graphs], Izvestiya YuFU. Tekhnicheskie nauki [Izvestiya SFedU. Engineering Sciences], 2004, No. 8 (43), pp. 298-301.
11. Ehrgott M., Gandibleux X. A survey and annotated bibliography of multiobjective combinatorial optimization, OR Spektrum, 2000, No. 22, pp. 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), pp. 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, pp. 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, pp. 1-21.