Exercices

Exercice 1

Exercice 3 du sujet 0 version A - 2024

Correction Q1.

image

Correction Q2.

Le chemin le plus court est A-E-D (10 km).

Correction Q3.

La matrice d'adjacence de G1 est : \(\pmatrix{ 0 & 4 & 0 & 0 & 4 & 0 & 0 \\ 4 & 0 & 0 & 0 & 0 & 7 & 5 \\ 0 & 0 & 0 & 4 & 8 & 0 & 0 \\ 0 & 0 & 4 & 0 & 6 & 8 & 0 \\ 4 & 0 & 8 & 6 & 0 & 0 & 0 \\ 0 & 7 & 0 & 8 & 0 & 0 & 3 \\ 0 & 5 & 0 & 0 & 0 & 3 & 0 \\ }\)

Correction Q6.

La fonction cherche_itineraires s'appelle elle-même, elle est donc récursive.

Correction Q7.

La fonction cherche_itineraires sert à remplir la liste tab_itineraires (initialement vide) avec tous les chemins (uniques) partant de start et allant à end.

Code pour tester la Q8. 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
G2 = {'A': ['B', 'C', 'H'],
    'B': ['A', 'I'],
    'C': ['A', 'D', 'E'],
    'D': ['C', 'E'],
    'E': ['C', 'D', 'G'],
    'F': ['G', 'I'],
    'G': ['E', 'F', 'H'],
    'H': ['A', 'G', 'I'],
    'I': ['B', 'F', 'H']
    }

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
Correction Q8. 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
G2 = {'A': ['B', 'C', 'H'],
    'B': ['A', 'I'],
    'C': ['A', 'D', 'E'],
    'D': ['C', 'E'],
    'E': ['C', 'D', 'G'],
    'F': ['G', 'I'],
    'G': ['E', 'F', 'H'],
    'H': ['A', 'G', 'I'],
    'I': ['B', 'F', 'H']
    }

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:
            mini = len(v)
    for v in tab_itineraires:
        if len(v) == mini:
            tab_court.append(v)
    return tab_court
Correction Q9.

Le problème vient de la variable globale tab_itineraires.

  • Après l'exécution de la commande itineraires_court(G2, 'A', 'E'), tab_itineraires contient tous les chemins de A à E.
  • Si le programme n'est pas re-exécuté, l'enchainement avec la commande itineraires_court(G2, 'A', 'F') va venir rajouter à la liste tab_itineraires tous les chemins de A à F.
  • Lors de la recherche du trajet minimum, les trajets testés seront donc à la fois les trajets de A à F mais aussi de A à E : on peut donc potentiellement avoir une réponse erronnée.

Pour éviter cela, on pourrait faire ceci (non demandé) :

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
def cherche_itineraires(G, start, end, chaine=[]):
    tab_itineraires = []
    def cherche(G, start, end, chaine=[]):
        chaine = chaine + [start]
        if start == end:
            return chaine
        for u in G[start]:
            if u not in chaine:
                nchemin = cherche(G, u, end, chaine)
                if len(nchemin) != 0:
                    tab_itineraires.append(nchemin)
        return []
    cherche(G, start, end, chaine=[])
    return tab_itineraires


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

Exercice 2

extrait de la BNS 2024

On considère dans cet exercice un graphe orienté représenté sous forme de listes d’adjacence.

On suppose que les sommets sont numérotés de 0 à n-1.

Par exemple, le graphe suivant :

image

est représenté par la liste d’adjacence suivante :

adj = [[1, 2], [2], [0], [0]]

Écrire une fonction voisins_entrants(adj, x) qui prend en paramètre le graphe donné sous forme de liste d’adjacence et qui renvoie une liste contenant les voisins entrants du sommet x, c’est-à-dire les sommets y tels qu’il existe une arête de y vers x.

Exemples :

>>> voisins_entrants([[1, 2], [2], [0], [0]], 0)
[2, 3]
>>> voisins_entrants([[1, 2], [2], [0], [0]], 1)
[0]
Correction 
1
2
3
4
5
6
def voisins_entrants(adj, x):
    vois = []
    for i in range(len(adj)):
        if x in adj[i]:
            vois.append(i)
    return vois

Exercice 3

Dans cet exercice, on considère un graphe non orienté représenté sous forme de listes d’adjacence. On suppose que les sommets sont numérotés de 0 à n-1.

Ainsi, le graphe suivant:

image

sera représenté par la liste d’adjacence suivante:

adj = [[1, 2], [0, 3], [0], [1], [5], [4]]

On souhaite déterminer les sommets accessibles depuis un sommet donné dans le graphe. Pour cela, on va procéder à un parcours en profondeur du graphe.

Compléter la fonction suivante.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
def parcours(adj, x, acc):
    '''Réalise un parcours en profondeur récursif
    du graphe donné par les listes d'adjacence adj 
    depuis le sommet x en accumulant les sommets
    rencontrés dans acc'''
    if x ...: 
        acc.append(x)
        for y in ...: 
            parcours(adj, ...) 

def accessibles(adj, x):
    '''Renvoie la liste des sommets accessibles dans le
    graphe donné par les listes d'adjacence adj depuis
    le sommet x.'''
    acc = []
    parcours(adj, ...) 
    return acc

Exemples : 

>>> accessibles([[1, 2], [0], [0, 3], [1], [5], [4]], 0)
[0, 1, 2, 3]
>>> accessibles([[1, 2], [0], [0, 3], [1], [5], [4]], 4)
[4, 5]

Correction 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
adj = [[1, 2], [0, 3], [0], [1], [5], [4]]

def parcours(adj, x, acc):
    '''Réalise un parcours en profondeur récursif
    du graphe donné par les listes d'adjacence adj
    depuis le sommet x en accumulant les sommets
    rencontrés dans acc'''
    if x not in acc:
        acc.append(x)
        for y in adj[x]:
            parcours(adj, y, acc)

def accessibles(adj, x):
    '''Renvoie la liste des sommets accessibles dans le
    graphe donné par les listes d'adjacence adj depuis
    le sommet x.'''
    acc = []
    parcours(adj, x, acc)
    return acc

Exercice 4

Exercice 2 du sujet Concours GEIPI 2024.

Codes du sujet :

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
sentiers = [('Briana', 'La Concorde', 'Grand Palais', 100),
            ('Teddy', 'Grand Palais', 'Trocadéro', 550),
            ('Elaine', 'La Concorde', 'Trocadéro', 200),
            ('Lucie', 'Grand Palais', 'Champ de Mars', 512),
            ('Sydney', 'Trocadéro', 'Champ de Mars', 100)]

def creer_dico_arcs_sortants(sentiers):
    arcs_sortants = ...
    for (n, p1, p2, d) in sentiers:
        if ... not in arcs_sortants:
            arcs_sortants[ ... ] = []
        arcs_sortants[ ... ].append((p1, n, d))
        if ... not in ... :
            arcs_sortants[ ... ] = []
        arcs_sortants[ ... ].append( ... )
    return arcs_sortants

from math import inf # la constante inf représente (+ infini)
def plus_proche(a_visiter):
    min = ...
    proche = ''
    for (p, (poids, pred, sent)) in a_visiter.items():
        if ... <= ... :
            ( ... , ... ) = ( ... , ... )
    return ...

def meilleur_chemin(base, depart, arrivee):
    arcs = creer_dico_arcs_sortants(base)
    a_visiter = {p: (inf, '', '') for p in arcs.keys()}
    a_visiter[depart] = ...
    visites = ...
    while a_visiter != ... :
        # recherche du sommet suivant à visiter
        p = ...
        (dist,precedent,sentier) = a_visiter[p]
        # m-à-j des voisins de p restant à visiter
        for (suivant, n, d) in ... :
            if ... in a_visiter:
                (min,prec,sent) = ...
                poids = ... + dist
                if ... < ... :
                    a_visiter[suivant] = (..., ..., ...)
        # p passe des sommets à visiter aux sommets visités
        visites[p] = a_visiter[p]
        del a_visiter[p]
    affichage(visites, depart, arrivee)

def affichage(visites, depart, arrivee):
    pass
    (dist, depuis, nom) = visites[arrivee]
    pass
    if dist == inf:
        pass
        return
    pass
    if depart != arrivee:
        pass  
        pass
    pass

Pour vous aider à comprendre l'algorithme de Dijkstra, n'oubliez pas cette vidéo d'un youtuber célèbre.

Correction Q1. 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
def creer_dico_arcs_sortants(sentiers):
    arcs_sortants = {}
    for (n, p1, p2, d) in sentiers:
        if p2 not in arcs_sortants:
            arcs_sortants[p2] = []
        arcs_sortants[p2].append((p1, n, d))
        if p1 not in arcs_sortants :
            arcs_sortants[p1] = []
        arcs_sortants[p1].append((p2, n, d))
    return arcs_sortants
Correction Q2. 
1
2
3
4
5
6
7
8
from math import inf # la constante inf représente (+ infini)
def plus_proche(a_visiter):
    min = inf
    proche = ''
    for (p, (poids, pred, sent)) in a_visiter.items():
        if poids <= min :
            ( min , proche ) = ( poids , p )
    return p
Correction Q3. 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
def meilleur_chemin(base, depart, arrivee):
    arcs = creer_dico_arcs_sortants(base)
    a_visiter = {p: (inf, '', '') for p in arcs.keys()}
    a_visiter[depart] = (0, '', '')
    visites = {}
    while a_visiter != {} :
        # recherche du sommet suivant à visiter
        p = plus_proche(a_visiter)
        (dist, precedent, sentier) = a_visiter[p]
        # m-à-j des voisins de p restant à visiter
        for (suivant, n, d) in arcs[p] :
            if suivant in a_visiter:
                (min, prec, sent) = a_visiter[suivant]
                poids = dist + d
                if poids < min :
                    a_visiter[suivant] = (poids, p, n)
        # p passe des sommets à visiter aux sommets visités
        visites[p] = a_visiter[p]
        del a_visiter[p]
    affichage(visites, depart, arrivee)
Correction Q4. 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
def affichage(visites, depart, arrivee):
    pass
    (dist, depuis, nom) = visites[arrivee]
    pass
    if dist == inf:
        print('aucun chemin du point', depart, 'au point', arrivee)
        return
    pass
    if depart != arrivee:
        affichage(visites, depart, depuis)  
        print('en passant par le chemin', nom)
    print('étape au point', arrivee, '(distance', dist, ')')