Directed Graphs

Introduction

Does it matter whether a line goes from A to B or B to A?

A directed graph gives each edge a direction. A directed graph or digraph is an ordered pair (V, A) with

  • a set V whose elements are called vertices or nodes, and
  • a set A of ordered pairs of vertices, called arcs, directed edges, or arrows.

Use

Example

A directed graph may be represented by the following nodes and edges.

A→B→C ↓ D

The set V of vertices is

{A, B, C, D}

The set E of edges is

{(A, B), (B, C), (B, D)}

The graph may be uniquely specified as the ordered pair

( {A, B, C, D}, {(A, B), (B, C), (B, D)} )