Théorie des graphes en CPGE ECG : ressources

vendredi 14 juillet 2023
par  Quentin SOUILLOT

Dans le cadre de l’atelier IREM 2022-2023 sur la théorie des graphes, cet article propose quelques ressources afin de mener à bien cet enseignement en CPGE économique et commerciale voie générale (ECG).

La théorie des graphes a fait son apparition dans les nouveaux programmes des CPGE économique et commerciale (en maths appliquées uniquement) lors de la dernière réforme en 2021. Elle permet de mettre en application le calcul matriciel vu plus tôt dans l’année, et offre un certain nombre de possibilités pour la pratique de l’algorithmique. Cliquer ici pour le programme (page 12).

Voici un cours (version élève) et un TD sur les graphes donnés cette année aux élèves du lycée Bellepierre :

Cours
TD

L’année précédente, deux TP avaient été donnés aux élèves : le premier portait sur différentes modélisations des graphes, le second sur l’algorithme de Dijkstra. Cette année, en plus de ces deux TP, et dans le cadre de l’atelier IREM, il m’a semblé pertinent de proposer un troisième TP sur un thème pouvant être abordé à tout niveau : la coloration des graphes. Ce TP s’inscrit dans le programme ECG puisqu’il s’agit ici de mettre en œuvre un algorithme glouton : cette classe d’algorithmes a été étudiée plus tôt dans l’année avec l’exemple du rendu de monnaie. J’en profite pour remercier Alain de ses conseils sur ce dernier TP.

TP1
TP2
TP3

Pour terminer, voici une brève analyse des premiers sujets de concours spécifiques aux nouveaux programme, tombés cette année.

Graphes aux concours 2023

Commentaires

Logo de Quentin SOUILLOT
mercredi 19 juillet 2023 à 07h35 - par  Quentin SOUILLOT

Merci pour tes suggestions !

Dijkstra n’est effectivement pas le meilleur choix pour le calcul matriciel, mais il est mentionné dans le programme officiel, donc je le fais...

Logo de Sébastien HOARAU
mardi 18 juillet 2023 à 16h03 - par  Sébastien HOARAU

Le plus court chemin à l’aide de l’algorithme de Dijkstra repose sur la fonction du même nom qui construit et renvoie 2 tableaux :

def dijkstra(g, dep, arr):
    """renvoie le plus court chemin de dep à arr dans le graphe g à n sommets"""
    n = g.number_of_nodes()
    preds, dist = initialise(n, dep)
    visited = set()
    while arr not in visited:
        s = select_node(g, dist, visited)
        visited.add(s)
        for v in not_visited_neighbors(g, s, visited):
            d = dist[s] + g.edge_view(s, v).weight
            if d < dist[v]:
                dist[v] = d
                preds[v] = s
    return preds, dist

À partir du tableau preds on pourra reconstruire tout le chemin, si on le souhaite, dans une autre fonction :

def shortest(g, dep, arr, alpha=False):
    preds, dist = dijkstra(g, dep, arr)
    node = arr
    the_path = [node if not alpha else ALPHA[node]]
    while node != dep:
        node = preds[node]
        the_path.append(node if not alpha else ALPHA[node])
    the_path.reverse()
    return the_path, dist[arr]
Logo de Sébastien HOARAU
mardi 18 juillet 2023 à 15h56 - par  Sébastien HOARAU

Je ne suis pas sûr que Dijkstra soit un bon candidat pour illustrer du calcul matriciel, en utilisant du Numpy... Disjktra ne manipule que 2 tableaux (celui des prédécesseurs et celui des distances — par rapport au sommet de départ)

Certes on peut représenter le graphe par sa matrice d’adjacence mais on ne fera aucun calcul avec.

Navigation

Articles de la rubrique