8 Théorie des graphes

Un graphe est un couple $ G = (X, E) $ constitué d'un ensemble $ X $, non vide et fini, et d'un ensemble $ E $ de paires d'éléments de $ X $. Les éléments de $ X $ sont les sommets du graphe $ G $, ceux de $ E $ sont les arêtes du graphe $ G $. Un graphe est orienté si les arêtes ont une direction, c'est-à-dire si les couples d'éléments de $ E $ sont des listes ordonnées telles que $ (i,j) \in E $ n'est pas équivalent à $ (j,i)\in E $. Ici seuls des graphes non orientés, c'est-à-dire dont les paires d'éléments de $ X $ sont des ensembles non ordonnés ($ \{i,j\} \in E $), sont considérés.

Par exemple, le graphe complet à $ n $ sommets $ K_n $ est le graphe de sommets $ X = {1,2,\dots,n} $ ayant comme arêtes les parties à deux éléments de $ X $. En particulier, $ K_4 = (X,E) $ où $ X=\{1,2,3,4\} $ et $ E = \big\{ \{1,2\}, \{1,3\}, \{1,4\}, \{2, 3\}, \{2, 4\}, \{3, 4\} \big\} $.

Concepts abordés:

graphes non orientés
représentation comme dictionnaire
utilisation des frozensets
matrice d'adjacence
recherche de chemins et de triangles
fonction récursive

Exercice 8.1: Graphes comme dictionnaires

Une façon de représenter un graphe $ G $ est de le faire avec un dictionnaire dont les clefs sont les sommets, et la valeur associée à chaque clef $ x \in X $ est un ensemble contenant les voisins de $ x $.

a) Construire sous forme de dictionnaire les graphes suivants:

b) Écrire une fonction complet(n) qui construit comme dictionnaire le graphe complet $ K_n $.

c) Un graphe donné sous forme de dictionnaire contient l'information plusieurs fois. Écrire une fonction corriger(graphe) permettant de rajouter les éléments manquants de sorte que pour tout sommet x, si y appartient à graphe[x], alors y est aussi une clef et x appartient à graphe[y]. Tester cette fonction.

d) Écrire une fonction qui retourne l'ensemble (type set) de toutes les arêtes d'un graphe représenté par un dictionnaire.

Indication

Les ensembles sont mutables et donc pas hashables.

e) ! Écrire une fonction permettant de déterminer si deux sommets sont connectés par un chemin ou non et qui retourne le chemin si oui.

Indication

Utiliser une fonction récursive.

f) ! Écrire une fonction qui retourne tous les chemins entre deux sommets (sans les cycles).

Exercice 8.2: Triangles dans un graphe

Un triangle dans un graphe est un ensemble de trois sommets reliés entre eux par trois arêtes. La recherche et l'analyse des triangles dans un graphe sont importantes pour comprendre sa structure.

a) Déterminer mathématiquement le nombre de sous-ensembles de cardinal trois que possède un ensemble de sommets $ X $.

b) Écrire une fonction retournant l'ensemble des triangles d'un graphe.

À chaque graphe $ G=(X,E) $ correspond une unique matrice $ A $ symétrique de taille $ n \times n $ avec $ n=|X| $ définie par: $$ A_{ij}=\begin{cases} 1\,, & \text{si}\;\{i,j\}\in E\,,\\ 0\,, & \text{si}\;\{i,j\}\notin E\,. \end{cases} $$ Cette matrice est appelée la matrice d'adjacence du graphe $ G $.

c) Définir une fonction retournant la matrice d'adjacence d'un graphe.

Indication

Faire attention que les sommets ne sont pas forcément indexés par des entiers compris entre 0 et $ n $ dans le dictionnaire.

d) Définir une fonction ayant pour argument une matrice d'adjacence et retournant le graphe correspondant sous forme d'un dictionnaire.

e) En utilisant la matrice d'adjacence $ A $ et la matrice $ B=A^2 $, écrire une fonction retournant l'ensemble des triangles d'un graphe.

f) En utilisant la matrice d'adjacence $ A $, écrire une fonction calculant le nombre de triangles.

Indication

Interpréter les entrées de la matrice $ A^n $.

Exercice 8.3: !! Module NetworkX

De nombreux algorithmes de la théorie des graphes sont implémentés dans le module networkX, voir la documentation ici.

a) Suivre le tutoriel de networkX disponible ici.

b) Analyser un des graphes téléchargeables à l'adresse: https://github.com/gephi/gephi/wiki/Datasets ou https://snap.stanford.edu/data/.