Devoir sur les graphes

L'usage de la calculatrice n'est pas autorisé.

Durée : plus d'une heure

Exercice 1

Dessiner tous les graphes non orientés ayant exactement trois sommets.

Exercice 2

Un graphe orienté est donné sous forme de matrice d'adjacence (tableau). Écrire une fonction afficher qui permet d'afficher le graphe sous la forme suivante:

0 -> 1 3
1 -> 2 3
2 -> 3
3 -> 1

Corrigé

Une version minimaliste, pour s'amuser.

for i in range(len(G)):
  print(i, "->", " ".join([str(j) for j in range(len(G[i])) if G[i][j]==1]))

Exercice 3

Écrire une fonction qui permet de retourner la matrice d'adjacence d'un graphe à partir de sa liste d'adjacence (dictionnaire)

Corrigé

L est la liste d'adjacence et M la matrice d'adjacence

def liste2mat(L)
  n=len(L)
  M=[[0]*n for i in range(n)]
  som=list(L.keys())
  for i in range(n):
      for j in range(n):
          if som[j] in L[som[i]]:
              M[i][j]=1
  return M

Exercice 4

Écrire une fonction qui permet de déterminer si un graphe non orienté est connexe (à partir d'un sommet quelconque on peut atteindre n'importe quel autre sommet du graphe).

Corrigé

Soit M la matrice d'adjacence du graphe. On suppose implémentée une classe File. On utilise un parcours en largeur.

def Existechemin(M, depart, arrive):
  n = len(M)  # nombre de sommets dans le graphe
  F = File()
  visites = [False] * n
  # ajouter le premier sommet à la file d'attente
  F.enfiler(depart)
  while not F.estvide():
      # supprimer le sommet supérieur de la pile et marqué comme visité
      courant = F.defiler()
      visites[courant] = True
      # visiter les sommets adjacents
      for i in range(n):
          # s'il existe et qu'un bord entre depart et i et
          # le sommet i n'est pas encore visité
          if M[courant][i] > 0 and visites[i] == False:
              # ajouter i à la file marqué comme visité
              F.enfiler(i)
              visites[i] = True

          # Si le sommet i est le sommet voulu (i = arrive)
          # donc il existe un chemin de u à i (arrive)
          elif M[courant][i] > 0 and i == arrive:
              return True
  return False

Une fois cette partie du cours un peu récrite pour retourner un booléen, on parcourt les sommets et on regarde s'il existe un chemin vers chacun des autres sommets, où plutôt s'il n'existe pas un chemin entre deux sommets.

def connexe(M):
  n=len(M)
  for i in range(n):
    for j in range(i+1,n):
      if Existechemin(M,i,j)==False:
        return False
  return True

Exercice 5

Voici un graphe représentant les distances dans le réseau sud-est.

Implémenter ce graphe sous la forme d’un dictionnaire de liste dans lequel chaque clé représente le noeud étudié et les sommets adjacents sont représentés sous la forme d’une liste de dictionnaires clé(sommet adjacent): valeur(distance).
Corrigé

Le terme liste est à prendre comme un dictionnaire. Pas de pénalités pour les élèves qui ont crée des listes comme valeurs.
```
L={'Lyon':{'Grenoble':106,'Aix':292},
'Grenoble':{'Lyon':106,'Aix':239,'Nice':293},
'Aix':{'Lyon':292,'Grenoble':239,'Nice':174,'Marseille':30},
'Nice':{'Aix':174,'Grenoble':293},
'Marseille':{'Aix':30}}
```
Écrire la matrice d’adjacence et vérifier qu’elle est symétrique(on utilisera l’ordre alphabétique pour indexer les noeuds).
Corrigé

Il suffit de l'écrire de la façon suivante pour vérifier qu'elle est bien symétrique:
```
M=[[0,1,1,1,1],
   [1,0,1,0,1],
   [1,1,0,0,0],
   [1,0,0,0,0],
   [1,1,0,0,0]]
```

Proposer un algorithme qui renvoie tous les chemins possibles pour aller de Nice à Lyon sans jamais passer deux fois par la même ville. On utilisera trois paramètres d’entrée: le graphe implémenté sous la forme d’un dictionnaire d’adjacence comme celui de la question 2 et les deux villes de départ et d’arrivée.

Corrigé

Vous remarquerez que pour répondre à la question posée, il n'y a aucun intérêt de connaître la distance entre deux villes.

On utilise un parcours un profondeur, et donc une structure de pile.

Comme précédemment, on suppose que la classe Pile est implémentée, munie des méthodes classiques.

Le fait que les voisins soient donnés sous forme de dictionnaire ne change pas grand chose au programme.

def cherche_tous_chemins(graphe, depart,arrivee):
    """
    recherche tous les chemins dans un graphe depuis un sommet de départ vers un sommet d'arrivée
    graphe: liste d'adjacence du graphe étudié (un dictionnaire)

    depart: ville de départ pour le chemin recherché

    arrivee: ville d'arrivée pour le chemin recherché

    return: la liste des chemins pour aller de depart à arrivee.
    """
    chemins = []
    if not(depart in graphe.keys()) or not(arrivee in graphe.keys()):
        return []
    P = Pile()
    P.empiler([(depart,[depart])])
    chemin = []
    while not P.estvide():
        sommet,chemin = P.depiler()
        liste_nouveaux_sommets_voisins = [voisin for voisin in graphe[sommet] if not(voisin in chemin)]
        for voisin in liste_nouveaux_sommets_voisins:
            if voisin == arrivee:
                chemins.append(chemin + [arrivee])
            P.empiler((voisin,chemin + [voisin]))
    return chemins