CSC 208-01 (Spring 2023)

Reading: Introduction to Graphs

\[ \newcommand{\set}[1]{\{\, #1 \,\}} \newcommand{\card}[1]{|#1|} \newcommand{\pset}[1]{𝒫(#1)} \newcommand{\falling}[2]{(#1)_{#2}} \]

Recall that a relation models a relationship between objects. Of particular note are binary relations which capture relationships between pairs of objects drawn from the same universe. For example, we might consider:

Binary relationships are ubiquitous in mathematics and computer science, and they all have a similar structure: a relation \(R : 𝒰 × 𝒰\). Can we exploit this structure to talk about all these sorts of relationships in a uniform manner? Is there a set of universal definitions and properties that apply to binary relations?

This is precisely the study of graph theory, the final area of discrete mathematics we’ll examine in this course. Graph theory is really the study of binary relations, although we more commonly think of a graph as a visual object with nodes and edges.

Basic Definitions

Consider the following abstract binary relation over universe \(𝒰 = \set{a, b, c, d, e, f}\).

\[ R = \set{(a, b), (b, c), (c, d), (d, e)}. \]

A graph allows us to visualize these relationships. Here is an example of a such graph for this relation:

A graph for relation R

We call the elements \(a, …, f\) vertices or nodes of the graph. For each related pair of elements, we draw a line called an edge in our graph.

While our graph is simply a graphical representation of our binary relation, we traditionally represent a graph using a slightly different structure. We say that the graph above is \(G = (V, E)\). That is, graph \(G\) is a pair of sets:

Definition (Graph): a graph \(G\) is a pair of sets:

  • \(V\), the set of vertices or nodes of the graph.
  • \(E : V \times V\), the set of edges of the graph.

Because we talk about edges so much, we frequently write the edge \((a, b) \in E\) as \(ab \int E\), i.e., we drop the pair notation and simply write the vertices together.

Exercise (Sketchin’): draw the graph \(G = (V, E)\) where:

  • \(V = \set{a, b, c, d, e, f, g}\).
  • \(E = \set{ag, bg, cg, dg, eg, fg}\).

Variations

The fundamental definition of a graph is a simple riff on a binary relation. We call such graphs simple graphs. However, there exists several variations of graphs that accommodate the wide range of scenarios we might find ourselves in.

Directed versus Undirected Graphs

Because individual relationships are encoded as pairs, the order matters between vertices. For example, the pair \((a, b)\) is distinct from the pair \((b, a)\). In a directed graph or digraph, we acknowledge this fact and distinguish between the two orderings.

For example, consider the following graph \(G = (V, E)\) with

If we consider this graph directed, we would draw it as follows:

A directed graph

Note that the edges are directed edges where the direction is indicated by an arrowhead. If we were to have two vertices be mutually related, i.e., related in both directions, we need two edges, one for each direction. For example, \(c\) and \(d\) are mutually related, so we connect them with two edges \(cd\) and \(dc\).

In contrast, we can consider \(G\) to be undirected where we do not distinguish between the two orderings. Effectively, this means relations are unordered sets rather ordered pairs, but in terms of notation, we still keep \(E : V × V\). If we consider \(G\) to be undirected, we would draw it as follows:

A undirected graph

Here, the edges are undirected, i.e., without arrowheads. Effectively, we treat a single edge pair as relating symmetrically by default, so the edge \(ab\) implies that \(a\) is related to \(b\) and \(b\) is related to \(a\). Because of this, we should not include symmetric pairs in our set of edges. So we should define \(E\) for the above graph as \(E = \set{ab, bc, cd, da}\) where we removed the symmetric pair \(dc\).

When should we employ a directed versus undirected graph? We should employ a directed graph where it is not assumed that our relation is symmetric for every pair of related vertices. For example, a “loves”-style relationship where \(a\) loves \(b\) is not inherently symmetric since \(b\) might not love \(a\). A directed graph allows us to represent this distinction. A directed graph can always represent an undirected graph by explicitly including symmetric edges. Therefore, we can think of an undirected graph as a shortcut where we can avoid writing extras edges if we know that our relation is already symmetric. For example, a “friends”-style relationship is symmetric because \(a\) being friends with \(b\) implies that \(b\) is also \(a\)’s friend.

Self-loops

Like symmetry, we may or may not take reflexivity of a relation for granted. If we do not take this for granted, i.e., some elements are reflexively related but not all of them are, then we might consider introducing self-loops into a graph. For example, consider the following digraph \(G = (V, E)\) with \(E = \set{ab, bc, ca, aa, cc}\).

A graph with self-loops

In this graph, \(a\) and \(c\) are related to themselves, but not \(b\).

Weights and Multi-graphs

Edges encode relations between objects in a graph. We can also carry additional information on these edges dependent on context. Most commonly, we will add numeric weights to our edges, e.g., to capture the distance between cities, or the cost of moving from one state to another. Both directed and undirected graphs can be weighted. As an example, consider the digraph \(G = (V, E)\) with \(E = \set{ab, bc, ca, cd}\).

A weighted graph

We annotate the edges with a weight whose interpretation depends on context. For example, we can see that the edge \(ca\) has weight 5. We represent the weights on our graph formally with an additional structure, a function \(W : E → ℤ\), that maps edges to weight value. The codomain of \(W\) can be whatever type is appropriate for the problem at hand; here we choose integers (\(ℤ\)). For the above graph, we would define our weight function as:

\[\begin{align} W(ab) =&\; 3 \\ W(bc) =&\; 1 \\ W(ca) =&\; 5 \\ W(cd) =&\; -2 \end{align}\]

We can also extend our graphs further by extending \(E\) to be a multiset, a set that tracks duplicate elements. This allows us to express the idea of multiple edges, e.g., with different weights according to \(W\).

Simple Graphs Revisited

Now that we have introduced various variations on a graph, we can finally come back and formally define a simple graph as a graph with no such variations.

Definition (Simple Graph): a simple graph is an undirected, unweighted graph with no self-loops.

In closing, we have many different variations of a graph to consider to capture our domain of interest. In successive readings, we’ll consider various analyses over graphs and problems we might try to solve. The beauty of graph theory is that because graphs are so general, by defining and solving problems in terms of graphs, we can apply our solutions to a whole host of problems!

Exercise (What’s That?, ‡): consider the following formal definition of an abstract graph \(G = (V, E)\) with:

\[\begin{gather*} V = \set{a, b, c, d, e} \\ E = \set{(a, b), (a, c), (a, d), (a, e), (c, d), (c, e), (b, e)} \end{gather*}\]

  1. Draw \(G\).
  2. Instantiate this abstract graph to a real-life scenario. Describe what objects the vertices \(V\) represent and what relationship between objects is captured by \(E\).
  3. Observe that \(c\), \(d\), and \(e\) are mutually connected in this graph, i.e., each vertex has an edge to the other. Interpret the fact that they are mutually connected in your real-life scenario. Is the fact that they are mutually connected have special meaning in the scenario you envisioned?