Why do we have at least three definitions of a graph in math?

Question

Definition 1 - 2 sets and function

Definitioin 2 - 1 set and 1 family

Definition 3 - 1 relation

Why do we need such a diversity? Are some of these definitions old-fashioned or all of them have their pros and cons?

Answer 1

Undirected graphs and directed graphs

The third definition differs from the first two because it is about directed graphs, while the first two define undirected graph. We care about directed graphs and undirected graphs because they are adapted to different situations and to solving different problems.

You can think of directed graphs and undirected graphs as two different objects.

In general, undirected graphs are somewhat easier to reason about, and most often if someone mentions a "graph" without precision, they mean an undirected graph.

Named edges and incidence function

The first two definitions are pretty much equivalent.

The first definition, with (V, E, ѱ) gives "names" to vertices (elements of V) and names to edges (elements of E), and uses an "incidence function" ѱ to tell you which edge in E corresponds to which pair of vertices of V.

The second definition uses only (V', E') and no ѱ. I am calling them V' and E' instead of V and E to make a distinction from the first definition. Here the vertices have "names", they are the elements of V'; but the edges don't really have individual names, and E' is defined as a subset of the set of undirected pairs of V. Therefore an edge is an undirected pair of elements of V'.

Here is an example of a graph:

By the first definition:

• V = {a, b, c, d};
• E = {1, 2, 3};
• ѱ : E -> {unordered pairs of V}
• • 1 -> ab
• • 2 -> ac
• • 3 -> cd.

By the second definition:

• V' = {a, b, c, d}
• E' = {ab, ac, cd}.

As you can see, V' = V, and E' is the image of E by ѱ.

If you don't care about "names" for the edges, the second definition is somewhat shorter. But which one you use really doesn't matter; the theorems you might prove with one definition will be equivalent to the theorems you can prove for the other definition. The difference between the two definition is just a set theory nitpick of what "edge" means: is it a pair of elements of V, or an element of another set which is mapped to a pair of elements of V by a function? Note that the function ѱ is a bijection between the two sets E and E', so really E and E' are two different names for the same set.

Algorithms, programming languages, and representations of graphs

If you ever have to code an algorithm using a graph in your favourite programming language, you will have to decide how to represent the graph using variables and arrays and all the data structures you are used to.

For the vertices, most often, people use V = {0, 1, 2, ..., n-1} where n is the number of vertices. This is convenient because it means you can use the vertices as indices for an array.

For the edges, sometimes we encode E using an vertex-vertex incidence matrix of size n*n with a 1 in cell i,j to indicate an edge between vertices i and j and a 0 in cell i,j to indicate no edge. Here is the incidence matrix for the graph above (I replaced a,b,c,d with 0,1,2,3 as the names for the vertices):

  0 1 2 3
0 0 1 1 0
1 1 0 0 0
2 1 0 0 1
3 0 0 1 0

Sometimes we encode E using an array of lists: an array of size n, where cell i contains the list of indices of vertices which are neighbours of vertex i. Here is the array of lists for the same graph:

0: 1,2
1: 0
2: 0,3
3: 2

Those two representations are closer to the second definition, since the edges don't have names; we just care about whether each pair of vertices is an edge or not.

Recently I had to write a C++ program where it was very important for me to number the edges, because I wanted to be able to use them as indices of a matrix. Thus I had V = {0, 1, 2, ..., n-1}; E = {0, 1, 2, ..., m-1}; and then I used an std::map<int, std::pair<int, int>> to map the edge indices to pairs of vertex indices. This representation was closer to your first definition, which an std::map for ѱ. Note that I had to make a choice between mapping edge indices to pairs of vertex indices, or mapping pairs of vertex indices to edge indices. Had I felt the necessity, I could even have used both. The first definition doesn't care, because ѱ is a bijection, so mathematicians can use ѱ and its inverse function ѱ^-1 indifferently; but the data structure std::map is not a mathematical function, and inversing it might take time.

Conclusion

Both definitions are equivalent, and it really doesn't matter which one you use. But if you need to code algorithms using graphs, take some time to consider different representations of graphs and which one will make your algorithm the most efficient.