I’m not so hot on the maths for this but for what I understand…
A graph g exists with v vertices and edges. g = (V,E);
The spanning graph for this is an acyclic copy of this where all the vertices are present, and all the edges are a subset of the graph with the condition that each connection is distinct.
Apparently the MST should have n-1 nodes. How can this be proven ?
Sources:
http://youtu.be/zFbq8vOZ_0k?t=25m1s
http://www.gtkesh.com/minimum-spanning-tree/
1
Proof by induction:
Every acyclic graph can be represented as a tree, if all the nodes are connected.
So let’s think about trees. You’ve got one root node. Let’s look at the simplest, case, in which the tree only has one branch, and so it’s a simple linked list.
If there are two nodes, there’s one edge between them. Add one node to the end of the linked list, and there are three nodes and two edges, and so on.
Now if we take the linked list and add another node to one of the nodes in the middle, we have a true tree. And again, we’re adding one node along with one edge. Add another one, and it’s the same.
No matter how many nodes you add, or where you add them, as long as it remains an acyclic, fully connected tree, there will always be N-1 edges for N nodes.
Consider any minimum spanning tree.
Choose some vertex as the root.
Then each vertex has one parent, except the root.
Essentially the same as Mason and Mike have already said, but in different words…
If you have no edges, the most (connected) vertices you can have is one. Call this vertex the root.
To add a new vertex to a tree, you must also add a new edge (in order that the new vertex is connected). That edge can (and must) connect to any pre-existing vertex. The new vertex is a child of the pre-existing vertex, and we don’t limit the number of children a parent can have.
If you start with just the root (1 vertex and 0 edges) you end up with 2 vertices and 1 edge. Repeat n times to get n+1 vertices and n edges.
This isn’t a full proof in itself, but it’s impossible to add edges or vertices in any other way (except that you could add two children at once, provided that you do it in a way that’s equivalent to doing adding one first then the other). You can’t add an edge without adding a vertex because doing so would complete a cycle. You can’t add a vertex without adding an edge because that vertex wouldn’t be connected to the tree.
BTW – for undirected graphs, words like “root”, “parent” and “child” don’t mean much, at least not formally. Any vertex in any undirected tree can be considered the root, and which vertex you happen to call the root decides for all edges which vertex is the parent and which is the child. My mental image of a tree tends to include identifying a particular vertex as the root, but that’s arguably a misleading mental image.
0