Introduction to Graph Theory - Part 2

The graphs that we have met up to now have all been undirected graphs in the sense that the edges have no orientation. In this section we extend the notion of a graph to include graphs in which “edges have a direction”. These kind of graphs are known as directed graphs, or digraphs for short. As shown in the diagram below the direction of an edge is defined so that movement between two vertices is only possible in the specified direction. The terminology for digraphs is essentially the same as for undirected graphs except that it is commonplace to use the term arc instead of edge. Digraphs can be used to model real-life situations such as flow in pipes, traffic on roads, route maps for airlines and hyperlinks connecting web-pages. We have actually encountered the concept of a digraph before in an earlier unit when we looked at relations on sets. In Section 3.3 of that unit, which was optional, we described how a relation R could be represented diagrammatically by a digraph as an alternative to using an arrow diagram or a matrix.

Added By:	Justin Bradley
Date Added:	21 Jul 2017 10:04
Name:
Viewing permissions:	World
URL:	http://hub.edshare.ac.uk/id/eprint/4667
Downloads & Views

Actions (login required)

View Item