$\begingroup$

From various books and online resources, I've come to know a directed graph is said to be strongly connected if, all of its vertices reachable from each vertices. But my question is, "is it same for the undirected graphs also ?" hence we can visit all vertices of an undirected from graph its each vertices.

$\endgroup$ 3

1 Answer

$\begingroup$

For an undirected graph, we simply say that it is connected when there is a path between any two vertices.

There are then (at least) two ways to generalize this notion to directed graphs:

• Weakly connected if there is an undirected path between any two vertices, not necessarily respecting the orientations on the edges.
• Strongly connected if there is a directed path between any two vertices.

These two definitions have the names they do because strong connectivity implies weak connectivity, but not vice versa. (If, between any two vertices, there is a directed path, it is still a path if we don't care about the orientations.)

In an undirected graph, because there is only one notion of connectivity to begin with, we don't call it strong or weak.

$\endgroup$ 3

Your Answer

Sign up or log in

Sign up using Google Sign up using Facebook Sign up using Email and Password Submit

Post as a guest

Post Your Answer Discard

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy