Comment modéliser une situation par un graphe et en extraire des informations ?

En identifiant les sommets (entités/états) et les arêtes (relations), en calculant les degrés de chaque sommet et en vérifiant la connexité

L'objectif

Construire un graphe représentant une situation et en lire les propriétés structurelles.

Le principe

Un graphe est défini par un ensemble de sommets (entités) reliés par des arêtes (relations) ; le degré d'un sommet est le nombre d'arêtes qui lui sont incidentes.

La méthode

1
Identifier les sommets : lister toutes les entités ou états de la situation.
2
Identifier les arêtes : relier deux sommets $i$ et $j$ s'il existe une relation directe entre eux.
3
Calculer le degré de chaque sommet : $d(i) =$ nombre d'arêtes incidentes à $i$ . Vérifier la formule des poignées de mains : $\sum_i d(i) = 2 \times$ nombre d'arêtes.
4
Vérifier la connexité : le graphe est connexe si, depuis n'importe quel sommet, on peut atteindre tous les autres en suivant des arêtes.

Exemple corrigé

Difficulté croissante de 1 à 3

Exercices aujourd'hui0 / 3

Prêt à t'entraîner ?

Génère un exercice personnalisé sur cette méthode et entraîne-toi avec la correction IA.