Minimum Spanning Tree Flashcards
What is kruskals algorithm?
Choose an unused edge with the lowest value
Add this edge to your tree
If there are n-1 edges in your tree, stop. If not go back to step one
Prims algorithm
From your start vertex , draw the lowest valued edge to start your tree
From any vertex on your tree, add the edge with the lowest value
If there are n-1 edges in your tree, stop
In an algorithm what can’t you do
Create a cycle
What is the matrix form of prims algorithm
Select the first node
Cross out the row and number the column for that node
Find the minimum undeleted weight in numbered columns. Circle the value. The node for this row is the next chosen node
Repeat 2 and 3 until all nodes are chosen
Isomorphic =
Graphs that show the same information
Connected graphs =
Be able to pick the whole thing up and take it anywhere without a vertex being left behind
Simple graph =
No multiple edges or loops
What is the order if every vertex on a complete graph
N-1
Total number of degrees =
2 x number of edges
Subdivision =
If you add extra vertices along the edges of a graph the result is a subdivision
Complete graph Kn has how many edges
N(n-1)/2
Bipartite graph =
Joining to distinct sets of vertices
But they can’t connect vertically
How to work out the edges on a complete bipartite graph Knm
N x m
What does order of a vertex mean
How many edges in or out of a vertex
What is ulers formula
V + F = 2 + E
What does the face count as
A face
