Back شجرة متفرعة Arabic Arbre d'expansió Catalan Kostra grafu Czech Udspændende træ (grafteori) Danish Spannbaum German Árbol de expansión Spanish درخت پوشا Persian Virittävä puu Finnish Arbre couvrant French עץ פורש HE

Spanning tree

For the network protocol, see Spanning Tree Protocol. For other uses, see Spanning tree (disambiguation).
A spanning tree (blue heavy edges) of a grid graph

In the mathematical field of graph theory, a spanning tree T of an undirected graph G is a subgraph that is a tree which includes all of the vertices of G.[1] In general, a graph may have several spanning trees, but a graph that is not connected will not contain a spanning tree (see about spanning forests below). 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 (that is, a tree has a unique spanning tree and it is itself).

  1. ^ "Tree". NetworkX 2.6.2 documentation. Retrieved 2021-12-10. For trees and arborescence, the adjective "spanning" may be added to designate that the graph, when considered as a forest/branching, consists of a single tree/arborescence that includes all nodes in the graph.

Developed by StudentB