Теорема про випадкові перестановки та деякі її застосування

Abstract

Розглянуто метод випадкових перестановок та його застосування до теорії графів та структурного аналізу складних дискретних систем. Запропоновано метод перестановоч ної склейки двох графів, який дозволяє будувати графи з даними зв' язнісними власти востями, що, у свою чергу, надає можливість конструювати складні дискретні системи з необхідними структурними властивостями.

In the study of the structural properties of complex discrete systems, graph theory is widely used. Thus, to assess the ability of a system to retain certain structural properties when break ing the relationships between its elements, it is important to study different types of connectivi ty of the graph and their generalizations. Of particular interest is the question of how likely it is that a given graph will remain connected or have a sufficiently large connected component when a certain number of its edges are removed? In this paper, the theorem on random permu tations is proved and a number of its applications in graph theory are considered. The operation of "permutation gluing of graphs" is introduced. It is shown how with the help of such gluing of two given graphs of a rather simple structure it is possible to construct graphs which with sufficient probability have the necessary connected properties. In particular, the constructions are described, which with a given probability allow to build expanders as well as graphs of greater connectivity. This approach allows you to synthesize graphs with certain properties as a result of some stochastic process followed by selection.