Aller au contenu

Exercices 2

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 :
  2. Calculez le degré de chaque sommet dans le graphe donné (A, B, C, D, E).

  3. Quel sommet a le plus haut degré ? Que peut-on en déduire dans un contexte sociologique ?

  4. Centralité de degré :

  5. Expliquez pourquoi un sommet ayant un haut degré peut être considéré comme central dans un réseau social.
  6. 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é :
  2. A ↔ B : 2
  3. A ↔ C : 3
  4. B ↔ C : 1
  5. B ↔ D : 4
  6. C ↔ E : 2

  7. D ↔ E : 1

  8. Distance minimale :

  9. Trouvez le chemin de coût minimal (somme des poids) entre le sommet A et le sommet E en utilisant l’algorithme de Dijkstra.
  10. 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é :
  2. Transformez le graphe initial (non orienté) en un graphe orienté en choisissant une direction pour chaque arête.

  3. Justifiez les directions choisies dans un contexte de réseaux sociaux (ex. influence d’une personne sur une autre).

  4. Conséquences sur les chemins :

  5. Quels chemins sont encore possibles entre A et E après l'orientation des arêtes ?
  6. 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 :
  2. A participe à E1 et E2.
  3. B participe à E1.
  4. C participe à E2.
  5. D participe à E2.
  6. E participe à E1 et E2.

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

  1. 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).

Dernière mise à jour : 24/07/2026