## Video transcripts

Hi, and welcome to this lesson! Today, we’re going to introduce some basic definitions related to graphs.

### Basic definitions

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.

### Standard graphs

Some graphs are very useful because they can appear in many situations.

Trees are connected graphs that are cycle-free.

### Concluding words

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:

### Theorem

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 .

### Proof

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 .

## To go further

- Graph theory for optimal Pacman game: This is very close to what we will be doing in PyRat.
- A course on spectral graph theory: This probably won’t be useful for winning the challenge, but it shows the strong connection between graph theory and linear algebra.