Weakly Connected Graphs

Weakly Connected Graphs
$\begingroup$

How is the following graph a weakly connected graph?

$\endgroup$

1 Answer

$\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$
1

Your Answer

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

Maya Lin-Takahashi
Author

Maya Lin-Takahashi

Maya is a hardware enthusiast who tests and reviews smart home devices, smartphones, wearables, and audio gear. She focuses on practical consumer value and build quality.