Graphes et influence

Modéliser les réseaux sociaux par des graphes : sommets, arêtes, degré et propagation de l'information (programme SNT 2nde)

À propos de cette page

Ces problèmes corrigés sur « Graphes et influence » en seconde permettent d'appliquer le cours à des situations concrètes en sciences numériques et technologie (SNT). Ils suivent le programme officiel de seconde et se résolvent étape par étape. Au programme : Qu'est-ce qu'un graphe ?, Vocabulaire des graphes, Degré d'un sommet et influence, Chemins et distances. Cherche au brouillon, saisis ta réponse puis clique sur « Vérifier » pour te corriger. Idéal pour développer le raisonnement, la rigueur et la confiance avant une évaluation. Problèmes gratuits proposés par un professeur particulier à Marseille pour progresser en sciences numériques et technologie (SNT) en seconde.

Résous chaque problème, écris ta réponse puis clique sur « Vérifier ». Pose tes calculs au brouillon.

Facile

Prob. 1 — Réseau d'une classeDans une classe de 5 élèves (A, B, C, D, E), les liens d'amitié sont les suivants : A-B, A-C, B-D, C-D, D-E. Réponds aux questions.

Combien d'arêtes comporte ce graphe ?

Quel est le degré du sommet D ?

Quelle est la distance entre A et E ?

Quel est le diamètre de ce graphe ?

La somme des degrés vaut-elle le double du nombre d'arêtes ? Calcule pour vérifier. (oui ou non)

Voir le corrigé

5 — A-B, A-C, B-D, C-D, D-E : 5 arêtes.
3 — D est relié à B, C et E : d(D) = 3.
3 — Chemin le plus court : A-B-D-E ou A-C-D-E, longueur 3.
3 — La distance maximale est 3, par exemple entre A et E.
oui — d(A)+d(B)+d(C)+d(D)+d(E) = 2+2+2+3+1 = 10 = 2×5. Oui.

Moyen

Prob. 2 — Matrice d'adjacence et analyseOn donne la matrice d'adjacence suivante pour un graphe non orienté à 4 sommets {1,2,3,4} : M = [[0,1,1,0],[1,0,0,1],[1,0,0,1],[0,1,1,0]]. Réponds aux questions.

Quel est le degré du sommet 1 ?

Le sommet 2 et le sommet 3 sont-ils voisins ? (oui ou non)

Combien d'arêtes comporte ce graphe ?

Quelle est la distance entre le sommet 2 et le sommet 3 ?

Ce graphe est-il connexe ? (oui ou non)

Voir le corrigé

2 — La somme de la ligne 1 est 0+1+1+0 = 2.
non — M[2][3] = 0 : pas d'arête entre 2 et 3.
4 — Somme de tous les éléments = 8, divisée par 2 (car non orienté) = 4 arêtes.
2 — Pas d'arête directe ; chemin 2-1-3 ou 2-4-3, longueur 2.
oui — Tous les sommets peuvent être atteints depuis n'importe quel autre.

Difficile

Prob. 3 — Propagation d'une informationUn réseau social compte 8 utilisateurs : U1 à U8. Les liens sont : U1-U2, U1-U3, U2-U4, U2-U5, U3-U6, U3-U7, U4-U8. U1 publie une information à l'étape 0.

Combien d'utilisateurs reçoivent l'information à l'étape 1 (voisins directs de U1) ?

Combien d'utilisateurs reçoivent l'information à l'étape 2 (voisins des voisins de U1, non déjà atteints) ?

Combien d'étapes faut-il pour que U8 reçoive l'information ?

Si on supprime U2 du réseau, U5 et U8 peuvent-ils encore recevoir l'information de U1 ? (oui ou non)

Explique en une phrase pourquoi les réseaux sociaux numériques permettent une propagation plus rapide qu'un réseau humain classique.

Voir le corrigé

2 — U1 est directement relié à U2 et U3 : 2 utilisateurs à l'étape 1.
4 — À l'étape 2 : U4, U5 (voisins de U2) et U6, U7 (voisins de U3) : 4 nouveaux utilisateurs.
3 — Chemin U1-U2-U4-U8 : 3 étapes.
non — Sans U2, U4, U5 et U8 sont déconnectés de U1.
Réponse libre — exemple : Les réseaux sociaux numériques ont des sommets de très grand degré (hubs) et un diamètre très faible, ce qui permet à une information d'atteindre des millions de personnes en quelques étapes seulement.

Bloqué sur ce chapitre ?

Moi c'est Ben, j'ai créé ce site pour aider le plus d'élèves possible, partout en France. Je peux aussi reprendre avec toi ce qui coince en cours particulier : en visio, ou à domicile si tu es à Marseille.

Réserver un 1^er cours → Voir les tarifs

Soutien scolaire à Marseille · Cours particuliers au lycée · Aide aux devoirs