Terminale · Numérique et sciences informatiques

Graphes : représentation et parcours

Comprendre qu'un graphe est une structure relationnelle et identifier ses éléments de base : les sommets, les arcs et les arêtes.

Aperçu gratuit
Illustration de la fiche « Graphes : représentation et parcours »

Les points essentiels

  • Un graphe modélise des relations entre des objets.
  • Chaque objet modélisé est représenté par un sommet.

Les mots à connaître

graphe
Structure relationnelle formée de sommets reliés entre eux par des arcs ou des arêtes.
sommet
Élément de base d'un graphe qui représente un objet ou une entité.

Un exemple pour comprendre

On modélise un petit groupe de quatre personnes : Alice, Boris, Chloé et David. Alice connaît Boris et Chloé. Boris connaît Chloé. La connaissance est réciproque. Représente ces liens par un graphe.

Étape 1 : chaque personne est un sommet, donc le graphe possède 4 sommets. Étape 2 : chaque lien de connaissance est une liaison. Étape 3 : la connaissance est réciproque, donc la relation n'est pas orientée. Étape 4 : on utilise des arêtes. Le graphe a 4 sommets et 3 arêtes : Alice–Boris, Alice–Chloé, Boris–Chloé. David est un sommet isolé, car aucune arête ne le relie.

Première page de l’Essentiel : Graphes : représentation et parcours
Ketty