Comment modéliser une situation… : En identifiant les sommets… — maths expertes | MetMat

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é

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

Que ferais-tu face à un exercice de ce type ?

Quatre villes $A$ , $B$ , $C$ , $D$ sont reliées par des routes : $A$ - $B$ , $A$ - $C$ , $B$ - $C$ , $C$ - $D$ . Modéliser par un graphe.

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 \text{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.

Pour comprendre, fais des exercices !

Exercice d'exemple

Quatre villes $A$ , $B$ , $C$ , $D$ sont reliées par des routes : $A$ - $B$ , $A$ - $C$ , $B$ - $C$ , $C$ - $D$ . Modéliser par un graphe.

Étape 1 —

Identifier les sommets : lister toutes les entités ou états de la situation.

Sommets : $A$ , $B$ , $C$ , $D$ .

Étape 2 —

Identifier les arêtes : relier deux sommets

i

j

s'il existe une relation directe entre eux.

Arêtes : $\{A,B\}$ , $\{A,C\}$ , $\{B,C\}$ , $\{C,D\}$ .

Étape 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 \text{nombre d'arêtes}

$d(A)=2$ , $d(B)=2$ , $d(C)=3$ , $d(D)=1$ . Somme $= 8 = 2 \times 4$ . ✓

Étape 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.

De $A$ on atteint $B$ , $C$ directement, puis $D$ via $C$ : le graphe est connexe.

Graphe connexe à 4 sommets et 4 arêtes.

Les applications suivantes et la correction guidée sont réservées aux membres Premium

La méthode et sa première application corrigée restent en accès libre. Le Premium débloque les applications suivantes, l'aide IA et le suivi de ta maîtrise.