TD

Exercice 1

Enoncé

Représenter tous les graphes non orientés d'ordre 3.

Exercice 2

Enoncé

Combien y a-t-il de graphes orientés différents d'ordre 3. On ne demande pas de les représenter mais seulement de les dénombrer.

Exercice 3

Enoncé

Soit le classe Graphe suivante implémentant la structure de données des graphes orientés:

class Graphe:
    def __init__(self):
        self.adj = dict()

    def ajouter_sommet(self, sommet):
        if sommet not in self.adj:
            self.adj[sommet] = dict()

    def ajouter_arc(self, depart, arrivee):
        self.ajouter_sommet(depart)
        self.ajouter_sommet(arrivee)
        self.adj[depart][arrivee] = None

    def arc(self, depart, arrivee):
        return arrivee in self.adj[depart]

    def adjacents(self, sommet):
        lst = []
        for s in self.adj[sommet]:
            lst.append(s)
        return lst

1. Ajouter à la classe Graphe une méthode nb_sommets() qui renvoie le nombre de sommets du graphe.
2. Ajouter une méthode degre(sommet) renvoyant le degré du sommet passé en paramètre.
3. Ajouter une méthode nb_arcs() qui renvoie le nombre total d'arcs du graphe.
4. Ajouter une méthide supprimer_arc(s1, s2) permettant de supprimer l'arc allant de s1 à s2.

Exercice 4

ÉnoncéCorrection

1. Effectuer un parcours BFS sur le graphe non orienté ci-dessous, en prenant le sommet C comme sommet de départ. Que remarque-t-on?

   

Supposons qu'il existe une classe GrapheC implémentant l'interface d'un graphe connexe suivante:

méthode	description
ajouter_sommet(s)	Ajoute un sommet s au graphe
ajouter_arrete(s1, s2)	Ajoute une arrête entre les sommets s1 et s2. Ajoute les sommets si nécessaires
arrete(s1, s2)	Renvoie True si une arrête relie les sommets s1 et s2.
adjacents(s)	Renvoie une liste des sommets adjacents au sommet s
sommets()	Renvoie une liste des sommets du graphe
parcoursBFS(s)	Renvoie une liste des sommets lors du parcours en largeur partant du sommet s

2. Écrire une méthode est_connexe qui détermine si une instance de la classe GrapheC est connexe ou non. Renvoie un booléen.

Rappel

Un graphe est eulérien s'il est connexe et s'il possède exactement 0 ou 2 sommets de degré impair (le degré de sommet est son nombre de voisins).

3. Écrire une méthode est_eulerien qui détermine si un graphe est eulérien ou non.

Exercice 5: Type bac

ÉnoncéCorrection

La société CarteMap développe une application de cartographie-GPS qui permettra aux automobilistes de définir un itinéraire et d’être guidés sur cet itinéraire. Dans le cadre du développement d’un prototype, la société CarteMap décide d’utiliser une carte fictive simplifiée comportant uniquement 7 villes : A, B, C, D, E, F et G et 9 routes (toutes les routes sont considérées à double sens).

Voici une description de cette carte :

• A est relié à B par une route de 4 km de long ;
• A est relié à E par une route de 4 km de long ;
• B est relié à F par une route de 7 km de long ;
• B est relié à G par une route de 5 km de long ;
• C est relié à E par une route de 8 km de long ;
• C est relié à D par une route de 4 km de long ;
• D est relié à E par une route de 6 km de long ;
• D est relié à F par une route de 8 km de long ;
• F est relié à G par une route de 3 km de long.

1. Représenter ces villes et ces routes sur sa copie en utilisant un graphe pondéré, nommé G1.
2. Déterminer le chemin le plus court possible entre les villes A et D.
3. Définir la matrice d’adjacence du graphe G1 (en prenant les sommets dans l’ordre alphabétique).

Dans la suite de l’exercice, on ne tiendra plus compte de la distance entre les différentes villes et le graphe, non pondéré et représenté ci-dessous, sera utilisé :

Chaque sommet est une ville, chaque arête est une route qui relie deux villes.

4. Proposer une implémentation en Python du graphe G2 à l’aide d’un dictionnaire.
5. Proposer un parcours en largeur du graphe G2 en partant de A.

La société CarteMap décide d’implémenter la recherche des itinéraires permettant de traverser le moins de villes possible. Par exemple, dans le cas du graphe G2, pour aller de A à E, l’itinéraire A-C-E permet de traverser une seule ville (la ville C), alors que l’itinéraire A-H-G-E oblige l’automobiliste à traverser 2 villes (H et G).

Le programme Python suivant a donc été développé (programme p1) :

tab_itineraires=[]

def cherche_itineraires(G, start, end, chaine=[]):
    chaine = chaine + [start]
    if start == end:
        return chaine
    for u in G[start]:
        if u not in chaine:
            nchemin = cherche_itineraires(G, u, end, chaine)
            if len(nchemin) != 0:
                tab_itineraires.append(nchemin)
    return []

def itineraires_court(G,dep,arr):
    cherche_itineraires(G, dep, arr)
    tab_court = ...
    mini = float('inf')
    for v in tab_itineraires:
        if len(v) <= ... :
            mini = ...
    for v in tab_itineraires:
        if len(v) == mini:
            tab_court.append(...)
    return tab_court

La fonction itineraires_court prend en paramètre un graphe G, un sommet de départ dep et un sommet d’arrivée arr. Cette fonction renvoie une liste Python contenant tous les itinéraires pour aller de dep à arr en passant par le moins de villes possible.

Exemple (avec le graphe G2) :

itineraires_court(G2, 'A', 'F')
>>> [['A', 'B', 'I', 'F'], ['A', 'H', 'G', 'F'], ['A', 'H', 'I', 'F']]

On rappelle les points suivants :

• la méthode append ajoute un élément à une liste Python ; par exemple, tab.append(el) permet d’ajouter l’élément el à la liste Python tab ;
• en python, l’expression ['a'] + ['b'] vaut ['a', 'b'] ;
• en python float('inf') correspond à l’infini.

6. Expliquer pourquoi la fonction cherche_itineraires peut être qualifiée de fonction récursive.
7. Expliquer le rôle de la fonction cherche_itineraires dans le programme p1.
8. Compléter la fonction itineraires_court.

Les ingénieurs sont confrontés à un problème lors du test du programme p1. Voici les résultats obtenus en testant dans la console la fonction itineraires_court deux fois de suite (sans exécuter le programme entre les deux appels à la fonction itineraires_court) :

exécution du programme p1

>>> itineraires_court(G2, 'A', 'E')
[['A', 'C', 'E']]

>>> itineraires_court(G2, 'A', 'F')
[['A', 'C', 'E']]

alors que dans le cas où le programme p1 est de nouveau exécuté entre les 2 appels à la fonction itineraires_court, on obtient des résultats corrects :

exécution du programme p1

>>> itineraires_court(G2, 'A', 'E')
[['A', 'C', 'E']]

exécution du programme p1

>>>itineraires_court(G2, 'A', 'F')
[['A', 'B', 'I', 'F'], ['A', 'H', 'G', 'F'], ['A', 'H', 'I',
'F']]

9. Donner une explication au problème décrit ci-dessus. Vous pourrez vous appuyer sur les tests donnés précédemment

Exercice 6

Enoncé

La direction de la station de ski Le Lièvre Blanc, spécialisée dans la pratique du ski de fond, souhaite disposer d'un logiciel lui permettant de gérer au mieux son domaine skiable. Elle confie à un développeur informatique la mission de concevoir ce logiciel. Celui-ci décide de caractériser les pistes de ski à l'aide d'une classe Piste et le domaine de ski par une classe Domaine.

Le code Python de ces deux classes est donné en Annexe.

Partie A - Analyse des classes Piste et Domaine

1. Lister les attributs de la classe Piste en précisant leur type.

La difficulté des pistes de ski de fond est représentée par 4 couleurs : verte, bleue, rouge et noire. La piste verte est considérée comme très facile, la piste bleue comme facile, la piste rouge de difficulté moyenne et la piste noire difficile. Dans la station de ski Le Lièvre blanc, l'équipe de direction décide de s'appuyer uniquement sur le dénivelé pour attribuer la couleur d'une piste de ski.

Ainsi, une piste de ski sera de couleur :

• 'noire' si son dénivelé est supérieur ou égal à 100 mètres ;
• 'rouge' si son dénivelé est strictement inférieur à 100 mètres, mais supérieur ou égal à 70 mètres ;
• 'bleue' si son dénivelé est strictement inférieur à 70 mètres, mais supérieur ou égal à 40 mètres ;
• 'verte' si son dénivelé est strictement inférieur à 40 mètres.

2. Écrire la méthode set_couleur de la classe Piste qui permet d'affecter à l'attribut couleur la chaîne de caractères correspondant à la couleur de la piste.

On exécute à présent le programme suivant afin d'attribuer la couleur adéquate à chacune des pistes du domaine skiable Le Lièvre Blanc.

for piste in lievre_blanc.get_pistes():
    piste.set_couleur()

3. Indiquer, parmi les 4 propositions ci-dessous, le type de l'élément renvoyé par l'instruction Python lievre_blanc.get_pistes().

   • Proposition A : une chaîne de caractères ;
   • Proposition B : un objet de type Piste ;
   • Proposition C : une liste de chaînes de caractères ;
   • Proposition D : une liste d'objets de type Piste.

En raison d'un manque d'enneigement, la direction de la station est souvent contrainte de fermer toutes les pistes vertes car elles sont situées généralement en bas du domaine.

4. Écrire un programme Python dont l'exécution permet de procéder à la fermeture de toutes les pistes vertes en affectant la valeur False à l'attribut ouverte des pistes concernées.

5. Écrire une fonction pistes_de_couleur prenant pour paramètres une chaîne de caractères couleur représentant la difficulté d'une piste et une liste lst de pistes de ski de fond. Cette fonction renvoie la liste des noms des pistes dont couleur est le niveau de difficulté. Exemple : l'instruction pistes_de_couleur(lievre_blanc.get_pistes(), 'noire') renvoie la liste ['Petit Bonheur', 'Forêt', 'Duvallon'].

Un skieur de bon niveau se prépare assidûment pour le prochain semi-marathon, d'une distance de 21,1 kilomètres. À chaque entraînement, il note la liste des noms des pistes qu'il a parcourues et il souhaite disposer d'un outil lui indiquant si la distance totale parcourue est au moins égale à la distance qu'il devra parcourir le jour du semi-marathon.

La fonction semi_marathon donnée ci-dessous répond aux attentes du skieur : cette fonction prend en paramètre une liste L de noms de pistes et renvoie un booléen égal à True si la distance totale parcourue est strictement supérieure à 21,1 kilomètres, False sinon.

def semi_marathon(L):
    distance = ...
    liste_pistes = lievre_blanc.get_pistes()
    for nom in L:
        for piste in liste_pistes:
            if piste.get_nom() == ...:
                distance = distance + ...
    return ...

On donne ci-dessous deux exemples d'appels à cette fonction :

>>> entrainement1 = ['Verneys', 'Chateau enneigé', 'Rois mages', 'Diablotin']
>>> semi_marathon(entrainement1)
True
>>> entrainement2 = ['Esseillon', 'Aigle Royal', 'Duvallon']
>>> semi_marathon(entrainement2)
False

6. Recopier et compléter la fonction semi_marathon.

Partie B - Recherche par force brute

Le plan des pistes du domaine Le Lièvre Blanc peut être représenté par le graphe suivant :

Sur chaque arête, on a indiqué le nom de la piste et sa longueur en kilomètres. Les sommets correspondent à des postes de secours. Un pisteur-secouriste de permanence au point de secours D est appelé pour une intervention en urgence au point de secours A. La motoneige de la station étant en panne, il ne peut s'y rendre qu'en skis de fond. Il décide de minimiser la distance parcourue et cherche à savoir quel est le meilleur parcours possible. Pour l'aider à répondre à ce problème, on décide d'implémenter le graphe ci-dessus grâce au dictionnaire de dictionnaires suivant :

domaine = {'A': {'G': 7.5, 'H': 6.8},
        'B': {'C': 3.0, 'D': 9.2, 'E': 1.8, 'F': 4.6},
        'C': {'B': 3.0, 'D': 2.5, 'E': 6.1, 'G': 10.7},
        'D': {'B': 9.2, 'C': 2.5},
        'E': {'B': 1.8, 'C': 6.1, 'F': 10.1, 'G': 12.7},
        'F': {'B': 4.6, 'E': 10.1, 'G': 2.6, 'H': 3.4},
        'G': {'A': 7.5, 'C': 10.7, 'E': 12.7, 'F': 2.6, 'H': 5.5},
        'H': {'A': 6.8, 'F': 3.4, 'G': 5.5}}

7. Écrire une instruction Python permettant d'afficher la longueur de la piste allant du sommet E au sommet F.
8. Écrire une fonction voisins qui prend en paramètres un graphe G et un sommet s du graphe G et qui renvoie la liste des voisins du sommet s. Exemple : l'instruction voisins(domaine, 'B') renvoie la liste ['C', 'D', 'E', 'F'].

9. Recopier et compléter la fonction longueur_chemin donnée ci-dessous : cette fonction prend en paramètres un graphe G et un chemin du graphe G sous la forme d'une liste de sommets et renvoie sa longueur en kilomètres.

   Exemple : l'instruction longueur_chemin(domaine, ['B', 'E', 'F', 'H']) renvoie le nombre flottant 15.3.

   def longueur_chemin(G, chemin):
       precedent = ...
       longueur = 0
       for i in range(1, len(chemin)):
           longueur = longueur + ...
           precedent = ...
       return ...
   

On donne ci-dessous une fonction parcours qui renvoie la liste de tous les chemins du graphe G partant du sommet depart et parcourant les sommets de façon unique, c'est-à-dire qu'un sommet est atteint au plus une fois dans un chemin.

Par exemple, l'appel parcours(domaine, 'A') renvoie la liste de tous les chemins partant du sommet A dans le graphe domaine sans se soucier ni de la longueur du chemin, ni du sommet d'arrivée. Ainsi, ['A', 'G', 'C'] est un chemin possible, tout comme ['A', 'G', 'C', 'B', 'E', 'F', 'H'].

def parcours(G, depart, chemin=[], lst_chemins=[]):
    if chemin == []:
        chemin = [depart]
    for sommet in voisins(G, depart):
        if sommet not in chemin:
            lst_chemins.append(chemin + [sommet])
            parcours(G, sommet, chemin + [sommet])
    return lst_chemins

10. Expliquer en quoi la fonction parcours est une fonction récursive.

Un appel à la fonction parcours précédente renvoie une liste de chemins dans laquelle figurent des doublons.

11. Recopier et compléter la fonction parcours_dep_arr ci-après qui renvoie la liste des chemins partant du sommet depart et se terminant par le sommet arrivee dans le graphe G entrés en paramètres. La liste renvoyée ne doit pas comporter de doublons. Attention, plusieurs lignes de code sont nécessaires.

    def parcours_dep_arr(G, depart, arrivee):
        liste = parcours(G, depart)
        ...
    

12. Recopier et compléter la fonction plus_court donnée ci-dessous. La fonction plus_court prend pour paramètres un graphe G, un sommet de départ depart et un sommet d'arrivée arrivee ; elle renvoie un des chemins les plus courts sous la forme d'une liste de sommets.

    def plus_court(G, depart, arrivee):
        liste_chemins = parcours_dep_arr(G, depart, arrivee)
        chemin_plus_court = ...
        minimum = longueur_chemin(G, chemin_plus_court)
        for chemin in liste_chemins:
            longueur = longueur_chemin(G, chemin)
            if ...:
                minimum = ...
                chemin_plus_court = ...
        return chemin_plus_court
    

13. Expliquer en quoi le choix fait par le pisteur-secouriste de choisir la distance minimale pour arriver le plus rapidement possible sur le lieu de l'incident est discutable. Proposer un meilleur critère de choix.

Annexe

# Pistes
class Piste:
    def __init__(self, nom, denivele, longueur):
        self.nom = nom
        self.denivele = denivele  # en mètres
        self.longueur = longueur  # en kilomètres
        self.couleur = ''
        self.ouverte = True

    def get_nom(self):
        return self.nom

    def get_longueur(self):
        return self.longueur

    def set_couleur(self):
        # À compléter

    def get_couleur(self):
        return self.couleur

# Domaine skiable
class Domaine:
    def __init__(self, a):
        self.nom = a
        self.pistes = []

    def ajouter_piste(self, nom_piste, denivele, longueur):
        self.pistes.append(Piste(nom_piste, denivele, longueur))

    def get_pistes(self):
        return self.pistes

# Programme principal
lievre_blanc = Domaine("Le Lièvre Blanc")
lievre_blanc.ajouter_piste('Aveyrole', 62, 9.2)
lievre_blanc.ajouter_piste('Verneys', 10, 2.5)
lievre_blanc.ajouter_piste('Vincendières', 45, 3)
lievre_blanc.ajouter_piste('Ribon', 70, 6.1)
lievre_blanc.ajouter_piste('Esseillon', 8, 1.8)
lievre_blanc.ajouter_piste('Petit Bonheur', 310, 4.6)
lievre_blanc.ajouter_piste('Aigle Royal', 85, 10.1)
lievre_blanc.ajouter_piste('Château enneigé', 54, 10.7)
lievre_blanc.ajouter_piste('Sallanches', 78, 12.7)
lievre_blanc.ajouter_piste('Forêt', 145, 2.6)
lievre_blanc.ajouter_piste('Hermine', 27, 7.5)
lievre_blanc.ajouter_piste('Rois mages', 42, 5.5)
lievre_blanc.ajouter_piste('Diablotin', 76, 6.8)
lievre_blanc.ajouter_piste('Duvallon', 200, 3.4)

Pydéfis sur les graphes

• Voyage en Fangorn
• L'affaire Cicéron
• SW VI : Les Ewoks sont tous copains
• Fouinette donne l'alerte
• SW II : À la recherche du système Kamino