Graphes/TP/TP2.md

TP Graphes 2 : Chemins et connexité 
============
- - - - -
Exercice 0 : Classes de Départ
----------

- Téléchargez les classes de départs présentes dans le dossier idoine.
- Compilez-les et exécutez la classe TestGraphe.
- Familiarisez-vous avec le code des classes données.
- Créez votre propre graphe de test, soit dans TestGraphe soit dans une nouvelle classe de test.


Le TP est prévu pour être fait en utilisant le codage des graphes à l'aide de matrices d'adjacence.
Les classes Graphe et MatriceCarre contiennent le résultat du TP1 en code java et servira de base aux TPs suivants.
La classe JGraphe contient une classe JComponent permettant d'afficher un graphe avec la méthode `affiche()`. Un exemple d'utilisation est donné dans la classe TestGraphe.java.

- - - - -
Exercice 1 : Chemins de longueur fixe
----------

La multiplication de matrices carrées se fait grâce à la fonction de prototype :
```
MatriceCarre multiplicationMatriceCarre(MatriceCarre a);
  ```

Le code de la fonction est donné ci-dessous. Si vous le souhaitez, vous pouvez ignorer le code et faire la fonction vous-même.
```
  public MatriceCarre multiplication(MatriceCarre a){
  if(this.n!=a.n)
    throw new IllegalArgumentException("multiplication de matrices de tailles différentes");
  MatriceCarre res=new MatriceCarre(this.n);
  int i,j,k;
  for(i=0;i<this.n;i++){
        for(j=0;j<this.n;j++){
          for(k=0;k<this.n;k++){
            res.m[i][j]+=this.m[i][k]*a.m[k][j];
          }
        }
    }
    return res;
  }
```

**Question :**
En utilisant la multiplication de matrices carrées, créez une fonction renvoyant une matrice contenant les chemins d'une longueur donnée :
```
public MatriceCarre nombreDeChemins(int longueur);
```

- - - - -
Exercice 2 : Connexité
----------

Un graphe (orienté) est (fortement) connexe si pour toute paire de sommet (x,y), il existe un chemin de x à y.
De plus, s'il existe un chemin de x à y, alors il en existe un de longueur *au plus* n, où n est l'ordre du graphe.

**Question :**
Ecrire la fonction `public boolean estConnexe();` renvoyant  true si le graphe est connexe, et false sinon. 
Indice : vous aurez besoin d'une fonction permettant d'additionner des matrices.

**Question :**
Testez votre fonction sur le graphe des frontières.
Créez un graphe similaire ayant en plus le Royaume-Uni. Vérifiez que ce graphe n'est pas connexe.


- - - - -
Exercice 3 : Graphe Eulériens
----------

***Question***
En utilisant le théorème d'Euler,  écrire une fonction décidant si un graphe a un cycle eulérien.
Théorème d'Euler : 
Un graphe est eulérien si, et seulement si, il est connexe et tous ses sommets sont de degré pair.

Bonus : Comment adapter votre fonction pour décider si un graphe a un *chemin* eulérien

- - - - -
Exercice 4 : Distance et diamètre.
----------

***Question***
Ecrire une fonction ```public MatriceCarre distances();``` renvoyant une matrice dont le coefficient (i,j) contient la distance entre i et j.
Indice : Les sommets à distance 1 sont ceux qui sont adjacent (valeur 1 dans la matrice d'adjacence). 
De façon générale, un sommet x est à distance l d'un sommet y si il existe un chemin de longueur l mais aucun chemin de longueur l-1.

***Question***
Ecrire une fonction ```public int diametre()``` retournant le diamètre d'un graphe.