Graphes et algorithmes - TP 1

Michel Couprie, Gilles Bertrand

1. Préliminaires

Avant tout, récupérez le fichier GraphesTP1.tgz et décompressez-le : 

    tar zxvf GraphesTP1.tgz
    rm GraphesTP1.tgz
    cd GraphesTP1; ls
Cette archive contient des programmes C pour manipuler des graphes, la documentation de ces programmes se trouve ici :

Documentation

1.1 Premiers graphes

1.1.1 Créer et imprimer un graphe

Dans un fichier ordinaire, saisissez les données d'un graphe quelconque, sous la forme suivante : 

<nombre_sommets> <nombre_arcs> 
arcs
<sommet_initial> <sommet_final>
<sommet_initial> <sommet_final>
...

Par exemple (voir le fichier k5.graph) : 

5 10
arcs
0 1
0 2
0 3
0 4
1 2
1 3
1 4
2 3
2 4
3 4

Editez les fichiers exo111.c, exo112.c et lisez-les. Compilez la bibliothèque : 

    make
puis compilez ces deux programmes : 
    make exo111.exe
    make exo112.exe
et exécutez-les : 
    ./exo111.exe k5.graph
    ./exo112.exe k5.graph
Ce dernier programme crée un fichier Postscript dont le nom reprend celui du fichier graphe donné (par exemple ici : k5.graph.eps). Vous pourrez visualiser ce fichier PostScript généré grâce à ghostview, kghostview ou display : 
    display k5.graph.eps

1.1.2 Générer un graphe aléatoire

Editez le fichier exo113.c, lisez-le, compilez et exécutez. Visualisez les résultats pour plusieurs valeurs des paramètres.

1.2 Premiers algorithmes

Avant de passer à la suite, étudiez la description des structures de données utilisée pour représenter un graphe sous la forme Γ (application successeurs). Pensez également à vous référer à la documentation du code source, en particulier :

1.2.1 Calcul du symétrique d'un graphe

Editez le fichier exo121.c, lisez-le, compilez et exécutez. Analyser la fonction Sym. Pourquoi n'est-elle pas efficace ? Quelle est la complexité de calcul de l'algorithme ?

1.2.2 Mesure du temps de calcul

Editez le fichier exo122.c, lisez-le, compilez et exécutez. Notez les temps de calculs obtenus pour diverses tailles de graphes.

1.2.3 Algorithme linéaire pour le calcul du symétrique

Dans le fichier exo122.c, modifiez la fonction Sym pour rendre l'algorithme linéaire. Voici comment parcourir une liste de successeurs : 

  pcell p;
  ...
    /* pour tout sommet j successeur de i */
    for (p = g->gamma[i]; p != NULL; p = p->next) 
    {
      j = p->som;    
      ...
Refaire les mesures de temps de calcul avec la nouvelle version, et comparer.

2. Friends

Imaginons un groupe de septs amis : Rachel, Monica, Ross, Chandler, Janice, Joe, et Phoebe. Ils habitent New York et projettent de louer deux voitures pour aller passer des vacances en Floride. Toutefois, passer ensemble les 18 heures que dure le trajet peut s'avérer problématique si les passagers des deux véhicules ne sont pas soigneusement choisis.

En effet, il faut savoir que :

Formulez ce problème en termes de graphe et donnez une solution pour ce cas particulier.

3. Graphes bipartis

On dit qu'un graphe G = (E, Γ) est biparti si l'ensemble E des sommets peut être partitionné en deux sous-ensembles E1 et E2 (c'est-à-dire, E1 ∪ E2 = E et E1 ∩ E2 = ∅) de telle sorte qu'un arc ne puisse relier entre eux deux sommets de E1, ni relier entre eux deux sommets de E2. Considérons, par exemple :

On voit que G1 est un graphe biparti avec E1 = {1, 4, 5} et E2 = {2, 3}, et que G2 n'est pas un graphe biparti. On peut voir la bipartition des sommets du graphe en deux sous-ensembles E1 et E2 comme un ``coloriage'' des sommets par deux couleurs différentes (bi-coloriage).

Dans ce qui suit, pour simplifier, on suppose que G est connexe.

3.1 Algorithme

Proposer un algorithme, linéaire en temps de calcul, qui indique si un graphe G donné est biparti ou pas, et si oui, qui indique un bi-coloriage de G. Il est conseillé de vous inspirer de l'algorithme CompFortConnexe étudié en cours.

3.2 Implémentation

Pour l'implémentation de votre algorithme, vous pouvez également vous inspirer de celle de l'algorithme CompFortConnexe, que vous trouverez dans le fichier compfoco.c. Il vous sera sans doute plus simple de recopier ce code et de le modifier (il faut avant cela bien le comprendre !).

Vous pourrez utiliser le champ v_sommets de la structure graphe pour stocker les couleurs associées aux sommets, et la fonction AfficheValeursSommets pour afficher le résultat en mode texte.

Pour visualiser graphiquement le résultat de votre algorithme, vous pouvez vous inspirer du programme demo_couleurs.c qui se trouve dans votre répertoire. Ce programme dessine un graphe dont les sommets portent chacun un nom (chaîne de caractères) et une valeur (champ v_sommets). Ces valeurs, des entiers entre 0 et 4, sont interprétés comme des couleurs (blanc, noir, rouge, vert, bleu respectivement pour 0, 1, 2, 3, 4). Le fichier demo_couleurs.graph contient un exemple.

Testez votre programme sur plusieurs graphes bipartis ou non, y compris celui de la section ``Friends''.

4. Bonus (travail personnel après le TP)

4.1 Propriété

Montrer qu'un graphe est biparti si et seulement si il ne contient pas de cycle de longueur impaire.

4.2 Détection de cycles impairs

Etant donné un graphe non biparti, proposez et implémentez une méthode pour détecter et afficher un cycle de longueur impaire.

4.3 Trouver des graphes bipartis

On peut maintenant imaginer deux stratégies pour trouver un graphe biparti, à partir d'un graphe qui ne l'est pas : l'idée est de détecter puis de supprimer des cycles de longueur impaire, soit par suppression d'arcs, soit par suppression de sommets. Dans notre application "friends", la première stratégie revient à négliger une ou plusieurs inimitiés, la seconde est plus radicale car elle exclut carrément des membres du groupe. Implémentez une de ces deux stratégies.

Dernière mise à jour :  par Michel Couprie.