COMP2521 Directed Graphs and Weighted Graphs Notes

Directed Graphs and Weighted Graphs

Overview of Directed Graphs

• Definition: A directed graph (or digraph) consists of a set of vertices connected by edges, where each edge has a direction.

• Notation: An edge from vertex v to vertex w is denoted as (v, w).

Applications of Directed Graphs

• Examples of real-world representations:

  • Social Media: Relationships like following on Twitter, where direction is significant (e.g., you can follow someone without them following you back).

  • Traffic: One-way streets where movement is restricted in certain directions.

  • Task Scheduling: Tasks can depend on the completion of previous tasks, represented as directed edges.

  • Function Calls: In programming, a function call can be viewed as a directed edge from one function (vertex) to another.

Terminology in Directed Graphs

• In-Degree: The number of incoming edges to a vertex.

  • Notation: $ext{deg}^-(v)$ or $ext{in}(v)$

• Out-Degree: The number of outgoing edges from a vertex.

  • Notation: $ext{deg}^+(v)$ or $ext{out}(v)$

Example of In-Degree and Out-Degree

• For a vertex configuration:

  • Vertex 0: in(0) = 1, out(0) = 1

  • Vertex 1: in(1) = 2, out(1) = 0

  • Vertex 2: in(2) = 1, out(2) = 3

  • Vertex 3: in(3) = 2, out(3) = 2

Paths and Connectivity

• Directed Path: A sequence of vertices where each vertex connects to the next via an outgoing edge.

  • If there’s a directed path from vertex v to vertex w, w is reachable from v.

• Directed Cycle: A directed path where the starting and ending vertices are the same (e.g., 0-2-3-1-0).

• Strong Connectivity: A digraph is strongly connected if every vertex is reachable from every other vertex.

• Strongly-Connected Component: A maximal strongly connected subgraph.

Representations of Directed Graphs

Directed graphs can be represented similarly to undirected graphs:

• Adjacency Matrix: A 2D array where the cell at (i, j) indicates whether there is a directed edge from vertex i to vertex j.

• Adjacency List: Each vertex has a list of vertices it points to (outgoing edges).

• Array of Edges: A list that stores every directed edge, typically as pairs of vertices.

Complexities of Representations

• Space Complexity:

  • Adjacency Matrix: $O(V^2)$ where V is the number of vertices.

  • Adjacency List: $O(V + E)$ where E is the number of edges.

  • Array of Edges: $O(E)$.

• Operations:

  • Insert Edge: O(1) for matrix; O(deg(v)) for list; O(E) for array.

  • Remove Edge: Similar complexity to insertion.

  • Check for Edge: O(1) for matrix; O(deg(v)) for list; O(log(E)) for array.

Weighted Graphs

• Definition: In a weighted graph, each edge (s, t) has a weight (also referred to as a cost).

  • Notation: An edge may be denoted as (s, t, w) where w is the weight.

• Applications: Can represent costs such as distances, times, or capacities in transporting goods.

Representations of Weighted Graphs

• Adjacency Matrix for Weighted Graphs:

  • Weights are stored in the cell that corresponds to a directed edge.

  • A special value can indicate “no edge” for unconnected vertices.

Example Adjacency Matrix for Weighted Graphs:

• Example Matrix:
  $<br>\begin{bmatrix} 0 &amp; 0.2 &amp; 0.4 \ 0.5 &amp; 0 &amp; 0.6 \ 0.1 &amp; 0.7 &amp; 0 \ ext{…} \ ext{…} \ ext{…} \ ext{…} \ ext{…} <br>\end{bmatrix}<br>$

• Adjacency List for Weighted Graphs:

  • Each node in a list contains pairs of adjacent nodes and weights.

Array of Edges Representation:

• An array that holds each edge as a triplet of vertices and weight (e.g., (0, 2, 0.2)).

Summary

• Directed and weighted graphs extend the concept of regular graphs to handle directionality and cost/weight tasks effectively. They are critical in many applications including navigation systems, network flows, and algorithmic problem solving.