.png)
Spanning Trees
A spanning tree of a graph is just a subgraph that contains all the vertices and is a tree. A graph may have many spanning trees; for instance the complete graph on four vertices
o---o
|\ /|
| X |
|/ \|
o---o
has sixteen spanning trees: o---o o---o o o o---o
| | | | | |
| | | | | |
| | | | | |
o o o---o o---o o---o
o---o o o o o o o
\ / |\ / \ / \ /|
X | X X X |
/ \ |/ \ / \ / \|
o o o o o---o o o
o o o---o o o o---o
|\ | / | /| \
| \ | / | / | \
| \| / |/ | \
o o o---o o o o---o
o---o o o o o o---o
|\ | / \ | /|
| \ | / \ | / |
| \ |/ \| / |
o o o---o o---o o o
Minimum spanning trees
Now suppose the edges of the graph have weights or lengths. The weight of a tree is just the sum of weights of its edges. Obviously, different trees have different lengths. The problem: how to find the minimum length spanning tree?
This problem can be solved by many different algorithms. It is the topic of some very recent research.
One of the algorithm is :
Kruskal's algorithm
We'll start with Kruskal's algorithm, which is easiest to understand and probably the best one for solving problems by hand.
Kruskal's algorithm:
sort the edges of G in increasing order by length
keep a subgraph S of G, initially empty
for each edge e in sorted order
if the endpoints of e are disconnected in S
add e to S
return S
0 comments: