Graphs:Introduction and Graph Representations

Introduction

Trees, as data structures, are somewhat limited because they can only represent relations of a hierarchical nature, such as that of parent and child. A generalization of a tree so that a binary relation is allowed between any pair of elements would constitute a graph—formally defined as follows:

A graph G = (V, E) consists of a finite set of vertices V = {υ1, υ2,..., υn} and a finite set E of edges E = {e1, e2,..., em} (see Figure 4.1).

To each edge e there corresponds a pair of vertices (u, υ) which e is said to be incident on. While drawing a graph we represent each vertex by a dot and each edge by a line segment joining its two end vertices. A graph is said to be a directed graph (or digraph for short) (see Figure 4.2) if the vertex pair (u, υ) associated with each edge e (also called arc) is an ordered pair. Edge e is then said to be directed from vertex u to vertex υ, and the direction is shown by an arrowhead on the edge.

A graph is undirected if the end vertices of all the edges are unordered (i.e., edges have no direction). Throughout this chapter we use the letters n and m to denote the number of vertices |V | and number of edges |E| respectively, in a graph. A vertex is often referred to as a node (a term more popular in applied fields).

Two or more edges having the same pair of end vertices are called parallel edges or multi edges , and a graph with multi edges is sometimes referred to as a multigraph. An edge whose two end vertices are the same is called a self-loop (or just loop). A graph in which neither

parallel edges nor self-loops are allowed is often called a simple graph. If both self-loops and parallel edges are allowed we have a general graph (also referred to as pseudograph). Graphs in Figure 4.1 and Figure 4.2 are both simple but the graph in Figure 4.3 is pseudograph. If the graph is simple we can refer to each edge by its end vertices. The number of edges incident on a vertex v, with self-loops counted twice, is called the degree, deg(v), of vertex v. In directed graphs a vertex has in-degree (number of edges going into it) and out-degree (number of edges going out of it).

In a digraph if there is a directed edge (x, y) from x to y, vertex y is called a successor of x and vertex x is called a predecessor of y. In case of an undirected graph two vertices are said to be adjacent or neighbors if there is an edge between them.

A weighted graph is a (directed or undirected) graph in which a real number is assigned to each edge. This number is referred to as the weight of that edge. Weighted directed graphs are often referred to as networks . In a practical network this number (weight) may represent the driving distance, the construction cost, the transit time, the reliability, the transition probability, the carrying capacity, or any other such attribute of the edge [1, 4, 18, 20].

Graphs are the most general and versatile data structures. Graphs have been used to model and solve a large variety of problems in the discrete domain. In their modeling and problem solving ability graphs are to the discrete world what differential equations are to

the world of the continuum.

Graph Representations

For a given graph a number of different representations are possible. The ease of implementation, as well as the efficiency of a graph algorithm depends on the proper choice of the graph representation. The two most commonly used data structures for representing a graph (directed or undirected) are adjacency lists and adjacency matrix . In this section we discuss these and other data structures used in representing graphs.

Adjacency Lists: The adjacency lists representation of a graph G consists of an array Adj of n linked lists, one for each vertex in G, such that Adj[υ] for vertex υ consists of all vertices adjacent to υ. This list is often implemented as a linked list. (Sometimes it is also represented as a table, in which case it is called the star representation [18].)

Adjacency Matrix: The adjacency matrix of a graph G = (V, E) is an n × n matrix A = [aij ] in which aij = 1 if there is an edge from vertex i to vertex j in G; otherwise aij = 0. Note that in an adjacency matrix a self-loop can be represented by making the corresponding diagonal entry 1. Parallel edges could be represented by allowing an entry to be greater than 1, but doing so is uncommon, since it is usually convenient to represent each element in the matrix by a single bit. The adjacency lists and adjacency matrix of an undirected graph are shown in Figure 4.4, and the corresponding two representations for a digraph are shown in Figure 4.5.

Clearly the memory required to store a graph of n vertices in the form of adjacency matrix is O(n2), whereas for storing it in the form of its adjacency lists is O(m + n). In general if the graph is sparse, adjacency lists are used but if the graph is dense, adjacency matrix is preferred. The nature of graph processing is an important factor in selecting the data structure.

There are other less frequently used data structures for representing graphs, such as forward or backward star , the edge-list , and vertex-edge incidence matrix [1, 4, 15, 18, 20].

Weighted Graph Representation

Both adjacency lists and adjacency matrix can be adapted to take into account the weights associated with each edge in the graph. In the former case an additional field is added in the linked list to include the weight of the edge; and in the latter case the graph is represented by a weight matrix in which the (i, j)th entry is the weight of edge (i, j) in the weighted graph. These two representations for a weighted graph are shown in Figure 4.6. The boxed numbers next to the edges in Figure 4.6(a) are the weights of the corresponding edges.

It should be noted that in a weight matrix, W , of a weighted graph, G, if there is no edge (i, j) in G, the corresponding element wij is usually set to ∞ (in practice, some very large number). The diagonal entries are usually set to ∞ (or to some other value depending on the application and algorithm). It is easy to see that the weight matrix of an undirected graph (like the adjacency matrix) is symmetric.