Hi, and welcome to this lesson! Today, we’re going to introduce some basic definitions related to graphs.
Graph theory is probably one of the most common sub-fields of discrete mathematics. Graphs are mathematical structures that are used to represent the relationships between objects.
Mathematically, a graph is composed of a finite set of vertices, , and a set of edges, . We can therefore refer to a graph as a couple composed of and .
A graph is often depicted using circles for vertices and lines for edges.
That’s right. There are multiple ways to define graphs. In the simplest case, edges convey information about which pairs of vertices are connected, and which are not. This means that becomes a set of pairs of vertices.
As you can see, this is a simple, effective way to visualize a graph.
But it might also be misleading, because the creation of a figure like this requires you to make arbitrary decisions about the coordinates of vertices and the forms of lines.
In some cases, edges can be directed, which means that a vertex can be connected to a vertex , even if is not connected to . In such cases, edges are made up of couples of vertices, such as, for example, .
Couples are more informative than pairs because the order of vertices in the couple is meaningful.
The adjacency matrix and weighted graphs
You should note that the adjacency matrix of a graph is always symmetric.
Adjacency matrices can be generalized to take values other than 0s and 1s, which allows weighted graphs to be defined.
Weighted graphs are particularly useful when edges represent distances or delays between vertices, because values in the adjacency matrix can be used to indicate the corresponding quantities.
Paths and geodesic distances
Paths are often confused with walks. A walk is a sequence of vertices, such that any two consecutive vertices form an edge in the graph. The difference is that, in a path, an edge cannot appear twice.
A cycle in a graph is a path in which the extremities are identical.
The length of a path is the length of the sequence of edges. For weighted graphs, the length corresponds to the sum of the weights.
Finally, a graph is said to be connected if any two vertices there exists a path having these vertices as extremities.
Some graphs are very useful because they can appear in many situations.
Trees are connected graphs that are cycle-free.
Thank you for your attention! I have really enjoyed talking about graph theory with you today.
Counting walks between two vertices
An interesting problem in graph theory is to count the number of possible walks of a fixed length between two chosen vertices.
For simplicity, consider a graph with no weights or directed edges. Its adjacency matrix therefore contains only 1s and 0s. The following result holds:
Let denote the matrix power of a matrix , and let us note the entry of matrix which is at intersection of its row and its column.
The number of walks of length from vertex to vertex is equal to .
In order to prove this theorem, we proceed by induction, i.e., we are going to show two things :
That this is true under the initial conditions;
That if this is true for power (for any ), then it is true for power ).
1. Initial conditions
Case 1 – : The single walk of length 1 to go from to is to take edge .
Case 2 – : There cannot be any walk of length 1 as there is no direct edge between and .
2. Inductive step
For the purpose of induction, assume theorem is true for power .
A walk of length from to can be seen as a sequence of two walks:
A walk of length from to some vertex ;
A walk of length 1 from to .
As a consequence, the number of walks of length from to is equal to the sum of the number of walks of length from to , each multiplied by the number of ways to go from that to in one move. Mathematically, this is given by the following equation:
Since this is exactly the formulation of the dot-product used in matrix multiplications, this concludes that gives the number of walks from to .