Details

Работа посвящена разработке алгоритма проверки графов на свойства минимальности, минимальности по стягиванию и k-связности. Цель работы — поиск минимальных и минимальных по стягиванию k-связных графов. Настоящая выпускная квалификационная работа содержит обзор существующих результатов исследований рассматриваемых графов, методов проверки на k-связность и вспомогательных методов. Исходя из рассмотренных данных, предложен алгоритм проверки входящих графов на свойства минимальности, минимальности по стягиванию и k-связности, а также поиск графов, обладающих такими свойствами внутри заданного на вход графа. Результатом работы является программа, реализующая алгоритм проверки графов на свойства k-связности, минимальности и минимальности по стягиванию, алгоритм поиска графов, обладающих предыдущими свойствами.

The work is devoted to the development of an algorithm for checking graphs for the properties of minimality, minimality in contraction and k-connectivity. The work is devoted to the development of an algorithm for checking graphs for the properties of minimality, minimality in contraction and k-connectivity. The purpose of this work is to find minimal and minimal contraction k-connected graphs. This final qualifying work contains an overview of existing research results of the considered graphs, k-connectivity verification methods and auxiliary methods. Based on considered data, an algorithm is proposed for checking incoming graphs for properties of minimality, contraction minimality and k-connectivity, as well as for searching for graphs with such properties inside the graph given at the input. The result of the work is a program that implements an algorithm for checking graphs for the properties of k-connectivity, minimality and contraction minimality, an algorithm for finding graphs with the previous properties.