[Math] Can a graph be strongly and weakly connected

graph theory

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.

Best Answer

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.

Related Solutions

[Math] Can be a graph strongly connected but with undirected edges

It depends on how you see undirected edges in presence of directed edges. Depending on your need, you can have your own definition of 'strongly connected' and define it accordingly.

As far as I know, if one says 'directed graph' then one usually means that all edges are directed. And if a graph is not directed, then it is undirected.

Here, you can also treat undirected edges as 'bi-directed' edges i.e. you can traverse in any direction on these edges. If you see undirected edges this way then yes, you can call a graph which has at least one directed edge, a 'directed graph'.

[Math] Weakly connected graph test

The best way to go about this is to perform some sort of either depth first or breadth-first search through the graph: for example, the depth first search would look something like this in pseudocode (y in the code is a "neighbor" of x if there exists an edge from x to y or from y to x)

start at random vertex x
initialize an empty stack
repeat:
    mark x as visited
    push x onto the stack
    if x has an unvisited neighbor y:
        x = y
    else:
        y = stack.pop()
untill the stack is empty

If the search concludes after visiting all vertices, then the graph is weakly connected. Otherwise, all visited vertices form a weakly connected component.

Best Answer

Related Solutions

[Math] Can be a graph strongly connected but with undirected edges

[Math] Weakly connected graph test

Related Question