The simplest class of graphs is completely defined by a set of vertices and a set of edges. You can think of a vertex as a dot in space and an edge as a line connecting two dots. In this course, we will refer to vertices as nodes because frankly, it’s just simpler to say and type.
Let’s consider a first example:
This is a simple graph. As you can see, each node is labelled with a number which is how we usually keep track of nodes. Labeling nodes with numbers is not obligatory though. You can call your nodes whatever you want as long they are uniquely identifiable (which is why we call the node labels IDs). Sticking with the number labeling, though, we can define the set of nodes more formally by:
\[ N = \{1, 2, 3, 4, 5, 6, 7\} \]
Edges are simply described as pairs of nodes: \(\{a, b\}, \text{where a, b } \in N\). Notice that we use the set notation for an edge here because the order of the nodes in an edge does not play a role (Yet! More on that later…). In this specific case, the set of edges is given by:
\[ E = \{\{1, 3\}, \{1, 5\}, \{1, 7\}, \{2, 4\}, \{2, 6\}, \{3, 5\}, \{3, 6\}, \{4, 5\}, \{6, 7\}\} \]
In summary, the graph is fully described by:
\[ G = (N, E), \text{where N is the set of nodes and E is the set of edges.} \]
Now that we have seen our first graph, let’s take a look at some other ones. This is also a graph:
Obviously, it looks a little different.
And this one looks yet a little different:
But what differentiates these examples? How can we describe graphs in a way that gives us a vocabulary to characterize them in a meaningful way?