Chapter 6

GRAPH THEORY

6.1 INTRODUCTION

In this chapter, we introduce the basic representation of graphs and a variety of standard algorithms on graphs. Most problems on graphs require a systematic traversal or search of the graph. The actual method of traversal used can have advantageous structural characteristics which make an efficient solution possible.

A graph G is defined to be a pair (V, E) where V is the set of vertices and E is the set of edges. An edge is defined to be a pair of vertices (v1, v2) joined by the edge. In a directed graph the edge is directed from v1, called the source of the edge, to v2, called the sink of the edge. A graph with directions is called a directed graph.

6.2 GRAPH REPRESENTATION

In practice, the typical representation ...

Get Discrete Mathematics now with the O’Reilly learning platform.

O’Reilly members experience live online training, plus books, videos, and digital content from nearly 200 publishers.