C11 Graphes ¶

Cours¶

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 pratiques¶

Exercice 1 : Implémentation par matrice d'adjacence¶

Ecrire une fonction cree_graphe qui prend en argument un entier n et renvoie une liste de n listes de n booléens (tous initialisés à false). Cette liste permet donc de représenter un graphe par matrice d'adjacence.
Ecrire une fonction cree_arete qui prend en argument un graphe représenté par une matrice d'adjacence et deux entiers i et j et modifie cette matrice de façon à créer l'arc i -> j du graphe.

On donne ci-dessous une fonction de visualisation d'un graphe représenté par une matrice d'adjacence :

def visualise(g):
    '''Visualise le graphe g sous forme d'image avec graphviz.'''
    img_graphe = graphviz.Digraph()
    for i in range(len(g)):
        img_graphe.node(str(i))
        for j in range(len(g)):
            if g[i][j]:
                img_graphe.edge(str(i), str(j))
    img_graphe.view()

Attention pour utiliser cette fonction il faut importer le module graphviz.
Créer un graphe à 5 sommets (numérotés 0,1,2,3 et 4) et y créer les arcs suivants : 0 -> 1, 0 -> 2, 1 -> 2, 2 -> 3, 4 -> 1 puis visualiser ce graphe.

Ecrire une fonction qui affiche la matrice d'adjacence du graphe. Le résultat attendu pour le graphe ci-dessus est :
```
0 1 1 0 0 
0 0 1 0 0 
0 0 0 1 0 
0 0 0 0 0 
0 1 0 0 0
```
Ecrire une fonction qui degre_sortant qui prend en argument un graphe g représenté par une matrice d'adjacence ainsi qu'un entier i et renvoie le degre sortant de ce sommet.
Ecrire une fonction sucesseurs qui prend en argument un graphe g représenté par une matrice d'adjacence ainsi qu'un entier i et renvoie la liste des successeurs de ce sommet.
Ecrire une fonction ronde qui prend en entrée un entier n et renvoie un graphe dans lequel chaque sommet i a un unique successeur : le sommet i+1 modulo n.
Ecrire une fonction qui degre_entrant qui prend en argument un graphe g représenté par une matrice d'adjacence ainsi qu'un entier i et renvoie le degre entrant de ce sommet.
Ecrire une fonction predecesseurs qui prend en argument un graphe g représenté par une matrice d'adjacence ainsi qu'un entier i et renvoie la liste des predecesseurs de ce sommet.
Reprendre les questions précédentes dans le cadre d'un graphe non orienté.

Exercice 2 : Implémentation par liste d'adjacence¶

Ecrire une fonction cree_graphe qui prend en argument un entier n et renvoie un dictionnaire dont les clés sont les entiers de 0 à n-1 et dont les valeurs sont des listes vides. Ce dictionnaire permet donc de représenter un graphe par listes d'adjacence.
Ecrire une fonction cree_arete qui prend en argument un graphe représenté par liste d'adjacence et deux entiers i et j et modifie ce dictionnaire de façon à créer l'arc i -> j du graphe.
On donne ci-dessous une fonction de visualisation d'un graphe représenté par une matrice d'adjacence :
```
def visualise(g):
    img_graphe = graphviz.Digraph()
    for s in g:
         img_graphe.node(str(s))
         for t in g[s]:
              img_graphe.edge(str(s),str(t))
    img_graphe.view()
```
Attention pour utiliser cette fonction il faut importer le module graphviz.
Créer un graphe à 5 sommets (numérotés 0,1,2,3 et 4) et y créer les arcs suivants : 0 -> 1, 0 -> 2, 1 -> 2, 2 -> 3, 4 -> 1 puis visualiser ce graphe.
Ecrire une fonction qui degre_sortant qui prend en argument un graphe g représenté par liste d'adjacence ainsi qu'un entier i et renvoie le degre sortant de ce sommet.
Ecrire une fonction sucesseurs qui prend en argument un graphe g représenté par liste d'adjacence ainsi qu'un entier i et renvoie la liste des successeurs de ce sommet.
Ecrire une fonction ronde qui prend en entrée un entier n et renvoie un graphe dans lequel chaque sommet i a un unique successeur : le sommet i+1 modulo n.
Ecrire une fonction degre_entrant qui prend en argument un graphe g représenté par liste d'adjacence ainsi qu'un entier i et renvoie le degre entrant de ce sommet.
Ecrire une fonction predecesseurs qui prend en argument un graphe g représenté par une matrice d'adjacence ainsi qu'un entier i et renvoie la liste des predecesseurs de ce sommet.
Reprendre les questions précédentes dans le cadre d'un graphe non orienté.

Exercice 3 : D'une représentation à l'autre¶

Ecrire une fonction matrice_vers_liste qui prend en entrée un graphe représenté par une matrice d'adjacence (tel que dans l'exercice 1) et renvoie ce même graphe représenté par liste d'adjacence (tel que dans l'exercice 2).
Ecrire une fonction liste_vers_matrice qui prend en entrée un graphe représenté par liste d'adjacence (tel que dans l'exercice 2) et renvoie ce même graphe représenté par matrice d'adjacence (tel que dans l'exercice 1).

Exercice 4 : Coloration d'un graphe¶

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.

Combien de couleurs sont nécessaires au minimum pour colorier un graphe à \(n\) sommets ? Et au maximum ?
On suppose maintenant que les graphes sont représentés par liste d'adjacence et que les sommets sont \(0, 1, \dots\). Ecrire une fonction adjacent qui prend en argument un graphe et deux sommets et renvoie True lorsque ces deux sommets sont adjacents et False sinon.
On représente la coloration d'un graphe à \(n\) sommets par une liste de \(n\) entiers. Par exemple si le graphe a 4 sommets la coloration [1, 2, 1, 3] signigie que les sommets 0 et 2 sont de la couleur 1, le sommet 1 est de couleur 2 et le sommet 3 est de couleur 3. Ecrire une fonction valide qui prend en argument un graphe et une coloration et renvoie True lorsque cette coloration est valide et False sinon.
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 qui prend en argument un graphe et renvoie sa coloration gloutonne.
On considère un graphe cycle à 6 sommets, montrer que ce graphe peut-être colorer avec deux couleurs. En choisissant une numérotation appropriée des sommets montrer que l'algorithme glouton utilise 3 couleurs. Que peut-on en conclure ?

Exercice 5 : Exercices sur Codex¶

Quelques exercices sur les graphes sur Codex