Graphs and Trees Flashcards
What is the definition of a graph?
A graph G is a set of vertices V and a set of edges E
Each edge in E is a pair (u,v) are vertices in V
What is adjacent and incident?
Adjacent: Two vertices are adjacent when connected by an edge
Incident: A vertice at either end of an edge is considered incident to that edge
Define:
- walk
- path
- cycle
Walk: a sequence of alternating vertices and edges
Path: a walk in which no vertex is visited twice and no edge is used twice
Cycle: is a path that ends where it began (an edge joins the first and last vertex)
Define:
- connected
- disconnected
- components
- Connected : there exists a path between all vertices
- disconnected: there is not a path between all vertices
- components: when a graph is disconnected, each connected sub-graph is a component of the larger graph
What is:
- A tree
- A spanning tree
What are useful facts about a spanning tree?
Tree: A connected graph with no cycles
Spanning tree: subsets of a graph G that forms a tree (connected with no cycles)
Userful facts about spanning tree:
- Every connected graph has a spanning tree
- A spanning tree has N vertices and N-1 edges (a quick way to check if a spanning tree)
What is:
A weighted graph
Minimum spanning tree
weighted graph: a graph where each edge has a numeric value
minimum spanning tree: a weight graph G, whose set of edges has the least possible total weight when compared to all spanning trees in G
- It is possible for a graph G to have multiple minimum spanning trees
Optimization Problem: Minimum Spanning Tree
What is the input?
Optimization Problem: Minimum Spanning Tree
What is the required output?
Optimization Problem: Minimum Spanning Tree : Solution
Let’s say we have a complete, connected graph on n vertices.
What is the number of spanning trees (feasible solutoions)?
There are nn-2 feasible solutions.
Among those, for a MST we are looking for the feasible solution with the minimum cost
Prim’s Algorithmm for MST
What is the general idea?
General idea: Exapnd the spanning tree one edge at a time
How:
At each step you have a connected tree T
Start with any single vertex in the graph then:
- Make tree T bigger by adding the smallest-weight edge that has one connection inside of T and one endpoint outside of T
- Repeat n-1 times
What does the mathy pseudo code for Prim’s MST algorithm look like?
What is the pseudo code for Prim’s MST Algorithm
MST Algo: Prim
How do you prove the greedy-choice property?
MST Algo: Prims
How do you prove the optimal substructure property?
what is the run time of prim’s algorithm?
Kruskal’s Algo for MST
What is the general idea?
MST Algo: Kurskal’s
What is the mathy speak pseudo code?
MST Algo: Kruskal
What is the Pseudo code?
Prove the greedy choice property for MST Kruskal
Prove the Optimal substructure for Kraskals
Explain how Disjoint Set (Abstract Data Type) helps to implement kraskal’s algorithm
What is the analysis runtime speed off Kruskal’s Algorithm?
