Lecture Notes: Adjacency Matrix in Directed Graphs (Digraphs)

Introduction

• Focus on creating an adjacency matrix for a directed graph (digraph).
• Unlike undirected graphs, the adjacency matrix in a digraph is not symmetrical.

Key Concepts

Directed Graph (Digraph)

• A graph where edges have a direction, represented as arrows.
• Origin of an arrow is the tail, and it points towards the head.
• Example: food chain, where "A" gets eaten by "E" (A -> E).

Adjacency Matrix for Digraph

• Represented by a matrix where rows are origins (tails) and columns are destinations (heads).
• An entry of 1 indicates a direct edge from the row node to the column node.
• An entry of 0 indicates no direct edge.
• No symmetry: A can point to E, but E may not point to A.

Process of Filling the Adjacency Matrix

Diagonal

• No loops in nodes A, B, C, D, E, so the diagonal entries are zero.
  • A to A = 0
  • B to B = 0
  • C to C = 0
  • D to D = 0
  • E to E = 0

Off-Diagonal

• A
  • A to B = 0 (cannot directly go from A to B)
  • A to C = 0
  • A to D = 1 (direct edge exists)
  • A to E = 1 (direct edge exists)
• B
  • B to A = 0
  • B to C = 1 (direct edge exists)
  • B to D = 0
  • B to E = 1 (direct edge exists)
• C
  • C to A = 1 (direct edge exists)
  • C to B = 0
  • C to D = 0
  • C to E = 0
• D
  • D does not connect anywhere directly (all zeros)
• E
  • E does not connect anywhere directly (all zeros)

Summary

• An adjacency matrix for a digraph displays direct paths with 1s and non-paths with 0s.
• No symmetry; directionality is key in digraphs.
• Possibility for bidirectional arrows where both nodes could point to each other.