graphes-l3/Exercices_2.md

## Exercices Socio et algorithmes des graphes



### Exercice 1 : Questions de cours

1.1 Qu'est-ce qu'un graphe non orienté ? Donnez un exemple d'application pratique.

1.2 Quelle est la différence entre une matrice d'adjacence et une liste d'adjacence ?

1.3 Dans quel cas serait-il préférable d'utiliser une liste d'adjacence au lieu d'une matrice d'adjacence ?

---

### Exercice 2. Matrices et Listes d'Adjacence

Considérez le graphe suivant :

- A est connecté à B et C
- B est connecté à A, C et D
- C est connecté à A, B et E
- D est connecté à B et E
- E est connecté à C et D

### 2.1 Matrice d'adjacence

Complétez la matrice d'adjacence pour ce graphe.

|      | A    | B    | C    | D    | E    |
| ---- | ---- | ---- | ---- | ---- | ---- |
| A    | 0    | 1    | 1    | 0    | 0    |
| B    | 1    | 0    | 1    | 1    | 0    |
| C    | 1    | 1    | 0    | 0    | 1    |
| D    | 0    | 1    | 0    | 0    | 1    |
| E    | 0    | 0    | 1    | 1    | 0    |

### 2.2 Liste d'adjacence

Écrivez la liste d'adjacence correspondante.

---

### Exercice 3 : Degré des sommets et centralité
**Objectif** : Comprendre l’importance des sommets dans un réseau social.

1. **Degré d’un sommet** :  
   - Calculez le degré de chaque sommet dans le graphe donné (A, B, C, D, E).
   - Quel sommet a le plus haut degré ? Que peut-on en déduire dans un contexte sociologique ?

2. **Centralité de degré** :  
   - Expliquez pourquoi un sommet ayant un haut degré peut être considéré comme central dans un réseau social.
   - Donnez un exemple d’application (ex. influence sur les réseaux sociaux, diffusion d’informations).

---

### Exercice 4 : Graphes pondérés et applications
**Objectif** : Introduire la notion de poids sur les arêtes pour modéliser des relations plus complexes.

1. **Ajout de poids** :  
   Imaginez que les relations d’amitié entre les individus du graphe ont des intensités différentes. Attribuez un poids à chaque arête pour refléter cette intensité :
   - A ↔ B : 2
   - A ↔ C : 3
   - B ↔ C : 1
   - B ↔ D : 4
   - C ↔ E : 2
   - D ↔ E : 1

2. **Distance minimale** :  
   - Trouvez le chemin de coût minimal (somme des poids) entre le sommet A et le sommet E en utilisant l’algorithme de Dijkstra.
   - Expliquez l’intérêt de l’algorithme dans des contextes réels (ex. optimisation des trajets).

---

### Exercice 5 : Représentation alternative des graphes
**Objectif** : Explorer une autre représentation des graphes : les graphes orientés.

1. **Transformation en graphe orienté** :  
   - Transformez le graphe initial (non orienté) en un graphe orienté en choisissant une direction pour chaque arête.
   - Justifiez les directions choisies dans un contexte de réseaux sociaux (ex. influence d’une personne sur une autre).

2. **Conséquences sur les chemins** :  
   - Quels chemins sont encore possibles entre A et E après l'orientation des arêtes ?
   - Expliquez en quoi les graphes orientés peuvent être utiles pour modéliser des hiérarchies ou des flux d’informations.

---

### Exercice 6 : Graphes bipartis
**Objectif** : Introduire la notion de graphes bipartis et leur utilité.

1. **Construction d’un graphe biparti** :  
   Imaginez que le graphe initial représente des personnes (A, B, C, D, E) et des événements auxquels elles participent (E1, E2).  
   Voici les participations :
   - A participe à E1 et E2.
   - B participe à E1.
   - C participe à E2.
   - D participe à E2.
   - E participe à E1 et E2.

   Représentez ce graphe biparti sous forme de matrice d’adjacence.

2. **Application sociologique** :  
   Expliquez en quoi les graphes bipartis peuvent être utilisés pour analyser des réseaux sociaux ou des collaborations (ex. analyse de co-participation à des projets).