Minimal Spanning Trees
Notes
- I am using Roughgarden and CLRS
- A Graph G=(V,E)
- V is a set of vertices.
- E is a set of edges
- Normally vertices hold some element or data
- Represented by symbols (a,b,c ...), or (v1, v2, ... vn) for example
- |V| represents the number of vertices
- Normally edges represent a relationship betwen this data.
- Represented by pairs of edges (a,b)
- |E| represents the number of edges
- Edges can be two way (undirected) or one way (directed)
- Normally there is at most one edge between any two vertices
- Edges can be of equal value or weighted.
- Edges can have positive or negative weights.
- But normally negative weights require special algorithms.
- w(a,b) is used to sybolize the weight of edge (a,b)
- If |E| ≈ |V|2 the graph is dense
- A graph is a complete graph if there is an edge from every vertex to every other vertex.
- In this case v = |V|, |E| = $\frac{(v)(v-1)}{2}$
- If |E| ≈ |V| the graph is sparse.
- A tree is sparse as it will have |V|-1 edges
- A path P = {v1, v2, ... vn} on a graph G=(V,E) is a sequence of connected vertices such that
- vi is adjacent to vi+1, or (vi,vi+1) ∈ E for 1 ≤ i < n
- A Spanning Tree (MST): T of an undirected weighted graph G=(V,E)
- T ⊆ E
- T is a tree (ie each node has at most one parent)
- for every pair of verticies v,w ∈ V, a path P(v,w) exists in T.
- For a graph to have a spanning tree, it must be connected
- In a connected graph there is at least one path between every pair of verticies.
- for all u,v ∈ V, there exists $T_{(u,v)} \in E$
- A minimal spanning tree is a spanning tree such that $\Sigma_{e\in T} w(e)$, is minimized.