graphes-l3/Seance_5_Composantes_Diffusion_Corrige.md

# Séance 5 — Diffusion d'une information (BFS) et composantes connexes
### Fiche enseignant

## Objectifs pédagogiques
- Introduire intuitivement le concept de **parcours en largeur (BFS)** à travers la métaphore de la **diffusion d'une information** dans un réseau social.
- Faire le lien entre la **distance dans le graphe** et la **distance sociale** entre individus.
- Montrer que le **point de départ** d'une diffusion change radicalement son déroulement.
- Introduire la notion de **composantes connexes** à travers un acteur isolé.
- Comparer BFS et DFS sans mathématiques : deux logiques d'exploration du réseau.

---

## Prérequis
- Avoir compris les notions de **graphe**, **sommets**, **arêtes** (Séance 1).
- Avoir manipulé BFS et DFS une première fois (Séance 4).
- Avoir manipulé un graphe simple avec `networkx` (ajout de sommets, arêtes, visualisation).

---

## Durée estimée
**2h**, séance unique (fusion des anciennes séances 6 et 6bis — leur contenu se recoupait largement).

---

## Matériel / outils
- Notebook `Seance_5_Composantes_Diffusion.ipynb`
- Python avec `networkx` et `matplotlib`

---

## Déroulé pédagogique

### 1. Introduction sociologique
**But :** ancrer le BFS dans une situation concrète.

Expliquer :
> Une information (rumeur, message, idée) se propage dans un réseau social.
> Certain·es la reçoivent directement, d'autres plus tard.
> Le BFS modélise cette propagation *par cercles de proximité*.

**Point clé à dire** : « En BFS, on explore *niveau par niveau* — comme une onde sociale. »

### 2. Exemple manuel : propagation pas à pas
Simulation à la main sur le petit graphe (Alice — Bob/Emma — Chloé/Félix — David/Gaël) : faire remplir le tableau des niveaux avant de passer à Python.

### 3-4. Construction du réseau et parcours BFS depuis Alice
**Résultat attendu (ordre BFS) :**
```
[('Alice', 'Bob'), ('Alice', 'Emma'), ('Bob', 'Chloé'), ('Bob', 'Félix'), ('Chloé', 'David'), ('Chloé', 'Gaël')]
```
**Distances depuis Alice :** Alice 0, Bob/Emma 1, Chloé/Félix 2, David/Gaël 3.

**À dire :** la distance = nombre d'étapes pour atteindre une personne ; plus elle est grande, plus la personne est éloignée du centre du réseau. Lien sociologique : proximité sociale, vitesse d'accès à l'information.

### 5. Comparaison BFS / DFS (à l'oral)
| Stratégie | Métaphore | Manière d'explorer | Exemple |
|:-----------|:-----------|:------------------|:---------|
| BFS (largeur) | diffusion sociale | explore les cercles autour de la source | bouche-à-oreille, message collectif |
| DFS (profondeur) | exploration ciblée | suit un chemin jusqu'au bout avant de revenir | enquête, filiation, exploration hiérarchique |

### 6. Recommencer depuis Chloé
**Résultat attendu (exemple) :**
```
[('Chloé', 'Bob'), ('Chloé', 'David'), ('Chloé', 'Gaël'), ('Bob', 'Alice'), ('Bob', 'Félix'), ('Alice', 'Emma')]
```
**Analyse :** Chloé devient un nouveau centre de diffusion, la profondeur du graphe diminue (elle est plus "au milieu"). Chloé relie deux sous-groupes : c'est une **personne-pont** — à relier au coefficient de clustering vu en Séance 3 (un pont a un coefficient de clustering faible : ses ami·es ne se connaissent pas entre eux).

**Point clé à dire :** le point de départ de la diffusion influence sa vitesse et sa portée — une info ne se propage pas pareil selon qui la lance en premier.

### 7. Composantes connexes : Hugo l'isolé
Après `G.add_node('Hugo')` :
```
Composante 1 : {'Alice', 'Bob', 'Chloé', 'Emma', 'Félix', 'David', 'Gaël'}
Composante 2 : {'Hugo'}
```
**À dire :** le graphe n'est plus connexe : deux composantes distinctes. Hugo ne reçoit aucune information.

**Lien sociologique :** un acteur isolé symbolise une **exclusion sociale** : il n'est intégré à aucun cercle relationnel.

### 8. Discussion finale
**Questions à lancer :**
- Que se passe-t-il si un individu n'est relié à personne ?
- Si plusieurs personnes lancent l'info en même temps ?
- Qui apprend la nouvelle le plus vite ? Pourquoi ?

**Lien avec la sociologie des réseaux :** notions de **centralité**, **vitesse de diffusion**, **position périphérique**, **effet d'isolation**.

---

## Interprétations sociologiques clés à souligner
| Concept Python | Traduction sociologique |
|:----------------|:------------------------|
| Distance | Proximité ou éloignement social |
| Composante connexe | Groupe / sous-communauté |
| Sommet central | Individu influent, pivot relationnel |
| Sommet isolé | Exclusion, absence de lien social |
| BFS | Diffusion collective, propagation rapide |

## Notes pédagogiques
- Insister sur le **lien entre structure et diffusion** : le BFS donne une première intuition du "pouvoir de connexion" dans un réseau social.
- Éviter tout formalisme algorithmique (pas de file, pas de pseudo-code) — le DFS/BFS formels ont déjà été codés en Séance 4, ici on reste sur l'interprétation sociologique.
- Valoriser les représentations graphiques et le vocabulaire sociologique (proximité, cercles, diffusion, influence).

**Transition possible :**
Cette séance consolide le BFS (Séance 4) et introduit les composantes connexes. Le DFS ayant déjà été vu et comparé au BFS dès la Séance 2/4, ces notions sont désormais réunies : elles préparent directement les étudiantes à l'évaluation (partiel blanc), qui reprend BFS, DFS et composantes connexes dans un contexte de lecture de réseau. La séance suivante (6-7) introduit les **graphes pondérés** et l'algorithme de **Dijkstra**.