patternMinor
Determining if an undirected connected graph is minimally connected
Viewed 0 times
determininggraphminimallyundirectedconnected
Problem
I'm trying to solve a practice problem in Elements of Programming Interviews (19.4) and I am a bit confused. The question is to determine if an undirected connected graph is minimally connected.
The authors define minimally connected as "it is connected and there is no edge that can be removed while still leaving the graph connected."
This question is equivalent to asking if there are any cycles in the graph.
They authors' solution runs the white-gray-black variant of recursive DFS, and return false if a grey node is visited twice.
It seems to me though, that since you know the graph is connected you can just count the number of edges. Any minimally connected graph, like a binary tree, will have (V - 1) edges.
So, long story short, is this solution correct for the case of an undirected, connected graph? I checked the books errata and it doesn't mention it.
The authors define minimally connected as "it is connected and there is no edge that can be removed while still leaving the graph connected."
This question is equivalent to asking if there are any cycles in the graph.
They authors' solution runs the white-gray-black variant of recursive DFS, and return false if a grey node is visited twice.
It seems to me though, that since you know the graph is connected you can just count the number of edges. Any minimally connected graph, like a binary tree, will have (V - 1) edges.
return num_edges/2 == num_vertices - 1;So, long story short, is this solution correct for the case of an undirected, connected graph? I checked the books errata and it doesn't mention it.
Solution
If $G$ is an undirected graph, it's a standard lemma that the following are equivalent:
-
$G$ is a tree.
-
$G$ is connected and has no cycles.
-
$G$ is connected and the number of edges is one less than the number of vertices.
Therefore, yes, your solution is also correct.
(The authors' solution does have the benefit of giving you a relatively simple setting where you can think through the properties of depth-first search in a deep way. There are other problems that aren't solved so easily, and where the best solution involves some other sort of modification to depth-first search.)
-
$G$ is a tree.
-
$G$ is connected and has no cycles.
-
$G$ is connected and the number of edges is one less than the number of vertices.
Therefore, yes, your solution is also correct.
(The authors' solution does have the benefit of giving you a relatively simple setting where you can think through the properties of depth-first search in a deep way. There are other problems that aren't solved so easily, and where the best solution involves some other sort of modification to depth-first search.)
Context
StackExchange Computer Science Q#52157, answer score: 5
Revisions (0)
No revisions yet.