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 books, live events, courses curated by job role, and more from O’Reilly and nearly 200 top publishers.
