Partiel L3 Sociologie Quantitative - Analyse des Graphes
Introduction et Rappels
Ce partiel a pour objectif d'évaluer vos compétences sur les notions fondamentales des graphes et leurs applications sociologiques.
Vous devez répondre aux questions en suivant les consignes.
Définitions utiles :
- Graphe : Un ensemble de sommets reliés par des arêtes (ou arcs pour les graphes orientés).
- Chemin : Une suite de sommets connectés par des arêtes.
- Cycle : Un chemin qui revient au sommet de départ.
- Matrice d'adjacence : Représentation tabulaire des connexions entre sommets.
- Liste d'adjacence : Représentation où chaque sommet est associé à ses voisins.
- BFS (parcours en largeur) : Algorithme pour explorer un graphe niveau par niveau.
- Algorithme de Dijkstra : Méthode pour trouver le chemin de coût minimal dans un graphe pondéré.
Exercice 1 : Représentation des Graphes (7 points)
Étude de cas :
Un réseau universitaire connecte les départements suivants : - A (Sociologie) est connecté à B (Psychologie) et C (Histoire). - B est connecté à A, C, et D (Philosophie). - C est connecté à A, B, et E (Anthropologie). - D est connecté à B et E. - E est connecté à C et D.
Consignes :
- Représentez ce graphe sous forme de matrice d'adjacence. (3 points)
- Représentez ce graphe sous forme de liste d'adjacence. (3 points)
- Justifiez si la liste ou la matrice est la plus adaptée pour analyser un réseau universitaire. (1 point)
Exercice 2 : Recherche de Chemins (8 points)
Étude de cas :
Dans un graphe représentant un réseau social : - A (Alice) est amie avec B (Bob) et C (Carla). - B est ami avec A, C, et D (Dan). - C est amie avec A, B, et E (Eve). - D est ami avec B et E. - E est amie avec C et D.
Consignes :
- Effectuez un parcours en largeur (BFS) depuis Alice. Listez les sommets dans l’ordre de leur visite. (4 points)
- Trouvez le chemin le plus court entre Alice et Eve en utilisant BFS. (2 points)
- Expliquez en quoi ce type d’analyse peut être utile pour étudier des dynamiques sociales. (2 points)
Exercice 3 : Optimisation Logistique avec Dijkstra (10 points)
Étude de cas :
Une entreprise veut optimiser ses livraisons entre ses dépôts. Le graphe pondéré suivant représente les coûts (en minutes) entre les dépôts : - A ↔ B : 10 - A ↔ C : 15 - B ↔ C : 5 - B ↔ D : 20 - C ↔ D : 10 - C ↔ E : 30 - D ↔ E : 10
Consignes :
- Représentez ce graphe sous forme de matrice d'adjacence pondérée. (3 points)
- Utilisez l’algorithme de Dijkstra pour trouver le chemin de coût minimal entre A et E. Montrez toutes les étapes. (5 points)
- Expliquez en quoi cet algorithme est utile dans des problématiques logistiques. (2 points)
Exercice 4 : Analyse des Communautés (10 points)
Étude de cas :
On analyse la participation des étudiants à des projets collaboratifs : - A participe aux projets P1 et P2. - B participe aux projets P1 et P3. - C participe aux projets P2 et P4. - D participe aux projets P3 et P4. - E participe aux projets P1 et P4.
Consignes :
- Représentez ce graphe biparti sous forme de matrice d'adjacence. (3 points)
- Identifiez les groupes d’étudiants qui collaborent régulièrement en analysant leurs participations communes. (4 points)
- Expliquez comment cette analyse peut aider à améliorer la collaboration dans un cadre universitaire. (3 points)
Dernière mise à jour : 24/07/2026