C17 Graphes ¶

"Bad programmers worry about the code. Good programmers worry about data structures and their relationships. "
L. Torvalds
(lwn.net)

Cours¶

Support de cours chapitre 17

Attention

Ce diaporama ne vous donne que quelques points de repères lors de vos révisions. Il devrait être complété par la relecture attentive de vos propres notes de cours et par une révision approfondie des exercices.

Travaux dirigés¶

Fiche de TD17

Travaux pratiques¶

Exercice 1 : Matrice d'adjacence en C¶

Dans cet exercice, on s'intéresse à la représentation par matrice d'adjacence en C, on rappelle la structure de données vue en cours :

Définition de la structure de données

#define NMAX 100                 // nombre maximal de sommets
typedef bool graphe[NMAX][NMAX]; // La matrice d'adjacence

Ecrire une fonction d’initialisation de prototype void init_graphe(graphe g, int size) qui initialise un graphe de taille size en remplissant la matrice avec des valeurs false
Ecrire une fonction de création d'un arc dans un graphe de prototype void cree_arete(graphe g, int i, int j) qui permet de créer une arête de entre les sommets i et j

On donne ci-dessous une fonction permettant de visualiser un graphe :

Fonction de visualisation

// Visualisation du graphe g de taille n
void visualise(graphe g, int n)
{
    FILE *writer = fopen("temp.gv", "w");
    fprintf(writer, "graph mygraph {\n");
    for (int i = 0; i < n; i++)
    {
        fprintf(writer, "%d\n", i);
        for (int j = i + 1; j < n; j++)
        {
            if (g[i][j])
            {
                fprintf(writer, "%d -- %d\n", i, j);
            }
        }
    }
    fprintf(writer, "}\n");
    fclose(writer);
    system("xdot temp.gv &");
}

Créer et visualiser le graphe suivant :

graph LR
A(("0"))
B(("1"))
C(("2"))
D(("3"))
E(("4"))
F(("5"))
G(("6"))
A --- B
A --- C
B --- D
C --- F
C --- G
E --- G
A --- E
D --- F
G --- F
B --- C

Ecrire une fonction qui renvoie le degré d'un sommet dans un graphe
Ecrire une fonction qui renvoie un tableau de dimension NMAX, contenant les voisins d'un sommet i ce tableau contiendra une sentinelle -1 indiquant la fin de la liste des sommets. Par exemple, sur le graphe représenté ci-dessus pour le sommet 0, la fonction renvoie un tableau de taille NMAX dont les quatre premiers éléments sont 1,2,4 et -1.
Ecrire une fonction complet qui prend un graphe et sa taille effective en argument et ajoute tous les arcs possibles dans ce graphe.
Ecrire une fonction cycle qui prend un graphe et sa taille effective en argument et en fait un graphe cycle

Exercice 2 : Matrice d'adjacence en OCaml¶

Reprendre l'exercice précédent en OCaml en utilisant la structure de données vue en cours et rappelée ci-dessous :

Définition de la structure de données

type graphe = {
  taille : int; 
  madj : bool array array};;

La fonction de visualisation pour OCaml est donnée ci-dessous :

Fonction de visualisation

let visualise g =
  let n = (g.taille - 1) in
  let writer = open_out "temp.gv" in
  output_string writer "graph mygraph {\n";
  for i=0 to n do
    Printf.fprintf writer "%d\n" i;
    for j=i+1 to n do
      if g.madj.(i).(j) then Printf.fprintf writer "%d -- %d\n" i j;
    done;
  done;
  output_string writer "}\n";

Pour la question 5., on pourra renvoyer la liste des sommets et pas un tableau.

Exercice 3 : Matrice d'adjacence dynamique linéarisée en C¶

Reprendre l'exercice 1 en C en utilisant la structure de données d'une matrice linéarisée allouée en mémoire lorsque la taille est connue :

Définition de la structure de données

struct graphe
{
    int taille; // |S|
    bool *madj; // matrice linéarisée (à allouer)
};
typedef struct graphe graphe;

On rappelle qu'avec cette structure, il devient inutile de passer la taille du graphe en argument puisqu'on y accède directement via le champe taille.

Aide

Pour rappel :

La valeur de \(M_{ij}\) se situe à l'indice \(i \times |S| + j\) dans la matrice linéarisée
L'indice \(k\) dans la matrice linéarisée correspond à la ligne \(\left\lfloor \dfrac{k}{|S|} \right\rfloor\) et à la colonne \(k \mod |S|\) de la matrice d'adjacence

On donne la fonction de visualisation adaptée à cette nouvelle structure

Fonction de visualisation

// Visualisation du graphe g
void visualise(graphe g)
{
    int n = g.taille;
    FILE *writer = fopen("temp.gv", "w");
    fprintf(writer, "graph mygraph {\n");
    for (int i = 0; i < n; i++)
    {
        for (int j = i + 1; j < n; j++)
        {
            if (g.madj[i * n + j])
            {
                fprintf(writer, "%d -- %d\n", i, j);
            }
        }
    }
    fprintf(writer, "}\n");
    fclose(writer);
    system("xdot temp.gv &");
}

Exercice 4 : Listes d'adjacence en C¶

On rappelle la structure de données vues en cours permettant de représenter un graphe par ses listes d'adjacence en C :

Définition de la structure de données

#define NMAX 100 // nombre maximal de sommets
// graphe[i][0] contient le degré du sommet i
// graphe[i][1..] est la liste d'adjacence du sommet i
typedef int graphe[NMAX][NMAX];

Attention

On rappelle que dans cette représentation la première colonne est le degré du sommet (et pas un numéro de sommet adjacent) A titre d'exemple, le graphe

graph LR
A(("0"))
B(("1"))
C(("2"))
D(("3"))
A --- B
A --- C
A --- D
B --- C

est représenté par le tableau d'entiers \(\begin{pmatrix} 3 & 1 & 2 & 3 \\ 2 & 0 & 2 & .\\ 2 & 0 & 1 & . \\ 1 & 0 & . & . \\ \end{pmatrix}\) où . indique une valeur non utilisée du tableau.

Ecrire une fonction d’initialisation de prototype void init_graphe(graphe g, int size) qui initialise un graphe de taille size en affectant le degré 0 à tous les noeuds.
Ecrire une fonction de création d'un arc dans un graphe de prototype void cree_arete(graphe g, int i, int j) qui permet de créer une arête de entre les sommets i et j

On donne ci-dessous une fonction permettant de visualiser un graphe :

Fonction de visualisation

void visualise(graphe g, int n)
{
    FILE *writer = fopen("temp.gv", "w");
    fprintf(writer, "graph mygraph {\n");
    for (int i = 0; i < n; i++)
    {
        fprintf(writer, "%d\n", i);
        for (int j = 1; j <= g[i][0]; j++)
        {
            if (i > g[i][j])
            {
                fprintf(writer, "%d -- %d\n", i, g[i][j]);
            }
        }
    }
    fprintf(writer, "}\n");
    fclose(writer);
    system("xdot temp.gv &");
}

Créer et visualiser le graphe suivant :

graph LR
A(("A"))
B(("B"))
C(("C"))
D(("D"))
E(("E"))
F(("F"))
G(("G"))
A --- B
A --- C
G --- E
C --- D
D --- F
B --- E
E --- F
A --- G

Ecrire une fonction qui affiche la matrice d'adjacence du graphe.
Ecrire une fonction qui renvoie le degré d'un sommet dans un graphe
Ecrire une fonction existe de prototype bool existe(graphe g, int i, int j) qui renvoie true si il y a un arc entre les sommets i et j et false sinon.
Ecrire une fonction qui renvoie un tableau contenant les voisins d'un sommet i.

Exercice 5 : Listes d'adjacence en OCaml¶

On rapelle la structure de données vue en cours permettant de représenter un graphe par liste d'adjacence en OCaml :

Définition de la structure de données

type graphe = {
  taille : int;
  ladj : int list array};;

Ecrire une fonction d'initialisation int -> graphe qui renvoie un graphe d'ordre n n'ayant aucune arête
Ecrire une fonction qui permet de créer une arête dans un graphe.

La fonction de visualisation pour OCaml est donnée ci-dessous :

Fonction de visualisation

    let visualise g =
      let n = (g.taille - 1) in
      let writer = open_out "temp.gv" in
      output_string writer "graph mygraph {\n";
      let rec aux i wl =
        match wl with
        | [] -> ()
        | h::t -> if h>i then (Printf.fprintf writer "%d -- %d\n" i h); aux i t
      in
      for i=0 to n do
        Printf.fprintf writer "%d\n" i;
        aux i g.ladj.(i);
      done;
      output_string writer "}\n";
      close_out writer;
      ignore (Sys.command "xdot temp.gv &");;

Créer et visualiser le graphe suivant :

graph LR
A(("A"))
B(("B"))
C(("C"))
D(("D"))
E(("E"))
F(("F"))
G(("G"))
A --- B
A --- C
G --- E
C --- D
D --- F
B --- E
E --- F
A --- G

Ecrire une fonction qui affiche la matrice d'adjacence du graphe.
Ecrire une fonction qui renvoie le degré d'un sommet dans un graphe
Ecrire une fonction existe de prototype bool existe(graphe g, int i, int j) qui renvoie true si il y a un arc entre les sommets i et j et false sinon.
Ecrire une fonction qui renvoie une liste contenant les voisins d'un sommet i.

Exercice 6 : Listes chainées d'adjacence en C¶

Comme indiqué en cours, on peut représenté les listes d'adjacence en C à l'aide d'un tableau de liste chainées. Reprendre les questions de l'exercice précédent à l'aide de cette nouvelle représentation.

struct maillon{
    int valeur;
    struct maillon* suivant;};
typedef struct maillon maillon;
typedef maillon* liste;

struct graphe{
    int taille;
    liste* ladj;};
typedef struct graphe graphe;

Pour réviser la structure de liste chainées, on pourra revenir si besoin sur cet exercice

On donne aussi pour cette représentation une fonction de visualisation !

Langagec

void visualise(graphe g)
{
    FILE *writer = fopen("temp.gv", "w");
    fprintf(writer, "graph mygraph {\n");
    maillon * mc;
    int n = g.taille;
    for (int i=0; i<n; i++)
    {
        mc = g.ladj[i];
        while (mc!=NULL)
        {
            if (i>mc->valeur) {fprintf(writer,"%d -- %d\n",i,mc->valeur);}
            mc=mc->suivant;
        }
    }
    fprintf(writer, "}\n");
    fclose(writer);
    system("xdot temp.gv &");
}

Exercice 7 : Graphes orientés¶

Note

Afin d'adapter les fonctions de visualisations au cas des graphes orientés, il suffit d'apporter les modifications suivantes :

modifier la ligne écrivant l'entête graph mygraph dans le fichier dot en digraph mygraph
modifier les arcs entre les sommets en -> (au lieu de --)

Dans le langage (C ou Ocaml) et avec la représentation de votre choix (matrice ou listes d'adjacence), représenter un graphe orienté et écrire sur le type graphe les fonctions suivantes :

Test d'existence d'un arête
Ajout d'un arête.
Calcul du degré sortant d'un sommet.
Obtention de la liste des successeurs d'un sommet.
Calcul du degré entrant d'un sommet.
Obtention de la liste des prédécesseurs d'un sommet.

Exercice 8 : Triangles dans un graphe¶

On considère un graphe non orienté \(G=(S,A)\) et on supposera que les sommets sont indexés par les entiers à partir de 0. On dit que \(\{i,j,k \}\) est un triangle de \(G\) si \(ij\), \(jk\) et \(kj\) sont dans \(A\). Les fonctions demandées sont à écrire en OCaml et on supposera dans toute la suite de l'exercice, qu'on représente les graphes par listes d'adjacence :

type graphe = {
  taille : int;
  ladj : int list array};;

Donner le nombre de triangles d'un graphe complet à \(n\) sommets.
Ecrire une fonction complet : int -> graphe qui renvoie le graphe complet à n sommets.
En utilisant les aspects impératifs du langage (boucles et références), écrire une fonction triangles : graphe -> (int*int*int) list qui renvoie la liste des triangles du graphe, en utilisant l'algorithme qui consiste pour chaque triplet \((i,j,k) \in \{0,\dots,|S|-1\}^3\) à tester s'il s'agit ou non d'un triangle.
On souhaite maintenant écrire une version de la fonction triangles sans utiliser les aspects impératifs du langage.
1. Ecrire une fonction sous_liste : 'a list -> int -> 'a list list qui prend en argument une liste lst et un entier n et renvoie toutes les sous listes de longueur n de lst. Par exemple sousliste [0; 1; 2; 3] 3 renvoie [[0; 1; 2]; [0; 1; 3]; [0; 2; 3]; [1; 2; 3]]
  
  Aide
  
  On pourra procédér par correspondance de motif sur lst et n et utiliser le fait qu'une sous liste de longueur n de lst est soit une sous liste de longueur n de la queue de lst, soit la tête de lst suivie d'une sous liste de longueur n-1 de la queue de lst.
2. En utilisant la question précédente et List.filter écrire une version de triangles qui n'utilise ni boucles ni références.
Tester vos fonctions sur le graphe à 1000 sommets représenté par le fichier ci-dessous (sur chaque ligne, se trouve un arc donné sous la forme de ses deux extémités séparé par un caractère espace.)

graphe.txt Vérifier votre réponse :
Une autre possibilité pour déterminer les triangles d'un graphe et de parcourir l'ensemble \(A\) des arêtes, pour chaque arête \(ij\) on cherche alors l'intersection des listes d'adjacences de \(i\) et de \(j\). Comparer les complexités des deux méthodes si on suppose que l'intersection est calculée en temps linéaire du nombre de sommets.
Ecrire une fonction intersection int list -> int list -> int list qui calcule en temps linéaire l'intersection de deux listes en les supposants triées.
Ecrire une nouvelle version de la fonction triangles qui utilise le parcours des arêtes.

Exercice 9 : Coloration gloutonne¶

Dans toute la suite de l'exercice, on considère un graphe \(G=(S,A)\) où chaque sommet est identifié par un entier de \(\{0, \dots, |S|-1 \}\). Les fonctions sont à écrire en OCaml et et on supposera ce graphe représenté par liste d'adjacence :

type graphe = {
  taille : int;
  ladj : int list array};;

La coloration d'un graphe consiste à attribuer une couleur à chacun des sommets de ce graphe de façon à ce que deux sommets adjacents soient de deux couleurs différentes. On s'intéresse généralement à une coloration utilisant un minimum de couleurs.

En donnant un exemple montrer que la coloration d'un graphe à \(n\) sommets peut nécessiter \(n\) couleurs.
Ecrire une fonction adjacent : graphe -> int -> int -> bool qui prend en argument un graphe ainsi que deux sommets et renvoie true si ces deux sommets sont adjacents et false sinon.
On propose de représenter la coloration d'un graphe à \(n\) sommets par une un tableau de longueur \(n\). Par exemple, si \(n=3\), le tableau [| 1; 2; 1 |] signifie que les sommets 0 et 2 sont de la couleur 1 et le sommet 1 de la couleur 2. Ecrire une fonction valide : graphe -> 'a array -> bool qui prend en argument un graphe et une liste d'entiers et renvoie true si cette coloration est valide.
On propose un algorithme glouton pour colorier un graphe : on parcourt les sommets dans leur ordre de numérotation et on leur attribue la plus petite couleur disponible. Ecrire la fonction glouton : graphe -> int array qui renvoie la coloration gloutonne d'un graphe.
La coloration gloutonne utilise-t-elle toujours un nombre minimal de couleurs ?

Aide

On pourra considérer un graphe cycle et tester différentes numérotation des sommets.

Humour d'informaticien¶

tree