1
$\begingroup$

I'm currently revising course notes on directed graphs.

It says that a directed graph (digraph) is strongly connected if there is a path between every pair of vertices.

It also says that a digraph is weakly connected if the underlying undirected graph is connected.

My question is, can one digraph be both strongly and weakly connected?

For example: Digraph and undirected graph

Can this graph (image) be both strongly and weakly connected? or does it have to be either strongly, or either weakly?

Thank you.

$\endgroup$
1
$\begingroup$

As suggested by the terminology, any strongly connected graph is weakly connected, but a weakly connected graph is not necessarily strongly connected. For instance, the graph $1 \to 2$ is weakly connected but is not strongly connected.

$\endgroup$
1
$\begingroup$

Yes, a graph can, according to the provided definitions, definitely be both weakly and strongly connected at the same time. Your example is exactly such a graph.

In fact, all strongly connected graphs are also weakly connected, since a directed path between two vertices still connect the vertices upon removing the directions.

$\endgroup$
0
$\begingroup$

To some extent this is a question about word usage in mathematics. One natural reading of the English term "weakly connected" would be "the connectedness of the graph is weak", weak meaning that it is deficient in some sense like a weak signal.

However, the use of "weakly" here is more of a conjugation of the term "weak connectedness", i.e. connected in a weak sense of the word "connected", with weak meaning that it is not a very strenuous requirement. A graph is weakly connected if it satisfies this weak connectedness requirement, not because it is less strongly connected than other graphs.

This is a fairly common idiom in math. In functional analysis one might refer to a sequence that is "weakly convergent" (again meaning convergent in a more generous sense that has a precise definition), and then later show that the same sequence is in fact strongly convergent.

There are other cases where the terminology is indeed exclusive, unlike the present case: when an infinite series is "conditionally convergent", the definition specifically excludes the case that it is absolutely convergent (which is a stronger notion of convergence).

$\endgroup$

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.