103 lines
3.8 KiB
Markdown
103 lines
3.8 KiB
Markdown
## 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).
|