So the definition of Spanning Tree is a bit complicated and it's based on a couple of math principles. So we've shown it here on screen but we shall come back to it in just a bit so first thing to understand is we can plot a couple of points and we shall call these nodes or vertices these different circles we can plot them on a graph from graph theory and then what we can do after doing that is we can interconnect some of them in different ways using these lines that we shall call edges now note that these edges do not have arrows so in between any two points you can move in either direction so this gives us a connected undirected graph it's a graph because of the the different points that we've plotted it's connected because we have lines connecting them it's undirected because we do not have arrows on those lines that connect them additionally for networking it might be useful to have numbers on each of these lines to tell you what happens when you use that line to connect between these two nodes it could be how long it takes or how far you must go this creates what we call a weighted connected undirected graph because you have some sort of value that tells you what happens when you use that edge now let us return to the definition of spanning tree given a connected undirected graph a spanning tree of that graph is a sub graph which means a subset of the graph which is a tree now we haven't talked about a tree a tree means there are no loops if you pick any two points on this spanning tree there is only one way to travel between those two points there is no loop so the spanning tree of that graph is a sub graph which is a tree and it must connect all the vertices or the nodes together these round circles must all be connected together that defines spanning tree in terms of the mathematics now note that a single graph might have many different spanning trees this one is different from the one that we saw on the previous slide just by choosing different edges that you shall use as the sub subgraph that you create your tree out of.
© Produced by Philip Smith and the Network Startup Resource Center, through the University of Oregon.
Attribution-NonCommercial 4.0 International (CC BY-NC 4.0)
This is a human-readable summary of (and not a substitute for) the license. Disclaimer. You are free to: Share — copy and redistribute the material in any medium or format Adapt — remix, transform, and build upon the material The licensor cannot revoke these freedoms as long as you follow the license terms. Under the following terms: Attribution — You must give appropriate credit, provide a link to the license, and indicate if changes were made. You may do so in any reasonable manner, but not in any way that suggests the licensor endorses you or your use. NonCommercial — You may not use the material for commercial purposes. No additional restrictions — You may not apply legal terms or technological measures that legally restrict others from doing anything the license permits.