Graphes

Introduction

Définir une classe permettant de représenter un graphe non orienté (non pondéré).
On peut faire cela de la manière suivante :
```
class Graphe(object):
  def __init__ (self, N):
    self. N = N
    self. arcs = [ [] for i in range (N)]
```
Définir une méthode d'ajout d'un arc à un graphe.
On peut faire cela de la manière suivante :
```
  def ajouteArc (self, n1, n2):
    self. arcs [n1]. append (n2)
    self. arcs [n2]. append (n1)
```
mais cela n'est pas très satisfaisant car si on ajoute deux fois le même arc, celui-ci apparaît deux fois. Avant d'ajouter, un successeur à un nœud, il vaut mieux tester s'il est déjà présent dans la sous-liste ou pas :
```
  def ajouteArc (self, n1, n2):
    if not n2 in self. arcs [n1]:
        self. arcs [n1]. append (n2)
    if not n1 in self. arcs [n2]:
    self. arcs [n2]. append (n1)
```
Définir une méthode qui affiche un graphe au format dot déjà vu pour les arbres.
Par exemple :

Recherche de chemin

Écrire une méthode qui détermine s'il existe un chemin entre deux nœuds. Elle renvoie True ou False selon le cas.
```
  def existeChemin (self, n1, n2):
    ...
```
Écrire une méthode qui détermine la longueur d'un chemin entre deux nœuds d'un graphe. S'il n'y a pas de chemin entre ces deux nœuds, la fonction renvoie -1.
définir une méthode qui détermine le nombre de composantes connexes dans un graphe.

définir une méthode qui associe chaque nœud à sa composante connexe (on numérote les composantes connexes et ensuite, on associe un numéro de composante connexe à chaque nœud).

  def composantes (self):
    listeNonParcourus = [i for i in range (self. N)]
    numeroComposantes = [0 for i in range (self. N)]
    compteur = 0
    while listeNonParcourus != []:
        noeud = listeNonParcourus [0]
        LNA = []
        for i in range (1, len (listeNonParcourus)):
            if not self. existeChemin (noeud, i):
                LNA. append (listeNonParcourus [i])
                numeroComposantes [listeNonParcourus [i]] = compteur + 1
        compteur = compteur + 1
        listeNonParcourus = LNA

Génération de graphes aléaotoires

On va générer des graphes aléatoires, c'est-à-dire pour un nombre de nœuds fixé, on crée un certain nombre d'arcs aléatoirement. On se donne un paramètre (proportion) qui contrôle le nombre d'arcs du graphe.
La forme générale de la fonction est la suivante :

on va générer proportion * N * (N-1)/2 arcs.
on fait une boucle réalisant ce nombre d'itérations. À chaque itération, on tire aléatoirement deux nœuds et on ajoute un arc les reliant.

Écrire une fonction qui fait cela.

def genereGrapheAleatoire (N, proportion):
    ga = Graphe (N)
    nbarcs = int (proportion * N * (N - 1) / 2)
    arcs = [[] for i in range (N)]
    for i in range (nbarcs):
        a = randint (0, N - 1)
        b = randint (0, N - 1)
        while (a == b) or (a in arcs [b]) or (b in arcs [a]):
            a = randint (0, N - 1)
            b = randint (0, N - 1)
        arcs [a]. append (b)
        arcs [b]. append (a)
        ga. ajouteArc (a, b)
    return (ga)