### Refine

#### Document Type

- Article (2)
- Conference Proceeding (1)

#### Institute

#### Keywords

- Architektur <Informatik> (1)
- CAD (1)
- Computerunterstütztes Verfahren (1)
- Fraktal (1)
- Graphentheorie (1)
- Spannender Baum (1)
- Stabilität (1)
- Vektorfunktion (1)
- Versorgungsnetz (1)

The paper is dedicated to decidability exploration of market segmentation problem with the help of linear convolution algorithms. Mathematical formulation of this problem represents interval task of bipartite graph cover by stars. Vertices of the first partition correspond to types of commodities, vertices of the second – to customers groups. Appropriate method is offered for interval problem reduction to two-criterion task that has one implemented linear convolution algorithm. Unsolvability with the help of linear convolution algorithm of multicriterion, and consequently interval, market segmentation problem is proved.

The idea of representing urban structure and various communication systems (water and energy supply, telephone and cable TV networks) as fractal objects is not absolutely new. However, known works, devoted to this problem use models and approaches from fractal physics. For example, to simulate urban growth Diffusion Limited Aggregation (DLA) model and Dielectric Breakdown (DB) model are used. This study introduces a different approach. Net structure of communication system is described by a graph of special type called regular G(l,r,n)-graph. Authors provide description of such graph, develop iterative process for its generation and prove its self-similarity, i.e. that every regular graph is a pre-fractal. After the infinite number of steps this process generates a fractal. The devised algorithm for generation and grathical representation of regular G(l,r,n)-graphs with different values of l,r and n has been programmed to receive computer simulations. For optimal graphic presentation of pre-fractals the Optimal Space Ordering method was suggested. It is based on the minimization of the >graph energy< value about vertices' coordinates. The effective procedure for optimization was developed that takes into account specific properties of graph energy as objective function For the fractal graph introduced the Hausdorff-Besikovich and similarity dimensions were calculated. It has been shown that >graph energy< is directly related to the graph's fractal properties. For G(3,3,n) and G(4,4,n) graphs fractal dimensions calculated by different methods are the same (D=1,5 and D=2 respectively), while topological dimension of both graphs is 1.

A multicriterial statement of the above mentioned problem is presented. It differes from the classical statement of Spanning Tree problem. The quality of solution is estimated by vector objective function which contains weight criteria as well as topological criteria (degree and diameter of tree). Many real processes are not determined yet. And that is why the investigation of the stability is very important. Many errors are connected with calculations. The stability analysis of vector combinatorial problems allows to discover the value of changes in the initial data for which the optimal solution is not changed. Furthermore, the investigation of the stability allows to construct the class of the problems on base of the one problem by means of the parameter variations. Analysis of the problems with belong to this class allows to obtaine axact and adecuate discription of model