Réprésentation

L'objectif de cet exercice est de manipuler les différentes représentations possibles des graphes :

• listes d'adjacence,
• matrice d'adjacence.

1. 1

   Indice

   Initialiser une matrice carrée de zéros puis parcourir chaque liste de voisins pour affecter la valeur 1.
   Écrire une fonction ladj_to_madj_l(g) qui renvoie la matrice d'adjacence correspondant à la liste d'adjacence g. Celle-ci est constituée de 0 (pas d'arête) et de 1 (une arête). Par exemple ladj_to_madj_l([[1, 2], [0], [0]]) renvoie [[0, 1, 1], [1, 0, 0], [1, 0, 0]].
2. 2

   Indice

   Créer une liste de n listes vides puis parcourir la matrice pour ajouter les indices des colonnes non nulles.
   Écrire une fonction madj_to_ladj(g) qui renvoie la liste d'adjacence correspondant à la matrice d'adjacence g. Par exemple madj_to_ladj([[0, 1], [1, 0]]) renvoie [[1], [0]].
3. 3

   Indice

   Créer une matrice de même dimension puis échanger les indices de lignes et de colonnes : $t_{ji}=m_{ij}$.
   Écrire une fonction transpose_m(g) qui renvoie la matrice transposée de la matrice d'adjacence g. Par exemple transpose_m([[0, 1, 0], [0, 0, 1], [0, 0, 0]]) renvoie [[0, 0, 0], [1, 0, 0], [0, 1, 0]].
4. 4

   Indice

   Initialiser une liste de n listes vides puis parcourir chaque sommet et ses voisins pour ajouter le sommet courant.
   Écrire une fonction transpose(g) qui renvoie la liste d'adjacence du graphe transposé correspondant à g. Par exemple transpose([[1], [2], []]) renvoie [[], [0], [1]].