\[ \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:

- An ordering relationship \((\leq)\) between members of \(\mathbb{N}\).
- A friendship relationship between friends.
- A connectedness relationship between cities by roads or available flights.
- A transition relationship between states in an abstract machine. For example, an idealized traffic light is such an abstract machine where the traffic light switches between â€śgreenâ€ť, â€śyellowâ€ť, and â€śred.â€ť

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:

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*:

- \(V\) is the
*set of vertices*in the graph. Here \(V = \set{a, b, c, d, e, f}\). - \(E\) is the
*set of edges*in the graph. Here \(E = \set{(a, b), (b, c), (c, d), (d, e)}\).

**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

- \(V = \set{a, b, c, d}\).
- \(E = \set{ab, bc, cd, dc, da}\).

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

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:

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}\).

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}\).

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*}\]

- Draw \(G\).
- 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\).
- 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?