Chapter 3: Graphs

A graph represents pairwise relationships between objects and consists of nodes and edges. In order to represent asymmetric relationships between ends of a graph, we would use a directed graph, which consists of a set of nodes and a set of directed edges. It is important to note that edges have a head and a tail, positions which are not interchangeable. We can also have undirected graphs which would refer to a graph that is not directed, while we will usually just call a “graph”. The following are some examples of graphs:

  • transportation networks
  • communication networks
  • information networks
  • social networks
  • dependency networks

When working with graphs, it is frequently necessary to be able to traverse a sequence of nodes and edges. Another important term here is a path, which is a sequence of nodes such that each consecutive pair of nodes is joined by an edge. There can also be a cycle in a graph, which means the path “cycles back” to its initial node. A graph can be connected, meaning every pair of nodes are connected by paths. To find the distance between two nodes, we consider the number of edges in the path from node 1 to node 2.

An undirected graph (or simply, graph) can be a tree as well. This means that a graph is connected and does not contain a cycle. There are two important facts about trees:

  • Every //n//-node tree has //n// - 1 edges.
  • Given //G//, an undirected graph with //n// nodes, any two of the following implies the third:
        i. //G// is connected
       ii. //G// does not contain a cycle
      iii. //G// has //n// - 1 edges