TD numéro 9 du tronc commun en informatique 1998-99 dirigé par Serge Vaudenay et David Pointcheval.

Graphes I

  1. * On utilise un graphe représenté par des listes de successeurs et implémentés par la classe GrapheOriente suivante. 
      class GrapheOriente {
  ListeDeSommets sommets;
  GrapheOriente() {
    sommets=null;
  }
  Sommet ajouteSommet() {...}
  void initialiseVisite() {...}
}
class Sommet {
  String etiquette;
  int travail;
  boolean visite;
  ListeDeSommet succ;
  Sommet(String e) {...}
  void nouveauSuccesseur(Sommet s) {...}
}
class ListeDeSommets {
  Sommet contenu;
  ListeDeSommets suivant;
  boolean visite;
  ListeDeSommets(Sommet s,ListeDeSommets adj) {...}
}
    Le constructeur de la classe GrapheOriente crée un graphe vide qui contient des objets de type Sommet. Une méthode d'instance de la classe GrapheOriente permet d'ajouter un nouveau sommet, en précisant son étiquette. Chaque sommet est composé d'une étiquette (son nom), d'un champs de travail de type int, d'un booléen visite utile pour visiter l'algorithme, et d'une liste de successeurs. Une méthode d'instance initialiseVisite de la classe GrapheOriente permet de mettre à false tous les champs visite. Les listes de sommets sont implémentées par la classe ListeDeSommet qui s'utilise comme une classe Liste habituelle avec un champs contenu et un champs suivant. Si l'on a un objet g de classe GrapheOriente, on a donc accès à
    • la liste de ses sommets g.sommets
    • les méthodes g.ajouteSommet qui retournent un nouveau sommet
    • la méthode g.initialiseVisite
    Etant donné deux sommets u et v, on peut également ajouter une nouvelle arête de u vers v par u.nouveauSuccesseur(v).

    Afin de faire une application Java qui permet de définir un graphe orienté et de faire un traitement dessus, on utilise l'interface GrapheOrienteEditeur. Pour cela, télécharger le fichier GrapheOrienteEditeur.java (en cliquant ici), puis le compiler. Le programme d'application peut alors se trouver dans un fichier séparé dans une classe GrapheOrienteApplication. L'éditeur de graphe lance le constructeur de cette classe. Le programme ressemble donc à ceci. 

      class GrapheOrienteApplication {
  GrapheOrienteApplication(GrapheOriente g) {
    ...
  }
}

    Faire une méthode

      void parcoursEnProfondeur(GrapheOriente g)
    qui parcours le graphe en profondeur en affichant les sommets dans l'ordre où ils sont visités.
    [corrigé]

  2. ** (On utilise la même structure de donnée que l'exercice précédent.)
    On cherche à effectuer un certain nombre de tâches t1, ..., tn. On a cependant un certain nombre de contraintes de précédance c1, ..., cm de la forme ci= (tji,tki) qui signifient que la tâche tji doit nécessairement être effectuée avant la tâche tki. On représente l'ensemble de ces tâches et de ces contraintes par un graphe orienté.

    Définir une méthode qui détermine si un tel ordonnancement est possible.

    Définir un algorithme qui affiche un ordre possible des tâches qui respecte toutes les contraintes lorsque l'ordonnancement est possible.
    [corrigé]

  3. * On utilise une structure de donnée de graphe non orienté analogue à celle de l'exercice 1. 
      class Graphe {
  ListeDeSommets sommets;
  Graphe() {
    sommets=null;
  }
  Sommet ajouteSommet() {...}
  void initialiseVisite() {...}
}
class Sommet {
  String etiquette;
  int travail;
  boolean visite;
  ListeDeSommet voisin;
  Sommet(String e) {...}
  void nouveauVoisin(Sommet s) {...}
}
class ListeDeSommets {
  Sommet contenu;
  ListeDeSommets suivant;
  boolean visite;
  ListeDeSommets(Sommet s,Liste adj) {...}
}
    On utilise de même l'interface GrapheEditeur. Pour cela, télécharger le fichier GrapheEditeur.java (en cliquant ici) Les applications sont définies dans la classe GrapheApplication.

    On dit qu'un graphe est bipartie si l'on peut faire une partition de l'ensemble de ses sommets en deux parties V1 et V2 telle qu'il n'existe pas d'arête reliant deux sommets d'une même classe. Faire une méthode

      boolean estBipartie(GrapheOriente g)
    qui indique si le graphe est bipartie.
    [corrigé]

  4. ** (On utilise la même structure de donnée que l'exercice précédent.)
    Etant donné un graphe connexe, ecrire une méthode qui affiche un chemin u1, u2, ..., un qui passe par tous les sommets (éventuellement plusieurs fois) en passant exactement deux fois par chaque arête.
    [corrigé]

  5. *** (On utilise la même structure de donnée que l'exercice 3.)
    On appelle circuit une suite de sommets u1, u2, ..., un telle que pour tout i, les sommets ui et ui+1 sont voisins, et u1 et un également. On dit qu'un circuit est Eulérien s'il passe exactement une fois par chaque arête.

    Etant donné un graphe connexe, à quelle condition nécessaire et suffisante existe-t-il un circuit Eulérien? ecrire une méthode qui affiche affiche un tel circuit s'il existe.
    [corrigé]