Many aspects of computer science, and especially programming can be explained or demonstrated with the aid of graph theory. What follows is a very brief “layman’s introduction” to graph theory.
Nodes and Arcs
Graph theory is based on the notion of Nodes (vertices) and arcs (edges). A node represents some state of the system. It could represent the value of a variable or a particular situation. We generally draw a node as a circle with some label inside of it. In the following figure, three nodes (labeled, 1, 2 and 3) are defined.
Arcs represent a way to transition from one node to the next. They can represent actions that move form one node to another or relationships between nodes. Arcs always begin and end at some node. It’s possible for an arc to begin and end at the same node.
In the following figure, nodes 1, 2 and 3 of the graph have been joined by arcs labeled a and b.
An example explanation might be that each node represents a person where nodes 1 and 2 “know” each other and nodes 1 and 3 “know” each other. However, nodes 2 and 3 have not yet been introduced.
Arc can also have a direction to them. This is indicated by an arrow head on one or both of the ends of the arc. A graph with directions to the arcs is called a directed graph. Directed graphs can be used to show a precedence relationship (e.g., which comes first?) or causal relationships (which node “causes” which other node).
In the following figure, each node represents a CIS course at Baruch College. The direction of the arrows indicates which courses are pre-requisites.
In this example, it is clear that a student must take (and pass!) CIS 2200 before he or she can take either CIS 3100 or CIS 3500.
A cycle occurs when one can start at a node and follow a path of arcs that lead back to the starting node. A cycle is sometimes called a circuit. We can write a cycle in terms of the nodes that are visited. For example, the following graph shows the cycle: 1 -> 3 -> 1
That is, by starting at node 1 and following arc a, then following arc c, we wind up back at node 1 again. Therefore, we say that this graph has a cycle.
It is possible for an arc to start and end at the same node as in the following example:
Here arc c is a directed arc that begins and ends at node 1. This graph also has a cycle: 1 -> 1
A graph that does not contain any cycles is called acyclic. The following is an example of an acyclic graph:
From the perspective of a node, we can view an arc as either incoming or outgoing. An incoming arc is pointing to the node. An outgoing arc is pointing away from the node. In the above figure: Node 1 has two outgoing arcs (a and d), and one incoming arc (b). Node 2 has two outgoing arcs (b and c), but no incoming arcs. Node 3 has no outgoing arcs and three incoming arcs (a, c and d).
A node with no incoming arcs but one or more outgoing arcs is called a source. A node with no outgoing arcs but one or more incoming arcs is called a sink.