Not that anyone is horribly interested in nerdy math stuff...but here's what a spanning tree is.
The image above is what we mathy people call a graph. It consists of a vertex set and an edge set. Vertices are points (zero-cells, if you really want) and edges are lines (one-cells). So you have a bunch of lines and a bunch of dots...and now you play connect the dots. That's a graph.
A tree (in math) is a graph with no closed loops. Here's a tree:
Note that this tree contains no closed polygons. That's what makes it a tree. Just like trees in the real world, generally.
A spanning tree is a subset of a graph. Specifically, a spanning tree contains the vertex set and enough of the edge set to keep all connected subsets of the graph connected. (Connected = you can draw it without picking up your pencil. And you're allowed to cross lines and draw back over lines you already drew.) The above tree is, in fact, a spanning tree for the graph up at the top. Here's a picture of them together.
Note that spanning trees are not unique. Here's another one for the graph at the top.
And again with the original graph superimposed:
On the second spanning tree I decided to go for the "without lifting the pencil, crossing lines, or drawing back over what you already drew" method.
Anyhow, that's what a spanning tree is. They play a significant role in Bass-Serre theory and graphs of groups. I'm not going to try to explain either. If you really want you can search for Bass-Serre theory on wikipedia. It's on there.
And I'm terribly clever for naming my blog "spanning trees" because I do tree work. Like the leafy things with bark and trunks. I'll get some pictures of that soon.
And I also promise that this blog won't be exclusively about math. Or tree work.
well done, but in your next post you should explore statistics; with a focus on "stem-and-leaf" plots.
ReplyDeleteOr you can do some tree diagrams. Those are always fun.
ReplyDeleteif you don't do a tree diagram you can do a family tree.
ReplyDelete