Directed vs Undirected Graphs

Undirected edges are symmetric; directed edges have direction. In the adjacency list of an undirected graph, each edge appears in both lists.

Applications: road networks (often directed), social networks (often undirected), dependency graphs (directed).

$$(u,v)\in E \nRightarrow (v,u)\in E$$

Where used

Dependencies and links are directed; roads with one-way restrictions are the same. Undirected models represent symmetric relationships. The choice changes reachability and algorithm selection.

Depth

A directed edge is an ordered relationship from the source to the target. Reachability can thus be asymmetric. In an undirected edge, the neighborhood is mutual.

In neighborhood collections, the undirected relationship is often represented by two entries. Algorithms must still recognize that both entries describe the same logical edge, for example, when counting or searching for cycles.

Strong connectivity in directed graphs requires mutual reachability, while weak connectivity ignores directions for consideration. These concepts coincide in the undirected case.

Difficulty levels

1. Distinguish between in-degree and out-degree.
2. Count logical edges despite double storage.
3. Compare strong and weak connectivity.

Pitfalls

An edge in one direction does not allow a return. When summing all neighborhood sizes, undirected edges without loops are counted twice.