Aller au contenu

Chapitre 7. Graphes

Cours

Travaux pratiques

Exercices d’application

D’après les exercices proposés par C. Gouygou.

Exercice 1.

  1. On considère le graphe suivant nommé graphe1.

    graph LR
    C(C) --- B(B)
    B --- D(D)
    B --- A(A)
    A --- E(E)
    D --- E
    C --- D
    F(F) --- G(G)
    E --- F & G

    1. Sélectionner dans chaque liste déroulante ci-dessous l’adjectif qui qualifie le mieux graphe1. graphe1 est un graphe , , et .

      Réponse

      graphe1 est un graphe connexe, simple, orienté et creux.

    2. Donner la représentation de graphe1 par listes d’adjacence sous la forme d’un disctionnaire Python.

      Réponse 
      1
2
3
4
5
6
7
8
9
      graphe1 = {
    'A': ['B', 'E'],
    'B': ['A', 'C', 'D'],
    'C': ['B', 'D'],
    'D': ['B', 'C', 'E'],
    'E': ['A', 'D', 'F', 'G'],
    'F': ['E', 'G'],
    'G': ['E', 'F'],
}

    3. Donner la matrice d’adjacence de graphe1

Exercice-type Bac

2023, Sujet zéro A, Exercice 4.

Idée de sujet de grand oral

Comment les applications de navigation font-elles pour être si efficaces ?

Une réponse en vidéo avec de magnifiques animations. La notion de graphe y prend une place importante. On aborde l’algorithme de Dijkstra hors programme mais que l’on peut aborder dans un grand oral et des heuristiques intéressantes.