Spanning tree

All 16 spanning trees of the complete graph with 4 nodes

A graph with a minimal spanning tree

A spanning tree (also spanning tree or scaffold called; English spanning tree , sometimes erroneously translated as "spanning tree") is in Graph theory , a subgraph of an undirected graph having a tree and contains all the nodes of this graph. Spanning trees only exist in connected graphs.

In a complete graph one finds different spanning trees according to the Cayley formula . In the adjacent example there are pieces. ${\displaystyle K_{n}}$ ${\displaystyle n^{n-2}}$ ${\displaystyle K_{4}}$ ${\displaystyle 4^{4-2}=16}$

Subspecies

A part graph in a graph for each component results in a spanning tree, is backbone , spanning forest or spanning forest mentioned. The graph does not necessarily have to be connected. In connected graphs, framework and spanning tree are identical terms, while spanning trees for disconnected graphs do not exist by definition.

In edge-weighted graphs, the sum of its edge weights can be defined as the weight of a graph. A spanning tree or a framework is called minimal if no other spanning tree or no other framework exists in the same graph with a lower weight. Often the minimal spanning tree is also abbreviated to MST (abbreviation of the English term Minimum Spanning Tree ) or MCST ( Minimum Cost Spanning Tree - a spanning tree with minimal costs). Instead minimal framework is also said minimum framework or scaffold smallest value . If the edge weighting function is injective, the minimum spanning tree is unique.

A spanner of a graph is a spanning subgraph in which the distance of each pair of nodes is at most times its distance in the output graph . ${\displaystyle k}$ ${\displaystyle k}$

In a degree-restricted spanning tree, not any number of edges may converge at one node.

Algorithms

A non-minimal spanning tree can be found in a graph with a set of nodes and a set of edges using a latitude or depth search in . ${\displaystyle G=(V,E)}$ ${\displaystyle V}$ ${\displaystyle E}$ ${\displaystyle {\mathcal {O}}{\bigl (}\left|V\right|+\left|E\right|{\bigr )}}$

A large number of sequential algorithms exist for the efficient calculation of minimal spanning trees, for example the algorithm of Prim , the algorithm of Kruskal and the algorithm of Borůvka . All three algorithms mentioned iteratively enlarge a subset of the edges to a minimal spanning tree and offer different approaches for parallel calculation. Another method is the Chazelle algorithm . ${\displaystyle E}$

In addition to the algorithms mentioned above, there are many other publications on the parallel calculation of minimal spanning trees. With a linear number of processors it is possible to solve the problem in time. Bader and Cong present an algorithm that calculates minimal spanning trees five times faster on eight processors than an optimized sequential algorithm. ${\displaystyle O(\log n)}$

Further specialized algorithms were developed for minimal spanning trees in the external memory model . According to the authors, this algorithm works only 2–5 times slower than an algorithm that only works on main memory.

A spanning tree of a graph can be found in linear time either by depth-first search or width-first search . Both algorithms examine the given graph starting from an arbitrary node by traversing the neighbors of the nodes they have found and adding each neighbor not found to a data structure that is to be examined later. They differ in whether this data structure is a stack (for depth-first search) or a queue (for breadth-first search). In either case, a spanning tree can be formed by connecting any node other than the root node to the node from which it was found. This tree is known as a depth-first search tree or breadth-first search tree according to the graph search algorithm used to create it.

Spanning trees are important for parallel computers and distributed systems in order to maintain communication between a number of processors. See for example the Spanning Tree Protocol or the Shout Protocol for distributed systems. However, depth-first search and breadth-first search for creating spanning trees on sequential computers are not well suited for parallel computers and distributed systems. Instead, researchers have developed several more specialized algorithms to find spanning trees in these computational models.

Optimal spanning trees have also been investigated for finite sets of points in a geometric space such as the Euclidean plane . For such an input, a spanning tree is again a tree whose nodes are the specified points . The quality of the tree is measured in the same way as in a graph, using the Euclidean distance between pairs of points as the weight for each edge . For example, a Euclidean minimal spanning tree corresponds to a minimal spanning tree in a complete graph with Euclidean edge weights. However, it is not necessary to build this graph to solve the optimization problem. For example, the Euclidean minimal spanning tree problem can be solved more efficiently with a running time on the order of magnitude by creating the Delaunay triangulation and then applying a linear running time algorithm for the minimal spanning tree of a planar graph to the resulting triangulation. ${\displaystyle O(n\cdot \log n)}$

Applications

Play media file

The Prim's algorithm generates a maze.

The calculation of minimal spanning trees is directly used in practice, for example for the creation of cost-effective interconnected networks, such as telephone networks or electrical networks. In computer networks with redundant paths, too, spanning trees are used to avoid packet duplication (see Spanning Tree Protocol ).

In graph theory itself, MST algorithms are often the basis of more complex algorithms for more difficult problems. The calculation of minimum spanning trees, for example, part of approximation algorithms for the Traveling Salesman Problem , often in the English designation traveling salesman problem- called (TSP) (see minimum spanning tree ), or for the Steiner tree problem . The latter is also a generalization of the problem of finding a minimal spanning tree.

Furthermore, spanning trees play a role in the algorithmic generation of labyrinths . A node in the spanning tree corresponds to a field, while an edge represents a possible transition to a neighboring field. A missing edge therefore describes a wall. Since spanning trees, like all trees, are cycle-free, a labyrinth created by means of spanning trees always has only one solution.

literature

• Jaroslav Nesetril, Eva Milková, Helena Nesetrilová: Otakar Borůvka on minimum spanning tree problem: Translation of both the 1926 papers, comments, history, Discrete Mathematics, 233 (2001), pages 3-36.
• Bernard Chazelle : A minimum spanning tree algorithm with inverse-Ackermann type complexity (PDF; 321 kB) . Journal ACM 47 (2000), pages 1028-1047.

Web links

Wikiversity: A lecture on spanning trees as part of a Discrete Mathematics  course - course materials

• Minimally exciting trees , Ronny Harbich, 2006
• Katharina Langkau, Martin Skutella: Minimally spanning trees , algorithm of the week, July 25, 2006. Computer Science Faculty Day .

Remarks

1. ↑ A comparable problem on directed graphs is finding a subgraph that is a rooted tree .
2. ↑ Ka Wong Chong, Yijie Han, Tak Wah Lam: Concurrent threads and optimal parallel minimum spanning trees algorithm . In: Journal of the Association for Computing Machinery . 48, No. 2, 2001, pp. 297-323. doi : 10.1145 / 375827.375847 .
3. ^ Seth Pettie, Vijaya Ramachandran: A randomized time-work optimal parallel algorithm for finding a minimum spanning forest . In: SIAM Journal on Computing . 31, No. 6, 2002, pp. 1879-1895. doi : 10.1137 / S0097539700371065 .
4. ^ David A. Bader, Guojing Cong: Fast shared-memory algorithms for computing the minimum spanning forest of sparse graphs . In: Journal of Parallel and Distributed Computing . 66, No. 11, 2006, pp. 1366-1378. doi : 10.1016 / j.jpdc.2006.06.001 .
5. ^ Roman Dementiev, Peter Sanders, Dominik Schultes, Jop F. Sibeyn: Proc. IFIP 18th World Computer Congress, TC1 3rd International Conference on Theoretical Computer Science (TCS2004) 2004, pp. 195-208. .
6. ^ Dexter Kozen: The Design and Analysis of Algorithms . Monographs in Computer Science, 1992, ISBN 978-0-387-97687-7 , pp. 19 .
7. ^ John H. Reif : Depth-first search is inherently sequential . In: Information Processing Letters . 20, No. 5, 1985, pp. 229-234. doi : 10.1016 / 0020-0190 (85) 90024-9 . .
8. ↑ RG Gallager, Humblet PA, PM Spira: A distributed algorithm for minimum-weight spanning trees . In: ACM Transactions on Programming Languages ​​and Systems . 5, No. 1, 1983, pp. 66-77. doi : 10.1145 / 357195.357200 . ; Hillel Gazit: An optimal randomized parallel algorithm for finding connected components in a graph . In: SIAM Journal on Computing . 20, No. 6, 1991, pp. 1046-1067. doi : 10.1137 / 0220066 . ; David A. Bader, Guojing Cong: A fast, parallel spanning tree algorithm for symmetric multiprocessors (SMPs) . In: Journal of Parallel and Distributed Computing . 65, No. 9, 2005, pp. 994-1006. doi : 10.1016 / j.jpdc.2005.03.011 . .
9. ^ David Eppstein : Handbook of Computational Geometry . In: Elsevier (Ed.): Spanning trees and spanners . 1999, pp. 425-461.