7  Graph theory

A graph is a pair \(G = (X, E)\) consisting of a finite non-empty set \(X\), and a set \(E\) of pairs of elements of \(X\). The elements of \(X\) are the vertices of the graph \(G\), those of \(E\) are the edges of the graph \(G\). A graph is oriented if the edges have a direction, i.e., if the pairs of elements of \(E\) are ordered lists such that \((i,j) \in E\) is not equivalent to \((j,i)\in E\). Here only undirected graphs, i.e., whose pairs of elements of \(X\) are unordered sets (\((i,j)\in E\)), are considered.

For example, the complete graph with \(n\) vertices \(K_n\) is defined as the graph of vertices \(X = \{1,2,\dots,n\}\) and of edges being the two-element of the power set of \(X\). In particular, \(K_4 = (X,E)\), where \(X=\{1,2,3,4\}\) and \(E = \big\{ \{1,2\}, \{1,3\}, \{1,4\}, \{2, 3\}, \{2, 4\}, \{3, 4\} \big\}\).

NoteConcepts covered
  • undirected graphs
  • graphs as dictionaries
  • use of frozensets
  • adjacency matrix
  • search for paths and triangles
  • recursive function

Exercise 7.1 - Graphs as dictionaries

One way to represent a graph \(G\) is with a dictionary whose keys are the vertices and the value associated to each key \(x \in X\) is a set containing the neighbors of \(x\).

a. Construct the following graphs in dictionary form:

b. Write a function complete(n) that constructs the complete graph \(K_n\) as a dictionary.

c. A graph given as a dictionary contains the information several times. Write a function correct(graph) to add the missing elements of an improperly defined graph so that for any vertex x, if y belongs to graph[x], then y is also a key and x belongs to graph[y]. Test this function, in particular, on the improperly defined graph {1:{3,4,2},3:{2}}.

d. Write a function that returns the set (type set) of all edges of a graph represented by a dictionary.

Sets are mutable and therefore not hashable.

e. ! Write a function to determine whether two vertices are connected by a path or not and return the path if yes.

Use a recursive function.

f. ! Write a function that returns all paths between two vertices (without cycles).

Exercise 7.2 - Triangles in a graph

A triangle in a graph is a set of three vertices connected by three edges. Finding and analyzing triangles in a graph is important for understanding its structure.

a. Determine mathematically the number of subsets of cardinal three that a set of vertices \(X\) has. Is it reasonable to iterate over these elements?

b. Write a function that returns the set of all triangles in a graph.

To each graph \(G=(X,E)\) corresponds a unique symmetric matrix \(A\) of size \(n \times n\) with \(n=|X|\) defined by:

\[A_{ij}=\begin{cases} 1\,, & \text{if}\;\{i,j\}\in E\,,\\ 0\,, & \text{if}\;\{i,j\}\notin E\,. \end{cases}\]

This matrix is called the adjacency matrix of graph \(G\).

c. Define a function that returns the adjacency matrix of a graph.

Be careful that the vertices are not necessarily indexed by integers between 0 and \(n\) in the dictionary.

d. Define a function having as argument an adjacency matrix and returning the corresponding graph as a dictionary.

e. Using the adjacency matrix \(A\) and the matrix \(B=A^2\), write a function returning the set of triangles of a graph.

f. Using the adjacency matrix \(A\), write a function computing the number of triangles.

Interpret the entries of the matrix \(A^n\).

Exercise 7.3 - Module NetworkX !!

Many graph theory algorithms are implemented in the NetworkX module, see the documentation here.

a. Follow the NetworkX tutorial available here.

b. Analyze one of the downloadable graphs at: https://github.com/gephi/gephi/wiki/Datasets or https://snap.stanford.edu/data/.