image
Graph Theory Lessons

rule

previous index next Lesson 31: Directed Graphs

So far we have considered having an edge from a vertex v1 to a vertex v2 to be the same as having an edge from v2 to v1. The edge was therefore defined by an unordered pair of vertices. If we want to consider direction, we need to use an ordered pair to define our edges. We will call such edges directed edges. In this case an edge from v1 to v2 is different from an edge from v2 to v1. We shall use an arrow to represent the direction. A graph that has directed edges is called a directed graph or sometimes just a digraph. The number of edges that end at a vertex is called the in-degree of that vertex while the number of edges that start at a vertex is the out-degree. In the figure 31.1, for example we have an edge from vertex i to vertex j if i divides j.

Fig 31.1

Questions:
  1. What relationship do you think there is between the sum of the in-degrees of all the vertices of a graph and the sum of the out-degrees?

Java Web Start Activity:
We can consider Euler circuits in directed graphs. In the Java Web Start application below draw a directed graph in the right pane and if there is a directed Euler circuit or path you will see it drawn on the left pane. To delete a directed edge drag the mouse in the same direction as the edge you are trying to delete.

Java Web Start Application 31.1: Directed Euler circuits

Questions:
  1. Find a necessary condition for a directed graph to have an Euler circuit.
  2. Find a necessary condition for a directed graph to have an Euler path.

Java Web Start Activity:
We can consider Hamilton circuits in directed graphs. In the Java Web Start application below draw a directed graph in the right pane and if there is a directed Euler circuit or path you will see it drawn on the left pane. To delete a directed edge drag the mouse in the same direction as the edge you are trying to delete.

Java Web Start Application 31.2: Directed Hamilton circuits

Answers


© C. Mawata