Random minimum spanning tree

Last updated January 21, 2025

In mathematics, a random minimum spanning tree may be formed by assigning independent random weights from some distribution to the edges of an undirected graph, and then constructing the minimum spanning tree of the graph.

When the given graph is a complete graph on $n$ vertices, and the edge weights have a continuous distribution function whose derivative at zero is $D > 0$ , then the expected weight of its random minimum spanning trees is bounded by a constant, rather than growing as a function of $n$ . More precisely, this constant tends in the limit (as $n$ goes to infinity) to $ζ (3)/ D$ , where $ζ$ is the Riemann zeta function and $ζ (3) \approx 1.202$ is Apéry's constant. For instance, for edge weights that are uniformly distributed on the unit interval, the derivative is $D = 1$ , and the limit is just $ζ (3)$ .^[1] For other graphs, the expected weight of the random minimum spanning tree can be calculated as an integral involving the Tutte polynomial of the graph.^[2]

In contrast to uniformly random spanning trees of complete graphs, for which the typical diameter is proportional to the square root of the number of vertices, random minimum spanning trees of complete graphs have typical diameter proportional to the cube root.^[3]^[4]

Random minimum spanning trees of grid graphs may be used for invasion percolation models of liquid flow through a porous medium,^[5] and for maze generation.^[6]

Related Research Articles

A minimum spanning tree (MST) or minimum weight spanning tree is a subset of the edges of a connected, edge-weighted undirected graph that connects all the vertices together, without any cycles and with the minimum possible total edge weight. That is, it is a spanning tree whose sum of edge weights is as small as possible. More generally, any edge-weighted undirected graph has a minimum spanning forest, which is a union of the minimum spanning trees for its connected components.

<span class="mw-page-title-main">Kruskal's algorithm</span> Minimum spanning forest algorithm that greedily adds edges

Kruskal's algorithm finds a minimum spanning forest of an undirected edge-weighted graph. If the graph is connected, it finds a minimum spanning tree. It is a greedy algorithm that in each step adds to the forest the lowest-weight edge that will not form a cycle. The key steps of the algorithm are sorting and the use of a disjoint-set data structure to detect cycles. Its running time is dominated by the time to sort all of the graph edges by their weight.

<span class="mw-page-title-main">Prim's algorithm</span> Method for finding minimum spanning trees

In computer science, Prim's algorithm is a greedy algorithm that finds a minimum spanning tree for a weighted undirected graph. This means it finds a subset of the edges that forms a tree that includes every vertex, where the total weight of all the edges in the tree is minimized. The algorithm operates by building this tree one vertex at a time, from an arbitrary starting vertex, at each step adding the cheapest possible connection from the tree to another vertex.

<span class="mw-page-title-main">Depth-first search</span> Search algorithm

Depth-first search (DFS) is an algorithm for traversing or searching tree or graph data structures. The algorithm starts at the root node and explores as far as possible along each branch before backtracking. Extra memory, usually a stack, is needed to keep track of the nodes discovered so far along a specified branch which helps in backtracking of the graph.

Borůvka's algorithm is a greedy algorithm for finding a minimum spanning tree in a graph, or a minimum spanning forest in the case of a graph that is not connected.

<span class="mw-page-title-main">Component (graph theory)</span> Maximal subgraph whose vertices can reach each other

In graph theory, a component of an undirected graph is a connected subgraph that is not part of any larger connected subgraph. The components of any graph partition its vertices into disjoint sets, and are the induced subgraphs of those sets. A graph that is itself connected has exactly one component, consisting of the whole graph. Components are sometimes called connected components.

In mathematics, random graph is the general term to refer to probability distributions over graphs. Random graphs may be described simply by a probability distribution, or by a random process which generates them. The theory of random graphs lies at the intersection between graph theory and probability theory. From a mathematical perspective, random graphs are used to answer questions about the properties of typical graphs. Its practical applications are found in all areas in which complex networks need to be modeled – many random graph models are thus known, mirroring the diverse types of complex networks encountered in different areas. In a mathematical context, random graph refers almost exclusively to the Erdős–Rényi random graph model. In other contexts, any graph model may be referred to as a random graph.

In the mathematical field of graph theory, a spanning treeT of an undirected graph G is a subgraph that is a tree which includes all of the vertices of G. In general, a graph may have several spanning trees, but a graph that is not connected will not contain a spanning tree. If all of the edges of G are also edges of a spanning tree T of G, then G is a tree and is identical to T.

In combinatorial mathematics, the Steiner tree problem, or minimum Steiner tree problem, named after Jakob Steiner, is an umbrella term for a class of problems in combinatorial optimization. While Steiner tree problems may be formulated in a number of settings, they all require an optimal interconnect for a given set of objects and a predefined objective function. One well-known variant, which is often used synonymously with the term Steiner tree problem, is the Steiner tree problem in graphs. Given an undirected graph with non-negative edge weights and a subset of vertices, usually referred to as terminals, the Steiner tree problem in graphs requires a tree of minimum weight that contains all terminals and minimizes the total weight of its edges. Further well-known variants are the Euclidean Steiner tree problem and the rectilinear minimum Steiner tree problem.

A Euclidean minimum spanning tree of a finite set of points in the Euclidean plane or higher-dimensional Euclidean space connects the points by a system of line segments with the points as endpoints, minimizing the total length of the segments. In it, any two points can reach each other along a path through the line segments. It can be found as the minimum spanning tree of a complete graph with the points as vertices and the Euclidean distances between points as edge weights.

In mathematics, loop-erased random walk is a model for a random simple path with important applications in combinatorics, physics and quantum field theory. It is intimately connected to the uniform spanning tree, a model for a random tree. See also random walk for more general treatment of this topic.

The $k$ -minimum spanning tree problem, studied in theoretical computer science, asks for a tree of minimum cost that has exactly $k$ vertices and forms a subgraph of a larger graph. It is also called the $k$ -MST or edge-weighted $k$ -cardinality tree. Finding this tree is NP-hard, but it can be approximated to within a constant approximation ratio in polynomial time.

In graph theory and graph algorithms, a feedback arc set or feedback edge set in a directed graph is a subset of the edges of the graph that contains at least one edge out of every cycle in the graph. Removing these edges from the graph breaks all of the cycles, producing an acyclic subgraph of the given graph, often called a directed acyclic graph. A feedback arc set with the fewest possible edges is a minimum feedback arc set and its removal leaves a maximum acyclic subgraph; weighted versions of these optimization problems are also used. If a feedback arc set is minimal, meaning that removing any edge from it produces a subset that is not a feedback arc set, then it has an additional property: reversing all of its edges, rather than removing them, produces a directed acyclic graph.

In the mathematical field of graph theory, the Erdős–Rényi model refers to one of two closely related models for generating random graphs or the evolution of a random network. These models are named after Hungarian mathematicians Paul Erdős and Alfréd Rényi, who introduced one of the models in 1959. Edgar Gilbert introduced the other model contemporaneously with and independently of Erdős and Rényi. In the model of Erdős and Rényi, all graphs on a fixed vertex set with a fixed number of edges are equally likely. In the model introduced by Gilbert, also called the Erdős–Rényi–Gilbert model, each edge has a fixed probability of being present or absent, independently of the other edges. These models can be used in the probabilistic method to prove the existence of graphs satisfying various properties, or to provide a rigorous definition of what it means for a property to hold for almost all graphs.

<span class="mw-page-title-main">Pseudoforest</span> Graph with at most one cycle per component

In graph theory, a pseudoforest is an undirected graph in which every connected component has at most one cycle. That is, it is a system of vertices and edges connecting pairs of vertices, such that no two cycles of consecutive edges share any vertex with each other, nor can any two cycles be connected to each other by a path of consecutive edges. A pseudotree is a connected pseudoforest.

In graph theory, a Trémaux tree of an undirected graph $is a type of spanning tree, generalizing depth-first search trees. They are defined by the property that every edge of connects an ancestor-descendant pair in the tree. Trémaux trees are named after Charles Pierre Trémaux, a 19th-century French author who used a form of depth-first search as a strategy for solving mazes. They have also been called normal spanning trees, especially in the context of infinite graphs.$

<span class="mw-page-title-main">Widest path problem</span> Path-finding using high-weight graph edges

In graph algorithms, the widest path problem is the problem of finding a path between two designated vertices in a weighted graph, maximizing the weight of the minimum-weight edge in the path. The widest path problem is also known as the maximum capacity path problem. It is possible to adapt most shortest path algorithms to compute widest paths, by modifying them to use the bottleneck distance instead of path length. However, in many cases even faster algorithms are possible.

The expected linear time MST algorithm is a randomized algorithm for computing the minimum spanning forest of a weighted graph with no isolated vertices. It was developed by David Karger, Philip Klein, and Robert Tarjan. The algorithm relies on techniques from Borůvka's algorithm along with an algorithm for verifying a minimum spanning tree in linear time. It combines the design paradigms of divide and conquer algorithms, greedy algorithms, and randomized algorithms to achieve expected linear performance.

In the mathematical fields of graph theory and finite model theory, the logic of graphs deals with formal specifications of graph properties using sentences of mathematical logic. There are several variations in the types of logical operation that can be used in these sentences. The first-order logic of graphs concerns sentences in which the variables and predicates concern individual vertices and edges of a graph, while monadic second-order graph logic allows quantification over sets of vertices or edges. Logics based on least fixed point operators allow more general predicates over tuples of vertices, but these predicates can only be constructed through fixed-point operators, restricting their power.

In computational complexity theory, a planted clique or hidden clique in an undirected graph is a clique formed from another graph by selecting a subset of vertices and adding edges between each pair of vertices in the subset. The planted clique problem is the algorithmic problem of distinguishing random graphs from graphs that have a planted clique. This is a variation of the clique problem; it may be solved in quasi-polynomial time but is conjectured not to be solvable in polynomial time for intermediate values of the clique size. The conjecture that no polynomial time solution exists is called the planted clique conjecture; it has been used as a computational hardness assumption.

References

↑ Frieze, A. M. (1985), "On the value of a random minimum spanning tree problem", Discrete Applied Mathematics , 10 (1): 47–56, doi: 10.1016/0166-218X(85)90058-7 , MR 0770868
↑ Steele, J. Michael (2002), "Minimal spanning trees for graphs with random edge lengths", in Chauvin, Brigitte; Flajolet, Philippe; Gardy, Danièle; Mokkadem, Abdelkader (eds.), Mathematics and Computer Science II: Algorithms, Trees, Combinatorics and Probabilities, Proceedings of the 2nd Colloquium, Versailles-St.-Quentin, France, September 16–19, 2002, Trends in Mathematics, Basel: Birkhäuser, pp. 223–245, doi:10.1007/978-3-0348-8211-8_14, ISBN 978-3-0348-9475-3
↑ Goldschmidt, Christina, Random minimum spanning trees, Mathematical Institute, University of Oxford , retrieved 2019-09-13
↑ Addario-Berry, Louigi; Broutin, Nicolas; Goldschmidt, Christina; Miermont, Grégory (2017), "The scaling limit of the minimum spanning tree of the complete graph", Annals of Probability , 45 (5): 3075–3144, arXiv: 1301.1664 , doi: 10.1214/16-AOP1132
↑ Duxbury, P. M.; Dobrin, R.; McGarrity, E.; Meinke, J. H.; Donev, A.; Musolff, C.; Holm, E. A. (2004), "Network algorithms and critical manifolds in disordered systems", Computer Simulation Studies in Condensed-Matter Physics XVI: Proceedings of the Fifteenth Workshop, Athens, GA, USA, February 24–28, 2003, Springer Proceedings in Physics, vol. 95, Springer-Verlag, pp. 181–194, doi:10.1007/978-3-642-59293-5_25, ISBN 978-3-642-63923-4 .
↑ Foltin, Martin (2011), Automated Maze Generation and Human Interaction (PDF), Diploma Thesis, Brno: Masaryk University, Faculty of Informatics.

This graph theory-related article is a stub. You can help Wikipedia by expanding it.

This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.

[frieze-1] Frieze, A. M. (1985), "On the value of a random minimum spanning tree problem", Discrete Applied Mathematics , 10 (1): 47–56, doi: 10.1016/0166-218X(85)90058-7 , MR 0770868

[steele-2] Steele, J. Michael (2002), "Minimal spanning trees for graphs with random edge lengths", in Chauvin, Brigitte; Flajolet, Philippe; Gardy, Danièle; Mokkadem, Abdelkader (eds.), Mathematics and Computer Science II: Algorithms, Trees, Combinatorics and Probabilities, Proceedings of the 2nd Colloquium, Versailles-St.-Quentin, France, September 16–19, 2002, Trends in Mathematics, Basel: Birkhäuser, pp. 223–245, doi:10.1007/978-3-0348-8211-8_14, ISBN 978-3-0348-9475-3

[goldschmidt-3] Goldschmidt, Christina, Random minimum spanning trees, Mathematical Institute, University of Oxford , retrieved 2019-09-13

[abgm-4] Addario-Berry, Louigi; Broutin, Nicolas; Goldschmidt, Christina; Miermont, Grégory (2017), "The scaling limit of the minimum spanning tree of the complete graph", Annals of Probability , 45 (5): 3075–3144, arXiv: 1301.1664 , doi: 10.1214/16-AOP1132

[d3m3h-5] Duxbury, P. M.; Dobrin, R.; McGarrity, E.; Meinke, J. H.; Donev, A.; Musolff, C.; Holm, E. A. (2004), "Network algorithms and critical manifolds in disordered systems", Computer Simulation Studies in Condensed-Matter Physics XVI: Proceedings of the Fifteenth Workshop, Athens, GA, USA, February 24–28, 2003, Springer Proceedings in Physics, vol. 95, Springer-Verlag, pp. 181–194, doi:10.1007/978-3-642-59293-5_25, ISBN 978-3-642-63923-4 .

[foltin-6] Foltin, Martin (2011), Automated Maze Generation and Human Interaction (PDF), Diploma Thesis, Brno: Masaryk University, Faculty of Informatics.

[1]

[2]

[3]

[4]

[5]

[6]