3
$\begingroup$

How is the following graph a weakly connected graph?

enter image description here

$\endgroup$
16
$\begingroup$

The concept of "strongly connected" and "weakly connected" graphs are defined for directed graphs.

A digraph is strongly connected if every vertex is reachable from every other following the directions of the arcs. I.e., for every pair of distinct vertices $u$ and $v$ there exists a directed path from $u$ to $v$.

A digraph is weakly connected if when considering it as an undirected graph it is connected. I.e., for every pair of distinct vertices $u$ and $v$ there exists an undirected path (potentially running opposite the direction on an edge) from $u$ to $v$.

In both cases, it requires that the undirected graph be connected, however strongly connected requires a stronger condition. You also have that if a digraph is strongly connected, it is also weakly connected.

In your example, it is not a directed graph and so ought not get the label of "strongly" or "weakly" connected, but it is an example of a connected graph. As soon as you make your example into a directed graph however, regardless of orientation on the edges, it will be weakly connected (and possibly strongly connected based on choices made).

$\endgroup$
  • $\begingroup$ thanks, helped me a lot! $\endgroup$ – Cosmic Dec 10 '18 at 18:56

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.