Algorithms for local search in the problem of studying invariants of a graph

A. S. Belozerov, B. F. Melnikov, N. P. Churikova

Abstract


The unsolved problem of isomorphism of graphs is directly related to one of seven so-called millenium problems: with the problem of equality of classes P and NP from the theory of algorithms. The reason of this is a lack of a sertificate algorithm for testing two n-vertex graphs for isomorphism.

The quantitative characteristic of the structure of a graph is called a graph invariant. Moreover, an invariant is called complete if the equality of its values for two different graphs means the isomorphism of the graphs under consideration. Currently known complete invariants (for example, the so-called maxi code) are difficult to calculate and do not effectively solve the problem of determining graph isomorphism.

In practice, a simpler procedure is applicable, based on the construction of the canonical code of a graph, independent of the order of the numbering of the vertices. The search for partitions when finding a canonical permutation is significantly reduced when using the automorphism group of the graph.

Algorithmization of the problem of graph generation on the basis of modifying several types of their adjacency matrix and determining some graph invariants according to the criterion of the greatest informativeness made it possible to carry out computational studies. Analysis of the results of experimental calculations revealed the informativeness of the following graph invariants (informative - for the same "differentiation" of graphs): the Wiener index, the determinant of the adjacency matrix and with a smaller degree of informativeness of the diameter. Statistically, a low level of informativeness of such invariants of the graph, as a vector of second-order degrees, the number of connected components, radius, Randic index, is revealed. It seems to be a relevant statistical task for the study of pair correlations for these invariants.

Full Text:

PDF (Russian)

References


Millenium Problems https://claymath.org/millennium-problems

L. Babai Graph isomorphism in quasipolynomial time [Online]. Available: https://arxiv.org/pdf/1512.03547.pdf

László Babai https://en.wikipedia.org/wiki/László_Babai

Kharari F. Graph theory. – М.: Mir, 1973.

B.F. Melnikov, E.F. Saifullina, Primenenie multievristicheskogo podkhoda dlya sluchainoy generatsii grafov s zadannym vektorom stepeney. Izvestiya vysshikh uchebnykh zavedeniy – Povolzhskyi region. Fiziko-matematicheskiye nauki. – 2013. – No. 3(27), pp.70-83.

B.D. McKay Practical graph isomorphism Congressus Numerantium. –1981.– V. 30, pp. 45-87.

B.D. McKay, A. Piperno, Practical graph isomorphism, II. J. Symbolic Computation. –2014.– V. 60, pp. 94-112.

M.I. Volodicheva, S.N. Leora, Issledovanie izomorfozma grafov s pomoschyu zhordanovykh form matritz smezhnosti матриц, PDM.–2018. – No. 40, pp.87-99.

Penrouz Rodzher, Novyi um korolya: O kompyuterakh, myshlenii i zakonakh fiziki: Per. s angl. / Obsch. red. V. O. Malyshenko. – M.: Editorial URSS, 2003. – 384 p.

Kormen, Tomas Kh., Leyzerson, Charlz I., Rivest, Ronald L., Shtayn, Klifford. Algoritmy: postroeniye i analiz, 2-ye izd.: Per. s angl. – M. : Izdatelskyi domд “Vilyams”, 2005.

Gromkovich Yu. Teoreticheskaya informatika. Per. s nem. / Pod red. B. F. Melnikova. - 3-ye izd. - SPb.: BKhV-Peterburg, 2010.

Gardner Martin,Ot mozaik Penrouza k nadyozhnym shifram: Per. S angl. M.: Mir, 1993. – 416 p., il.

R.Gera,S.HedetniemiandC.E.Larson,GraphTheory,FavoriteCon- jectures and Open Problems – 1, Springer International Publishing Switzerland 2016.

Rukovodstvo polzovatelya nauty [Elektronny resurs]: – Rezhim dostu-pa:http://users.cecs.anu.edu.au/~bdm/nauty/nug4b3.pdf(26.10.2018)

B.F. Melnikov, Е.F. Saifullina Generatsiya grafov s zadannym vektorom stepeney vtorogo poryadka i zadacha proverki izomorfizma, Stokhasticheskaya optimizatsiya v informatike. – 2014. – No. 2, pp. 24-36.

N.P. Churikova, O differentsiatsii grafov na osnove bystro vychi-lyayemykh invariantov, Materialy XII Belorusskoy matematicheskoy konferentsii. –2016. – Ch. 4, pp. 67-69.

L. Babai, P. Erdos, S.M. Selkow, Random graph isomorphism, SIAM Journal on Computing. – 1980. – Vol. 9(3). – pp. 628-635

Melnikov B.F., Melnikova Е.А., КKlasterizatsiya situatsii v algoritmakh realnogo vremeni dlya zadach diskretnoy optimizatsii // Sistemy upravleniya i informatsionnye tekhnologii. 2007. Т.28. No. 2, pp. 16-20.

Мelnikov B.F., Saifullina Е.F., Primeneniye multievrsiticheskogo podkhoda dlya sluchainoy generatsii grafa s zadannym vektorom stepeney // Izvestiya vysshikh uchebnykh zavedenii. Povolzhskyi region. Fiziko-matematicheskiye nauki. 2013. No. 3 (27), pp. 70- 83.

Мelnikov B.F., Saifullina Е.F., Тerentyeva Yu.Yu., Churikova N.P., Primeneniye algoritmov generatsii sluchainykh grafov dlya issledovaniya nadyozhnosti setey svyazi // Informatizatsiya i svyaz. 2018. No. 1, pp. 71-80.


Refbacks

  • There are currently no refbacks.


Abava  Кибербезопасность IT Congress 2024

ISSN: 2307-8162