Devoir n°3

Graphes et parcours en largeur

1h20

Exercice 1 : généralités et représentations

Soit le graphe de la figure 1 ci-dessous.

1. Vocabulaire

1.a. Ce graphe est-il orienté ou non orienté ?
1.b. Donner l’ordre et la taille de ce graphe.
1.c. Existe-t-il un chemin entre n’importe quelle paire de sommets de ce graphe ? Justifier.

2. Voisins et degrés

2.a. Donner les successeurs et les prédécesseurs du sommet C.
2.b. Donner les degrés entrant et sortant du sommet E, puis son degré.
2.c. Quel sommet a un degré sortant nul ?

3. Chemins

3.a. Donner un chemin de longueur 4 allant de A à F.
3.b. Donner un cycle de longueur 3 passant par A.
3.c. Quelle est la distance de A à F ? Justifier.

4. Représentations (les sommets sont toujours rangés dans l’ordre alphabétique)

4.a. Écrire en Python la liste d’adjacence de ce graphe, sous la forme d’un dictionnaire nommé graphe.
4.b. Écrire en Python la matrice d’adjacence de ce graphe, sous la forme d’une liste de listes nommée M.

5. Code à compléter

On suppose que la variable graphe contient la liste d’adjacence de la question 4.a (en cas de difficulté, on pourra s’aider de la figure 1). On souhaite écrire deux fonctions.

        def taille(graphe):
            t = 0
            for voisins in graphe.______():
                t = t + ______(voisins)
            return t

        def degre_entrant(graphe, sommet):
            d = 0
            for s in graphe:
                if ______ in graphe[s]:
                    d = ______
            return d
    

5.a. Compléter les quatre espaces ______.
5.b. Que renvoie l’appel degre_entrant(graphe, "C") ?

6. Graphe valué

Le graphe de la figure 2 représente des distances (en km) entre quatre villages.

6. Donner la matrice d’adjacence de ce graphe valué, sous la forme d’une liste de listes. On code l’absence de route par None.

Exercice 2 : parcours en largeur

Un réseau local compte huit machines numérotées de 1 à 8. Deux machines sont reliées si elles sont directement connectées par un câble. Ce réseau est modélisé par le graphe non orienté de la figure 3.

Dans tout l’exercice, lorsqu’un sommet a plusieurs voisins à explorer, on les traite par ordre croissant.

1. Principe

1.a. Quelle structure de données utilise le parcours en largeur pour mémoriser les sommets découverts qui restent à explorer ? Quel est le principe de fonctionnement de cette structure de données ?
1.b. À quoi sert le marquage des sommets (leur couleur) ? Que risquerait-il de se passer sans lui ?

2. Déroulement à la main

On effectue un parcours en largeur du graphe depuis le sommet 1. Recopier et compléter le tableau ci-dessous (ajuster le nombre de lignes nécessaires).

3. Arbre de parcours

3.a. Dessiner l’arbre de parcours en largeur obtenu depuis le sommet 1.
3.b. D’après cet arbre, quelle est la distance entre les sommets 1 et 6 ? Donner le chemin le plus court correspondant.
3.c. Le sommet 5 est relié à la fois au sommet 2 et au sommet 3. Pourquoi est-il pourtant un fils du sommet 2 dans l’arbre ?

4. Connexité

4.a. Quels sommets du graphe n’apparaissent pas dans l’arbre de parcours ?
4.b. Que peut-on en conclure sur la connexité du graphe ?
4.c. Combien d’arbres obtiendrait-on si on souhaitait parcourir tous les sommets du graphe ? Comment faudrait-il procéder ?

5. Code à compléter

On souhaite implémenter le parcours en largeur. La fonction renvoie un dictionnaire dont les clés sont les sommets du graphe et dont les valeurs sont des dictionnaires donnant la couleur, le parent et la distance de chaque sommet.

        def parcours_largeur(graphe, depart):
            parcours = {}
            parcours[depart] = {"couleur": "gris", "parent": None, "distance": 0}
            for sommet in graphe:
                if sommet != depart:
                    parcours[sommet] = {"couleur": "blanc", "parent": None, "distance": None}

            file = [depart]
            while file != []:
                sommet_visite = file.______(0)
                for voisin in ______:
                    if parcours[voisin]["couleur"] == ______:
                        parcours[voisin]["couleur"] = "gris"
                        parcours[voisin]["parent"] = sommet_visite
                        parcours[voisin]["distance"] = ______
                        file.append(voisin)
                parcours[sommet_visite]["couleur"] = ______
            return parcours
    

5.a. Compléter les cinq espaces ______.
5.b. On exécute p = parcours_largeur(graphe, 1). Quelle est la valeur de p[6] ? Quelle est celle de p[7] ?

6. Application

Compléter la fonction suivante, qui renvoie True s’il existe un chemin entre s1 et s2 dans le graphe, et False sinon. Que renvoie est_accessible(graphe, 1, 8) ?

        def est_accessible(graphe, s1, s2):
            parcours = parcours_largeur(graphe, s1)
            return parcours[s2]["couleur"] == ______