On représente le réseau autoroutier entre les villes de Rennes (R), Angers (A), Tours (T), Le Mans (M), Paris (P), Lyon (L) et Grenoble (G) à l’aide d’un graphe. Les villes sont les sommets du graphe et les (auto)routes sont représentées par les arêtes du graphe. On a indiqué les distances entre les villes sur les arêtes Graphe

Matrice d'adjacence

Ecrire la matrice d'adjacence de ce graphe :

  • La matrice sera représentée par un tableau à 2 dimensions
  • la variable s'appellera matrice1
# Votre réponse ici

matrice1 = [[]]

# YOUR CODE HERE
raise NotImplementedError()
# Vérification de la réponse
assert matrice1[0][6] == 120

Liste d'adjacence

Ecrire une fonction matrice2liste(matrice, noms)

  • prenant en paramètres matrice : matrice d'adjacence et noms : noms des sommets dans l'ordre de la matrice
  • renvoyant un dictionnaire dont les clés sont les sommets et les valeurs sont un tableau de tuples au format ('Nom', distance).

Exemple : A est reliée à M, R et T. le dictionnaire commencera par {'A':[('M',100), ('R', 120), ('T', 120)] ...}

def matrice2liste(matrice, noms):
    """Renvoie la liste d'adjacence sous format dictionnaire"""
    
    # YOUR CODE HERE
    raise NotImplementedError()
matrice = [[1, 2, 1, 0],
           [2, 3, 0, 1],
           [1, 0, 0, 0],
           [0, 1, 0, 4]]
test = matrice2liste(matrice, ['A', 'B', 'C', 'D'])

assert test['C'] == [('A', 1)]
assert ('B', 2) in test['A']
assert ('D', 4) in test['D']

Liste d'adjacence vers matrice

On considère à présent le graphe représentant les mêmes villes mais les sommets sont pondérés par le temps de parcours en minutes. Voici sa liste d'adjacence au format dictionnaire tel que décrit plus haut:

{'A': [('M', 65), ('R', 90), ('T', 80)],
 'G': [('L', 70)],
 'L': [('G', 70), ('P', 230), ('T', 260)],
 'M': [('A', 65), ('P', 95), ('R', 90), ('T', 55)],
 'P': [('L', 230), ('M', 95), ('T', 130)],
 'R': [('A', 90), ('M', 90)],
 'T': [('A', 80), ('L', 260), ('M', 55), ('P', 130)]}

Ecrire une fonction liste2matrice(dico) prenant en paramètre un graphe donné par une liste d'adjacence sous format dictionnaire comme ci-dessus et renvoyant la matrice d'adjacence de ce graphe ainsi que un tableau des sommets.

En d'autre termes, la fonction liste2matrice est l'inverse de la fonction matrice2liste précédente.

def liste2matrice(dico):
    """Converti une liste d'adjacence en matrice d'adjacence"""
    # YOUR CODE HERE
    raise NotImplementedError()
# Vérification

test = {'A': [('A', 1), ('B', 2), ('C', 1)],
 'B': [('A', 2), ('B', 3), ('D', 1)],
 'C': [('A', 1)],
 'D': [('B', 1), ('D', 4)]}
l, n = liste2matrice(test)
assert n == ['A', 'B', 'C', 'D']
assert l == [[1, 2, 1, 0], [2, 3, 0, 1], [1, 0, 0, 0], [0, 1, 0, 4]]