Aller au contenu

Réseau routier

Exercice

Note

Dans cet exercice 1, on met en place les conventions utilisées pour les exercices suivants.

Le schéma ci-dessous représente un réseau de routes entre des villes.

réseau routier 1

Les flèches signifient que les routes sont à sens unique.

On représente les liaisons entre villes par la liste de listes (matrice) ci-dessous:

routes = [ [0, 0, 0, 0],
           [1, 0, 0, 0],
           [1, 1, 0, 1],
           [1, 1, 0, 0]
         ]

Cette liste de listes est à interpréter comme suit:

a b c d
a 0 0 0 0
b 1 0 0 0
c 1 1 0 1
d 1 1 0 0

La "ligne" c, "colonne" a est marquée d'un 1: cela traduit le fait qu'il y a une route allant de c vers a.
La ligne a, colonne c est marquée d'un 0: il n'y a pas de route de a vers c.

A vous

Donner le code de la liste de listes correspondant au réseau routier ci-dessous (on prend les villes dans l'ordre alphabétique comme ci-dessus).

réseau routier 2

Attention

Dans ce réseau, certaines routes n'ont pas de flèches: cela signifie qu'elles sont à double-sens.

On placera donc un 1 par exemple de A vers B mais aussi de B vers A.

Réponse

A B C D E
A 0
1 1 0 1
B 1 0 0 0 0
C 1 0 0 0 0
D 0 0 1 0 1
E 0 1 0 0 0

La liste de listes python:

routes = [ [0, 1, 1, 0, 1],
           [1, 0, 0, 0, 0],
           [1, 0, 0, 0, 0],
           [0, 0, 1, 0, 1],
           [0, 1, 0, 0, 0]
         ]

Exercice

Écrire une fonction python prenant en entrée une liste de listes comme ci-dessus représentant un réseau routier, ainsi que la liste des noms des villes de ce réseau routier et renvoyant la liste des routes.

Une route allant de A vers B sera représentée par le tuple ('A','B').

def les_routes(reseau, villes):
    """
    reseau -- matrice traduisant la présence de routes 
    villes -- liste des noms des villes (même ordre que pour la matrice)

    renvoie la liste des routes 
    sous la forme de tuples (ville d'origine, ville d'arrivée)
    """

Exemple

Pour le deuxième réseau routier de l'exercice précédent:

  • l'entrée sera:

la matrice traduisant les routes:

[  [0, 1, 1, 0, 1],
   [1, 0, 0, 0, 0],
   [1, 0, 0, 0, 0],
   [0, 0, 1, 0, 1],
   [0, 1, 0, 0, 0]
]
et la liste des noms des villes reliées par ces routes:
['A', 'B', 'C', 'D', 'E']

  • la liste obtenue en sortie contiendra tous les couples ('A','B'), ('B', 'A'), ('A','E'), ('A','C'), ('C','A') ... qui traduisent l'existence d'une route entre les deux villes du couple.
Un code

Ce fichier ipynb contient un code possible.

Version statique html.

Exercice

Écrire une fonction python prenant en entrée une matrice représentant un réseau routier, ainsi que la liste des noms des villes de ce réseau routier et renvoyant la liste des routes à sens unique.

La fonction demandée est donc assez proche de celle de l'exercice précédent mais la liste obtenue en sortie ne doit pas contenir les routes à double-sens.

Un code

Ce fichier ipynb contient un code possible.

Version statique html