Chapter 33 Flashcards
What is strong component
A directed graph is strongly connected if there is a path between all pairs of vertices. A strongly connected component (SCC) of a directed graph is a maximal strongly connected sub graph.
What is component DAG
A DAG is converted into major components that are connected to each other. e.g. city areas connected to each other for police check posts.
What is mutual reachability
Ability of vertices to connect each other
Does mutual reachability a equivalence relation
Yes
What is component digraph
Vertices converted into strong components. Then the resulting digraph is component digraph.
Does component digraph must be acyclic
Yes
Can we reverse topological order
Yes
What about minimum spanning trees
A minimum spanning tree (MST) is a subset of the edges of a connected, edge-weighted undirected graph that connects all the vertices together, without any cycles and with the minimum possible total edge weight.
Their result is always accurate. They used in communication networks
Which trees we need to find in widgets
Minimum spanning trees
What is spanning tree
A spanning tree is a subset of Graph G, which has all the vertices covered with minimum possible number of edges. By this definition, we can draw a conclusion that every connected and undirected Graph G has at least one spanning tree.
Does electric circuit use minimum spanning tree algorithm to wire it
Yes
What is free tree
The tree which has root not clearly defined. We can choose any node to make a tree but the shape of tree should be remain a tree.
Can there be multiple spanning trees in a graph
Yes
What are 2 types of greedy algorithm
1- Kruskal
2- Prim
What is greedy algorithm
A greedy algorithm is the one that builds a solution by repeatedly selecting the cheapest among all options at each stage.
