Scientific journal
Bulletin of Higher Educational Institutions
North Caucasus region

TECHNICAL SCIENCES


UNIV. NEWS. NORTH-CAUCAS. REG. TECHNICAL SCIENCES SERIES. 2022; 3: 5-10

 

http://dx.doi.org/10.17213/1560-3644-2022-3-5-10

 

EXPERIMENTAL RESEARCH OF VARIOUS CHARACTERISTICS OF A SYMMETRIC GRAPH USING KERNELS OBTAINED USING THE MAGHOUT METHOD

Kobak V.G., Troshchy V.S.

Kobak Valeriy G. – Doctor of Technical Sciences, Professor, Department «The Software of Computer Facilities and Automated Systems», valera33305@mail.ru

Troshchy Vladislav S. Student, Department «The Software of Computer Facilities and Automated Systems».

 

Abstract

The problem of finding kernels of a graph using the Magoo method is considered, which is characterized by the fact that for graphs of small dimension it is possible to obtain the entire set of kernels. This problem of finding graph kernels belongs to the class of NP-complete problems (from the English non-deterministic polynomial - “non-deterministic with polynomial time”) - this is a class of computational problems for which an effective solution algorithm has not been found. In this paper, an example of solving the problem for a directed graph consisting of six vertices is given in detail, however, the Magu method is used in research for symmetric graphs. For such graphs, there is a theorem: that the number of elements of a subset of any of the cores of the graph is always less than or equal to the number of vertices of the largest of the internally stable subsets, and greater than or equal to the number of vertices of the smallest of the externally stable subsets. In the work, a computational experiment with a theorem related to the properties of kernels was carried out in order to determine other characteristics of a symmetric graph using the developed software. The results obtained in this work are presented for clarity in the form of tables and histograms.

 

Keywords: graph problems, graph kernel, NP-complete problem, search for graph kernels, Maghout method, externally stable set, internally stable set, theorem IV

 

Full text: [in elibrary.ru]

 

References

  1. Application of graph theory Available at: https://www.sites.google.com/a/labore.ru/teoria-grafov-i-ee-primenenie/integracionnaa-svaz (accessed 13.05.2022).
  2. Domracheev R. Y., Efimov S.S. Parallel implementation of the search for graph kernels. Bulletin of Omsk State University. 2011; (2):159-166 (In Russ.).
  3. NP-complete task. Available at: https://www.britannica.com/science/NP-complete-problem (accessed 14.05.2022).
  4. NP-complete tasks. Available at: https://alexeykalina.github.io/technologies/np-completeness.html (accessed 14.05.2022).
  5. Boolean matrices and operations on them. Available at: https://studfile.net/preview/1587941/page:19 / (accessed 19.05.2022).
  6. Kofman A. Introduction to Applied combinatorics. Moscow: Nauka; 1975. 481 p.
  7. Prokushev L.A. P80 Discrete Mathematics (fundamentals of graph theory and algorithmization of problems); Textbook. SPbSUAP. St. Petersburg; 2000. 82 p.
  8. The Magu method for finding externally stable sets. Available at:  https://studfile.net/preview/9491821/page:6/ (accessed 17.05.2022).
  9. The numbers of internal and external stability of the graph. Available at:  https://lektsii.org/17-62407.html (accessed 17.05.2022).
  10. Magu algorithm for determining the set of external stability. Available at:  https://studfile.net/preview/952540/page:13/(accessed 22.05.2022).