1
$\begingroup$

My question is about terminology.

I am interested in the reason why spanning trees are called this way. English is not my native language so maybe there is something that I don't see and a native speaker would see.

Why are spanning trees of a graph called like this "spanning" ?

$\endgroup$
  • 1
    $\begingroup$ A "spanning subgraph" of a graph $G$ is a subgraph $H$ of $G$ which has the save vertex set, $V(H)=V(G).$ (I don't know why it's called a "spanning" subgraph.) In particular, a "spanning tree" is a spanning subgraph which is a tree, a "spanning path" is a spanning subgraph which is a path. $\endgroup$ – bof Aug 29 '17 at 8:47
  • $\begingroup$ @bof thanks. I did not know about spanning graphs $\endgroup$ – yoyo_fun Aug 29 '17 at 12:11
  • 1
    $\begingroup$ The term is spanning subgraph, not spanning graph. Here is a wikipedia referene for this terminology. $\endgroup$ – bof Aug 29 '17 at 12:18
4
$\begingroup$

In mathematics, the word "span" is used about one thing that can reach every part of a (possibly) larger thing, under a suitable definition of "reach". A tree is a special kind of graph. So a spanning tree of a given graph is a smaller graph (a so-called subgraph) which reaches every node of the original graph, but at the same time fulfills the requirements of a tree.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.