maisМоделирование и анализ информационных системModeling and Analysis of Information Systems1818-10152313-5417Yaroslavl State University10.18255/1818-1015-2018-4-388-401mais-731Research ArticleОригинальные статьиArticlesОстовное дерево в делимом кратном графеThe Spanning Tree of a Divisible Multiple Graphhttps://orcid.org/0000-0002-0980-2507СмирновАлександр ВалерьевичSmirnovAlexander V.

канд. физ.-мат. наук, доцент

PhD, Associate Professor

alexander_sm@mail.ruЯрославский государственный университет им. П.Г. ДемидоваРоссияP.G. Demidov Yaroslavl State UniversityRussian Federation201827082018254388401Copyright © Смирнов А.В., 20182018Смирнов А.В.Smirnov A.V.Данная работа распространяется под лицензией Creative Commons Attribution 4.0.This work is licensed under a Creative Commons Attribution 4.0 License.https://www.mais-journal.ru/jour/article/view/731

В статье рассматриваются неориентированные кратные графы произвольной натуральной кратности k > 1. Кратный граф содержит ребра трех типов: обычные, кратные и мультиребра. Ребра последних двух типов представляют собой объединение k связанных ребер, которые соединяют 2 или k + 1 вершину соответственно. Связанные ребра могут использоваться только согласованно. Если вершина инцидентна кратному ребру, то она может быть инцидентна другим кратным ребрам, а также она может быть общим концом k связанных ребер мультиребра. Если вершина является общим концом мультиребра, то она не может быть общим концом никакого другого мультиребра. Особое внимание уделяется классу делимых кратных графов, которые отличаются возможностью выделения k частей, согласованных на всех связанных ребрах и не содержащих общих ребер. Каждая из частей является обычным графом. Вводится понятие кратного дерева, определяюся его основные свойства. В отличие от обычных деревьев количество ребер в кратных деревьях не фиксировано. Для делимых деревьев в работе приводится и обосновывается оценка минимального и максимального количества ребер. Далее определяются понятия остовного дерева и полного остовного дерева. Для делимых графов доказывается критерий полноты остовного дерева. Также доказано, что полное остовное дерево всегда существует в делимом графе. Если кратный граф является взвешенным, то для него можно поставить задачу о минимальном остовном дереве, а также о минимальном полном остовном дереве. В работе предложен эвристический алгоритм поиска минимального полного остовного дерева в делимом графе.

In this paper, we study undirected multiple graphs of any natural multiplicity k > 1. There are edges of three types: ordinary edges, multiple edges and multi-edges. Each edge of the last two types is a union of k linked edges, which connect 2 or k + 1 vertices, correspondingly. The linked edges should be used simultaneously. If a vertex is incident to a multiple edge, it can be also incident to other multiple edges, and it can be the common ending vertex to k linked edges of a multi-edge. If a vertex is the common end of some multi-edge, it cannot be the common end of any other multi-edge. Special attention is paid to the class of divisible multiple graphs. The main peculiarity of them is a possibility to divide the graph into k parts, which are adjusted on the linked edges and which have no common edges. Each part is an ordinary graph. The definition of a multiple tree is stated and the basic properties of such trees are studied. Unlike ordinary trees, the number of edges in a multiple tree is not fixed. In the article, the evaluation of the minimum and maximum number of edges in the divisible tree is stated and proved. Next, the definitions of the spanning tree and the complete spanning tree of a multiple graph are given. The criterion of completeness of the spanning tree is proved for divisible graphs. It is also proved that a complete spanning tree exists in any divisible graph. If the multiple graph is weighted, the minimum spanning tree problem and the minimum complete spanning tree problem can be set. In the article, we suggest a heuristic algorithm for the minimum complete spanning tree problem for a divisible graph.

кратный графкратное дереводелимый графостовное деревополное остовное деревоминимальное остовное деревоmultiple graphmultiple treedivisible graphspanning treecomplete spanning treeminimum spanning treeРабота выполнена при поддержке Российского фонда фундаментальных исследований (проект № 17-07-00823 А)This work was supported by the Russian Foundation for Basic Research under the Grant No 17-07-00823 AReferencesСмирнов А. В., “Задача о кратчайшем пути в кратном графе”, Моделирование и анализ информационных систем, 24:6 (2017), 466–478;Smirnov A. V., “The Shortest Path Problem for a Multiple Graph”, Modeling and Analysis of Information Systems, 24:6 (2017), 788–801, (in Russian).Cormen T. H., Leiserson C. E., Rivest R. L., Stein C., Introduction to Algorithms, 3rd ed., The MIT Press, McGraw-Hill Book Company, 2009.Cormen T. H., Leiserson C. E., Rivest R. L., Stein C., Introduction to Algorithms, 3rd ed., The MIT Press, McGraw-Hill Book Company, 2009.Berge C., Graphs and Hypergraphs, North-Holland Publishing Company, 1973.Berge C., Graphs and Hypergraphs, North-Holland Publishing Company, 1973.Basu A., Blanning R.W., “Metagraphs in workflow support systems”, Decision Support Systems, 25:3 (1999), 199–208.Basu A., Blanning R.W., “Metagraphs in workflow support systems”, Decision Support Systems, 25:3 (1999), 199–208.Basu A., Blanning R.W., Metagraphs and Their Applications, Integrated Series in Information Systems, 15, Springer US, 2007.Basu A., Blanning R.W., Metagraphs and Their Applications, Integrated Series in Information Systems, 15, Springer US, 2007.Рублев В. С., Смирнов А. В., “Потоки в кратных сетях”, Ярославский педагогический вестник, 3:2 (2011), 60–68Rublev V. S., Smirnov A. V., “Flows in Multiple Networks”, Yaroslavsky Pedagogichesky Vestnik, 3:2 (2011), 60–68, (in Russian).Smirnov A. V., “The Problem of Finding the Maximum Multiple Flow in the Divisible Network and its Special Cases”, Automatic Control and Computer Sciences, 50:7 (2016), 527–535.Smirnov A. V., “The Problem of Finding the Maximum Multiple Flow in the Divisible Network and its Special Cases”, Automatic Control and Computer Sciences, 50:7 (2016), 527–535.Ford L. R., Fulkerson D. R., Flows in Networks, Princeton University Press, 1962.Ford L. R., Fulkerson D. R., Flows in Networks, Princeton University Press, 1962.Рублев В. С., Смирнов А. В., “Задача целочисленного сбалансирования трехмерной матрицы и алгоритмы ее решения”, Моделирование и анализ информационных систем, 17:2 (2010), 72–98;Roublev V. S., Smirnov A. V., “The Problem of Integer-Valued Balancing of a Three-Dimensional Matrix and Algorithms of Its Solution”, Modeling and Analysis of Information Systems, 17:2 (2010), 72–98, (in Russian).Smirnov A. V., “Network Model for the Problem of Integer Balancing of a Four-Dimensional Matrix”, Automatic Control and Computer Sciences, 51:7 (2017), 558–566.Smirnov A. V., “Network Model for the Problem of Integer Balancing of a Four-Dimensional Matrix”, Automatic Control and Computer Sciences, 51:7 (2017), 558–566.Kruskal J. B., “On the Shortest Spanning Subtree of a Graph and the Traveling Salesman Problem”, Proceedings of the American Mathematical Society, 7:1 (1956), 48–50.Kruskal J. B., “On the Shortest Spanning Subtree of a Graph and the Traveling Salesman Problem”, Proceedings of the American Mathematical Society, 7:1 (1956), 48–50.

The authors declare that there are no conflicts of interest present.