Data Structures and Algorithms with Object-Oriented Design Patterns in Python
next up previous index

Undirected Graphs

An undirected graph is a graph in which the nodes are connected by undirected arcs  . An undirected arc is an edge that has no arrow. Both ends of an undirected arc are equivalent--there is no head or tail. Therefore, we represent an edge in an undirected graph as a set rather than an ordered pair:

Definition (Undirected Graph)  An undirected graph   is an ordered pair tex2html_wrap_inline70549 with the following properties:
  1. The first component, tex2html_wrap_inline70551, is a finite, non-empty set. The elements of tex2html_wrap_inline70551 are called the vertices of G.
  2. The second component, tex2html_wrap_inline70557, is a finite set of sets. Each element of tex2html_wrap_inline70557 is a set that is comprised of exactly two (distinct) vertices. The elements of tex2html_wrap_inline70557 are called the edges of G.

For example, consider the undirected graph tex2html_wrap_inline70795 comprised of four vertices and four edges:

eqnarray48792

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

   figure48796
Figure: An undirected graph.

Notice that because an edge in an undirected graph is a set, tex2html_wrap_inline70801, and since tex2html_wrap_inline70803 is also a set, it cannot contain more than one instance of a given edge. Another consequence of Definition gif is that there cannot be an edge from a node to itself in an undirected graph because an edge is a set of size two and a set cannot contain duplicates.

next up previous index

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