Data Structures and Algorithms with Object-Oriented Design Patterns in C#
next up previous contents index

Directed Graphs

We begin with the definition of a directed graph:

Definition (Directed Graph)  A directed graph  , or digraph , is an ordered pair tex2html_wrap_inline70252 with the following properties:
  1. The first component, tex2html_wrap_inline70254, is a finite, non-empty set. The elements of tex2html_wrap_inline70254 are called the vertices of G.
  2. The second component, tex2html_wrap_inline70260, is a finite set of ordered pairs of vertices. That is, tex2html_wrap_inline70262. The elements of tex2html_wrap_inline70260 are called the edges of G.

For example, consider the directed graph tex2html_wrap_inline70268 comprised of four vertices and six edges:

eqnarray47897

The graph G can be represented graphically as shown in Figure gif. The vertices are represented by appropriately labeled circles, and the edges are represented by arrows that connect associated vertices.

   figure47901
Figure: A directed graph.

Notice that because the pairs that represent edges are ordered, the two edges (a,c) and (c,a) are distinct. Furthermore, since tex2html_wrap_inline70278 is a mathematical set, it cannot contain more than one instance of a given edge. And finally, an edge such as (d,d) may connect a node to itself.

next up previous contents index

Bruno Copyright © 2001 by Bruno R. Preiss, P.Eng. All rights reserved.