In a weighted connected graph, if all edge weights are distinct, how many unique Minimum Spanning Trees (MSTs) exist?
If all edge weights in a connected graph are unique, the Minimum Spanning Tree is strictly unique.
If we decrease the weight of an edge that is ALREADY part of an MST, how does the MST change?
Decreasing the weight of an edge already present in the MST strictly lowers its cost further without creating cycles, so the MST structure remains valid and optimal.
Which graph algorithm uses the transitive closure matrix concept (Warshall's algorithm)?
Warshall's algorithm for boolean transitive closure is the direct precursor to Floyd-Warshall's dynamic programming all-pairs shortest path algorithm.
In a directed graph, vertex u is a source if:
A source vertex in a directed graph has an in-degree of 0 (no incoming edges) and positive out-degree.
In a directed graph, vertex v is a sink if:
A sink vertex has positive in-degree (incoming edges) and an out-degree of 0 (no outgoing edges).