Let \(A,B\) be sets. A relation from \(A\) to \(B\) is a subset \(R\subseteq A\times B\) of the Cartesian product \(A\times B\text{.}\) A relation from a set \(A\) to itself is called a relation on the set \(A\). Given a relation \(R\) from \(A\) to \(B\text{,}\) the inverse relation to \(R\text{,}\) denoted \(R^{-1}\text{,}\) is the relation from \(B\) to \(A\) given by
Given a relation \(R\) on a set \(A\text{,}\) a directed graph is a figure that illustrates \(R\text{.}\) Elements of \(A\) are depicted as dots, and \((a,a')\) in \(R\) is depicted by a segment of a line or an arc that starts at \(a\text{,}\) ends at \(a'\text{,}\) and has an arrow pointing from \(a\) to \(a'\text{.}\)
A (simple) graph is a pair \(G=(V,E)\text{,}\) where \(V\) is a set and \(E\) is a set of subsets of \(V\text{,}\) where every element of \(E\) has two elements. An element of \(V\) is called a vertex and an element of \(E\) is called an edge. The set \(V\) is called the set of vertices of the graph \(G\text{,}\) and the set \(E\) is called the set of edges of \(G\text{.}\)
One can also define graphs that allow loops, that is, edges that connect a vertex to itself. Further generalizations of graphs allow multiple edges that connect the same pair of vertices. In this course, the term “graph” will always refer to a simple graph, as defined above. 1
The definition of graph given in [1] uses the word “pair” in the definition of an edge. Unfortunately, this introduces ambiguity as to whether loops are allowed as edges. In mathematics, the word “pair” usually denotes an ordered list \((x,y)\text{.}\) By default, it is allowable that the objects \(x\) and \(y\) may be equal. We avoid this ambiguity by not using the word “pair” in our definition of graph.
