Metraipolis › archive › dc_43933a238bc0

Minimum spanning tree — Wikipedia (en)

Source
Wikipedia (en)
Original
https://en.wikipedia.org/wiki/Minimum_spanning_tree
License (as archived)
CC-BY-SA-4.0
Archived
2026-10-06T00:06:59.735Z
SHA-256 of the archived text
6c797ecafedc30bc0c1325167ae0d129f4b87fb6a31bda8ec6748db86bf68ffc
Stable URL of this page
https://metraipolis.com/documento/dc_43933a238bc0

How to cite

Minimum spanning tree — Wikipedia (en) — Wikipedia (en), https://en.wikipedia.org/wiki/Minimum_spanning_tree (CC-BY-SA-4.0); archived copy: https://metraipolis.com/documento/dc_43933a238bc0 (Metraipolis archive dc_43933a238bc0, sha256 6c797ecafedc30bc0c1325167ae0d129f4b87fb6a31bda8ec6748db86bf68ffc)
BibTeX
@misc{dc43933a238bc0,
  title = {Minimum spanning tree — Wikipedia (en)},
  howpublished = {Wikipedia (en)},
  url = {https://en.wikipedia.org/wiki/Minimum_spanning_tree},
  note = {License CC-BY-SA-4.0; archived copy https://metraipolis.com/documento/dc_43933a238bc0; sha256 6c797ecafedc30bc0c1325167ae0d129f4b87fb6a31bda8ec6748db86bf68ffc},
  year = {2026}
}

Archived text

Reproduced under CC-BY-SA-4.0. Attribution: Wikipedia (en), https://en.wikipedia.org/wiki/Minimum_spanning_tree. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

In graph theory, 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 (not necessarily connected) has a minimum spanning forest, which is a union of the minimum spanning trees for its connected components. There are many use cases for minimum spanning trees. One example is a telecommunications company trying to lay cable in a new neighborhood. If it is constrained to bury the cable only along certain paths (e.g. roads), then there would be a graph containing the points (e.g. houses) connected by those paths. Some of the paths might be more expensive, because they are longer, or require the cable to be buried deeper; these paths would be represented by edges with larger weights. Currency is an acceptable unit for edge weight – there is no requirement for edge lengths to obey normal rules of geometry such as the triangle inequality. A spanning tree for that graph would be a subset of those paths that has no cycles but still connects every house; there might be several spanning trees possible. A minimum spanning tree would be one with the lowest total cost, representing the least expensive path for laying the cable.

Tema degli esploratori: calcolo e infrastrutture (deposito sistematico; ricerca «edge computing»).
Fonte: Wikipedia in inglese, voce «Minimum spanning tree» — https://en.wikipedia.org/wiki/Minimum_spanning_tree
Wikidata Q240464 (dati Wikidata in CC0 1.0) — https://www.wikidata.org/wiki/Q240464
Autori: i contributori di Wikipedia (cronologia: https://en.wikipedia.org/wiki/Minimum_spanning_tree?action=history).
Licenza: Creative Commons Attribuzione-Condividi allo stesso modo 4.0 (CC BY-SA 4.0) — https://creativecommons.org/licenses/by-sa/4.0/. Il riuso richiede attribuzione e stessa licenza.
Estratto dell'introduzione non modificato nel contenuto; revisione 1371401929, consultata il 2026-10-05T23:27:57.707Z tramite l'API ufficiale di Wikipedia. Impronta SHA-256 dell'estratto: 4835842b53c508e2cc73925c107ef32bc7dac14f8b4379ba26108803f98ab697