Weak and Strong components of graph

Question

I have a graph:

I have in my homework assignament that it has 2 weak and 2 strong connected components. I clearly see strong components {4,5} and {0..3} But why they are also weak components if we cant even go from one component to another??

Do I understand weak components incorrectly?

Answer 1

Your directed graph has 2 disconnected components.

Lets call {4,5} A, and {0,1,2,3} B.

There is no way to traverse from A to B or visa versa from B to A.

Component A is strongly connected. A is strongly connected because you can traverse to every other vertex in the component from every vertex in the component.

Let's see:

• From 4 we can get to 5 by following the edge (4,5).
• From 5 we can get to 4 by following the edge (5,4).

Component B is also strongly connected. B is strongly connected because there exists a path from every vertex in B to every other vertex in B. There does not need to be an immediate edge to every vertex from every vertex, only a path that can reach them.

Let's see:

• From 0 we can get to 1 and 2 and 3 by following the path (0,1), (1,2), (2,3).
• From 1 we can get to 2 and from there to either 0 or 3.
  • Note: The two paths split at 2. (1,2), (2,0). And (1,2), (2,3).
• From 2 we only need to prove that we can get to either 0 or 1, because we have already proved that we can get to everything from either 0 or 1. We can get to 0 by following the edge (2,0). And then from 0 to every other vertex in component B.
  • Just in case you would like a full path from 2 to every other vertex in component B here is an example: (2,0),(0,1),(1,2),(2,3) .
• From 3 we only need to prove that we can get to 0 or 1 or 2 since we have already proved that we can get to anywhere from 0 or 1 or 2. We can get to 1 by following the edge (3,1) and from 1 to every other vertex in component B.
  • Just in case you would like a full path from 3 to every other vertex in component B here is an example: (3,1),(1,2),(2,0).

Now we have proved that Component A {4,5} and Component B {0,1,2,3} are both strongly connected connected components.

The definition of a weakly connected component is that if you ignore the direction of the edges there exists a path from every vertex in the component to every other vertex in the component. We already solved the harder problem of determining that Components A and B were both strongly connected components by using the directed edges. If we ignore the fact that the edges are directed such that they can go either way, it only makes the problem of connectivity that much easier to solve.

For that reason, every strongly connected component is also a weakly connected component, but it is not only a weakly connected component. A weakly connected component may or may not be a strongly connected component.

A strongly connected component satisfies the definition of both strongly and weakly connected.

Answer 2

"A directed graph is called weakly connected if replacing all of its directed edges with undirected edges produces a connected (undirected) graph."

So $\{4,5 \}$ and $\{0,1,2,3\}$ are weakly connected.

Clarification example:

is not strongly connected, because there is no way to get from vertex $2$ to vertex $1$. But if you replace the directed edge with an undirected edge, you can get from $2$ to $1$ (and of course $1$ to $2$), so the original graph is weakly connected.

Of course any strongly connected graph is also weakly connected.