Остовное дерево в делимом кратном графе

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

1. Смирнов А. В., “Задача о кратчайшем пути в кратном графе”, Моделирование и анализ информационных систем, 24:6 (2017), 466–478;

2. Cormen T. H., Leiserson C. E., Rivest R. L., Stein C., Introduction to Algorithms, 3rd ed., The MIT Press, McGraw-Hill Book Company, 2009.

3. Berge C., Graphs and Hypergraphs, North-Holland Publishing Company, 1973.

4. Basu A., Blanning R.W., “Metagraphs in workflow support systems”, Decision Support Systems, 25:3 (1999), 199–208.

5. Basu A., Blanning R.W., Metagraphs and Their Applications, Integrated Series in Information Systems, 15, Springer US, 2007.

6. Рублев В. С., Смирнов А. В., “Потоки в кратных сетях”, Ярославский педагогический вестник, 3:2 (2011), 60–68

7. 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.

8. Ford L. R., Fulkerson D. R., Flows in Networks, Princeton University Press, 1962.

9. Рублев В. С., Смирнов А. В., “Задача целочисленного сбалансирования трехмерной матрицы и алгоритмы ее решения”, Моделирование и анализ информационных систем, 17:2 (2010), 72–98;

10. 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.

11. 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.