3.8 KiB
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.
-
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 ?
-
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.
-
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
-
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.
-
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).
-
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é.
-
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.
-
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).