Spanning tree
A spanning tree (also called a spanning tree, english spanning tree, sometimes wrongly translated as " spanning tree " ) is in graph theory, a subgraph of an undirected graph is a tree and contains all nodes of this graph. Spanning trees exist only in connected graphs.
Subspecies
A subgraph that results in a spanning tree in a graph for each component is called scaffolding, or spanning forest spanning forest. Here, the graph is not necessarily contiguous. In a connected graph structure and spanning tree are identical concepts, while spanning trees for incoherent graphs are not defined.
In edge-weighted graph can be used as weight of a graph the sum of its edge weights define. A spanning tree or a structure is minimal, when no other spanning tree or any other structure in the same graph, there lighter weight. Frequently minimum spanning tree with MST ( abbreviation of minimum spanning tree ) or MCST (minimum cost spanning tree - a spanning tree with minimum cost ) will be abbreviated. Instead minimal scaffold is also said minimum framework. If the edge weight function is injective, so 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 the times its distance in the output graph.
With a degree restricted spanning tree may not converge at a node as many edges.
Algorithms
A non- minimal spanning tree can be found in a graph with vertex set and edge set by width or depth-first search in.
To finding a minimum spanning tree, there is, among other things Kruskal algorithm and the algorithm of the latter is the more efficient Prim and has the worst-case run-time. However, he needed for a rather complex data structure, the so-called Fibonacci heaps.
Applications
The calculation of minimum spanning trees finds direct application in practice, for example for the creation of cost- related networks, such as telephone networks or electric networks. Spanning trees are used (see Spanning Tree Protocol ) to avoid packet duplication Also for computer networks with redundant paths.
In graph theory itself MST algorithms are often based on complex algorithms for difficult problems. The calculation of minimum spanning trees, for example, part of approximation algorithms for the problem of a Salesman, often in the English name traveling salesman problem- (TSP ) called (see MST heuristic ), or for the Steiner tree problem. The latter is also a generalization of the problem of finding a minimum spanning tree.
Furthermore spanning trees play in the algorithmic generation of mazes a role. A node in the spanning tree corresponds to a field while an edge represents a possible transition to a neighboring field. A missing edge thus describes a wall. Since spanning trees, like all trees are cycle-free, has a produced means of spanning trees labyrinth always only one solution.