The Spanning Tree of a Divisible Multiple Graph
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 ed...
Saved in:
| Main Author: | |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Yaroslavl State University
2018-08-01
|
| Series: | Моделирование и анализ информационных систем |
| Subjects: | |
| Online Access: | https://www.mais-journal.ru/jour/article/view/731 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1850023959757586432 |
|---|---|
| author | Alexander V. Smirnov |
| author_facet | Alexander V. Smirnov |
| author_sort | Alexander V. Smirnov |
| collection | DOAJ |
| description | 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. |
| format | Article |
| id | doaj-art-7016325d782d4affb1c0f23c3d5e0404 |
| institution | DOAJ |
| issn | 1818-1015 2313-5417 |
| language | English |
| publishDate | 2018-08-01 |
| publisher | Yaroslavl State University |
| record_format | Article |
| series | Моделирование и анализ информационных систем |
| spelling | doaj-art-7016325d782d4affb1c0f23c3d5e04042025-08-20T03:01:14ZengYaroslavl State UniversityМоделирование и анализ информационных систем1818-10152313-54172018-08-0125438840110.18255/1818-1015-2018-4-388-401514The Spanning Tree of a Divisible Multiple GraphAlexander V. Smirnov0P.G. Demidov Yaroslavl State UniversityIn 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.https://www.mais-journal.ru/jour/article/view/731multiple graphmultiple treedivisible graphspanning treecomplete spanning treeminimum spanning tree |
| spellingShingle | Alexander V. Smirnov The Spanning Tree of a Divisible Multiple Graph Моделирование и анализ информационных систем multiple graph multiple tree divisible graph spanning tree complete spanning tree minimum spanning tree |
| title | The Spanning Tree of a Divisible Multiple Graph |
| title_full | The Spanning Tree of a Divisible Multiple Graph |
| title_fullStr | The Spanning Tree of a Divisible Multiple Graph |
| title_full_unstemmed | The Spanning Tree of a Divisible Multiple Graph |
| title_short | The Spanning Tree of a Divisible Multiple Graph |
| title_sort | spanning tree of a divisible multiple graph |
| topic | multiple graph multiple tree divisible graph spanning tree complete spanning tree minimum spanning tree |
| url | https://www.mais-journal.ru/jour/article/view/731 |
| work_keys_str_mv | AT alexandervsmirnov thespanningtreeofadivisiblemultiplegraph AT alexandervsmirnov spanningtreeofadivisiblemultiplegraph |