Key Concepts Flashcards
What is a DAGs?
Directed, Acyclic Graphs
What are Strongly Connected Components?
subsets of vertices in a directed graph such that there is a directed path from any vertex in the subset to every other vertex in the same subset.
What are Sources?
In a directed graph, a source is a vertex in a directed graph that has no incoming edges.
What are Sinks?
In a directed graph, a sink is a vertex in a directed graph that has no outgoing edges.
What are Trees?
is a specific type of undirected graph that is connected and acyclic.
In a directed graph, each vertex, except the root, has one incoming edge (from its parent) and may have multiple outgoing edges (to its children). The tree will be acyclic.
What is a MST?
MST is Minimum Spanning Tree. a connected, undirected graph is a tree that spans all the vertices of the graph, with the minimum possible total edge weight
What are Flow Networks?
is a directed graph in which each edge has a capacity and a flow
In runtime, O(m+n), what does m signify and what does n signify?
m signify edges
n signify vertices
In runtime O(C m), what does C signify?
Size of the max flow
What algorithm does Ford-Fulkerson use internally?
DFS
What black-box algorithms do SCC use internally?
2 DFS
What algorithm does Edmond-Karp use internally?
BFS
Why would use Djistra’s over Belman Ford and Floyd Warshall?
Dijkstra’s are more efficient for postive weights only.
Why would use Belman Ford and Floyd Warshall over Djikstra’s?
Bellman Ford and Floyd Warshall works on negative weights, whereas Djikstra’s does not.
Why would you use Floyd Warshall over Bellman Ford?
Floyd Warshall is good for finding shortest path from all vertices, whereas Bellman Ford is only good for finding shortest path from 1 vertex.
Why would you use Bellman Ford over Floyd Warshall ?
Floyd Warshall is good for finding shortest path from all vertices, whereas Bellman Ford is only good for finding shortest path from 1 vertex to all other vertices.
Why would you choose Kruskal’s over Prim or vice versa?
It does not matter which algorithm you use. Choose one which is easier to remember.
Reference: https://edstem.org/us/courses/50892/discussion/4313106?comment=10048285
Why would you use DFS over BFS or vice versa?
BFS is good for finding the shortest path for unweighted graphs from a starting vertex using dist(u).
DFS is good at topologically sorting a DAG and finding connected components.
Do Kruskal’s and Prims algorithm work on directed and undirected graphs?
No. They don’t work on directed graphs.
Why would you choose Explore over DFS?
Explore takes a starting vertex as an input. Explore only visits all reachable vertices from the starting vertex. We’ll get a visited array with reachable vertices marked as TRUE and non-reachable vertices marked as FALSE.
whereas DFS explores all vertices regardless if they are reachable from the starting vertex. The visited array for DFS will always return TRUE for all vertices.
What is the Cut Property?
asserts if (and only if) an edge is of minimum weight on any cut, then the edge is part of some MST.
This property is used to include edges
What is the difference between Ford-Fulkerson and Edmonds-Karp algorithm?
Edmonds-Karp only needs positive capacities whereas Ford-Fulkerson requires positive integer capacities.
What are the different types of graphs?
- connected vs disconnected vs strongly connected
- undirected vs directed
- cycle vs acyclic
- weighted vs unweighted
* positive vs negative weights
What is the Cycle Property?
states if e is the unique heaviest edge in any cycle of G, then e cannot be a part of any MST
This property is used to exclude edges.
In an undirected graph, what are bridges?
An edge in an undirected connected graph is a bridge if removing it disconnects the graph.
In an undirected graph, what are leaves?
A node in a graph is a leaf (or a leaf node) if it has degree one and the only edge associated to the node is either undirected or is directed to it.
In the example, 1, 2, 3, and 6 are leaves
What assumptions can we make with flow networks?
They are connected, weighted, and directed graphs.
What are the properties of a Tree?
Property 2: A tree on n nodes has n - 1 edges
Property 3: Any connected, undirected graph G = (V, E) with |E| = |V| - 1 is a tree
Property 4: An undirected graph is a tree if and only if there is a unique path between any pair of nodes
Reference: DPV book pg. 129 under section 5.1.1
Which of the following graphs do SCC work on?
undirected graphs
directed graphs
directed graphs
What does 2-SAT do differently from other algorithms?
While other problems involve reducing to a Graph, 2Sat involves reducing to a 2-satisfiability CNF into a graph.
Both BFS and Dijkstra’s find the shortest path. What are the differences?
BFS tells us how many edges from s (does not consider edge weights). O(m+n)
Dijkstras considers edge weights. O(n+m) log n)
What does BFS return if vertex s is unable to reach a vertex v?
inf
Reference: Joves Office Hour
Which version of Dijkstra’s do we use in the lectures?
Dijkstra’s using binary heap.
Reference: Joves Office Hour
What does Dijkstra’s return if vertex is unable to reach a vertex v?
inf
Reference: Joves Office Hour
Do Kruskal’s and Prims work with negative edge weights? Or only positive edge weights?
They work with both negative and positive edge weights.
Reference: Joves Office Hour
