Modéliser une situation par un graphe - Exercice 3

15 min

Sur un réseau social, cinq amis Amandine (

A

), Bruno (

B

), Chloé (

C

), David (

D

) et Emma (

E

) peuvent « suivre » d'autres personnes.
Amandine suit Bruno et Chloé ; Bruno suit Chloé ; Chloé suit David ; David suit Amandine et Bruno ; Emma suit Amandine et Chloé.

Question 1

Représenter cette situation par un graphe orienté : un arc allant de $X$ vers $Y$ signifie que $X$ suit $Y$ .

Correction

« Suivre » n'est pas une relation réciproque (Bruno suit Chloé, mais Chloé ne suit pas Bruno) : on utilise donc un graphe orienté.

Question 2

Que représentent le degré sortant et le degré entrant d'un sommet ? Donner le degré entrant de chaque sommet.

Correction

Le degré sortant d’un sommet

A

est le nombre d'arêtes dont le sommet

A

est le point de départ.

Le degré entrant d’un sommet

A

est le nombre d'arêtes dont le sommet

A

est le point d'arrivée.

Le degré sortant d'un sommet est le nombre de personnes que cette personne suit ; le degré entrant est son nombre d'abonnés.
En comptant les arcs qui arrivent sur chaque sommet, les degrés entrants sont :

A

2

;

B

2

;

C

3

;

D

1

;

E

0

Question 3

Qui a le plus d'abonnés ? Qui n'en a aucun ?

Correction

D'après la question

2

Chloé a le plus d'abonnés (

3

) et Emma n'en a aucun

Question 4

Donner un chemin de longueur $2$ allant de $E$ à $D$ . Existe-t-il un chemin allant de $D$ à $E$ ?

Correction

Il y a un arc de

E

vers

C

et un arc de

C

vers

D

: le chemin

E-C-D

est de longueur

2

.
En revanche, aucun arc n'arrive sur le sommet

E

(son degré entrant est

0

) : aucun chemin ne peut se terminer en

E

.
Ainsi :

il n'existe pas de chemin allant de

D

E

Signaler une erreur

Aide-nous à améliorer nos contenus en signalant les erreurs ou problèmes que tu penses avoir trouvés.

Connecte-toi ou crée un compte pour signaler une erreur.

Modéliser une situation par un graphe - Exercice 3

Représenter cette situation par un graphe orienté : un arc allant de XXX vers YYY signifie que XXX suit YYY .

Que représentent le degré sortant et le degré entrant d'un sommet ? Donner le degré entrant de chaque sommet.

Qui a le plus d'abonnés ? Qui n'en a aucun ?

Donner un chemin de longueur 222 allant de EEE à DDD . Existe-t-il un chemin allant de DDD à EEE ?

Représenter cette situation par un graphe orienté : un arc allant de $X$ vers $Y$ signifie que $X$ suit $Y$ .

Donner un chemin de longueur $2$ allant de $E$ à $D$ . Existe-t-il un chemin allant de $D$ à $E$ ?