Course contentsShow
← Mathematics
Lesson 2665 of 3,12153. Graph TheoryFree lesson

Weakly Connected Digraphs

Define weak connectivity in directed graphs; distinguish between strong, weak, and unilateral connectivity.

Weakly Connected Digraphs

You'll learn: How to recognize when a directed graph is weakly connected and how it differs from stronger forms of connectivity.

The Core Idea

In a directed graph (digraph), edges have direction—you can only traverse an edge from its tail to its head. This direction creates different "levels" of connectivity.

A digraph is weakly connected if you can reach every vertex from every other vertex when you ignore the direction of edges. In other words, if you treat all the directed edges as undirected edges, the resulting graph would be connected.

Think of it like a one-way street system in a city: weak connectivity means every location is reachable from every other location if you're allowed to drive the wrong way on one-way streets. You're connected "in principle," even if the legal routes don't always work.

Three Types of Connectivity

Let's clarify the hierarchy you've now encountered:

  1. Strongly connected: There's a directed path from every vertex to every other vertex, respecting edge directions. The strictest form.

  2. Weakly connected: The underlying undirected graph is connected (ignore directions). Less strict than strong connectivity.

  3. Unilaterally connected: For every pair of vertices u and v, there's a directed path from u to v or from v to u (or both), but not necessarily both ways. Sits between strong and weak connectivity.

Example

Consider vertices A → B → C with A ← C. This is weakly connected (ignoring arrows, all vertices form one component) but not strongly connected (you can't get from B to A following arrows).

Key Takeaway: A digraph is weakly connected when its underlying undirected version is connected—it's the loosest meaningful notion of connectivity in directed graphs.