THE USE OF GRAPH THEORY

The Use OF Graph Theory In Computer Science

The Use OF Graph Theory In Computer Science

Introduction

In computer science, a graph is an abstract data structure that is meant to implement the graph concept from mathematics.

A graph data structure consists mainly of a finite (and possibly mutable) set of ordered pairs, called edges or arcs, of certain entities called nodes or vertices. As in mathematics, an edge (x,y) is said to point or go from x to y. The nodes may be part of the graph structure, or may be external entities represented by integer indices or references. A graph data structure may also associate to each edge some edge value, such as a symbolic label or a numeric attribute (cost, capacity, length, etc.).

Computer Science is the study of the ways computers are utilized both to collect and to disseminate information. The discipline of computing has been characterized by the Association for Computing Machinery as "the systematic study of algorithmic processes—their theory, analysis, design, efficiency, implementation, and application—that describe and transform information." The association goes on to say, "In Europe the discipline of computing is called informatics, a name that directs attention to the central role of information. The fundamental question underlying all of computing is, What can be efficiently automated?" (Alizadeh, 1995, 13-51)

Different data structures for the representation of graphs are used in practice, e.g.

Adjacency list - An adjacency list is implemented as an array with one linked list for each source node, containing the destination nodes of the edges that leave each node.

Incidence list - A variant of the adjacency list that allows for the description of the edges at the cost of additional edges.

Adjacency matrix - A two-dimensional Boolean matrix, in which the rows and columns represent source and destination vertices and entries in the array indicate whether an edge exists between the vertices.

Incidence matrix - A two-dimensional Boolean matrix, in which the rows represent the vertices and columns represent the edges. The array entries indicate if both are related, i.e. incident.

Adjacency lists are preferred for sparse graphs; otherwise, an adjacency matrix is a good choice.

For graphs with some regularity in the placement of edges, a symbolic graph is a possible choice of representation.

Discussion

Graphs are represented graphically by drawing a dot for every vertex, and drawing an arc between two vertices if they are connected by an edge. If the graph is directed, the direction is indicated by drawing an arrow.

A graph drawing should not be confused with the graph itself (the abstract, non-visual structure) as there are several ways to structure the graph drawing. All that matters is which vertices are connected to which others by how many edges and not the exact layout. In practice it is often difficult to decide if two drawings represent the same graph. Depending on the problem domain some layouts may be better suited and easier to understand than others.( Kimia, 1995, 189-224)

Graph-theoretic data structures

There are different ways to store graphs in a computer ...