TNSI : Introduction aux Graphes

TNSI : cours Graphes ## Introduction : Exemples d'Utilisation des Graphes

Arbre 1 : Réseau Social, de type Follower

Arbre 2 : Réseau Social, de type Amitié.
Sur ce graphe, on constate qu'il y a une grosse composante connexe, et quelques petites

Arbre 3 : Réseau Routier à double Sens (Non Orienté)

Arbre 4 : Réseau Routier.
Sur ce graphe, les sommets sont des lieux sur la carte, et les arcs sont des routes les reliant. On pourrait imaginer :

• Des ruelles toutes à double sens : Graphe Non Orienté. Ou bien,
• Ajouter des flèches, pour indiquer les sens uniques. Dans ce cas, le graphe serait Orienté

Arbre 5 : Labyrinthe.
Voici un labyrinthe qui n'est pas parfait, il y a un îlot. On ne peut pas en sortir en utilisant la technique de la main gauche (ou droite) si on part d'un point entre D et F. À droite, on voit une modélisation sous forme de graphe, dont on pourra faire des parcours de graphe (en largeur ou en profondeur) pour résoudre des problèmes.

Arbre 6 : Théorie des Jeux.
Dans un jeu où on ne retrouve pas deux fois la même position dans la même partie, le graphe des positions est sans cycle, donc un arbre. Dans cet exemple (Algorithme minimax) :
1️⃣ On commence par les feuilles, qui modélisent des parties finies, en convenant de coder le résultat final :

• +1 pour une victoire de X, et
• −1 pour une défaite de X,
• 0 pour un nul.

2️⃣ À chaque étage, on remonte à l'étage précédent, en raisonnant comme suit :

• si c'est le tour de X, on prend le maximum des possibilités.
• Si c'est le tour de O, on prend le minimum des possibilités.

3️⃣ On peut prouver qu'il y a match nul pour deux joueurs qui ont la meilleure stratégie.

Arbre 7 : Réseau Internet

Arbre 8 : Graphe des Dépendances.
Ce graphe indique les modules requis pour accéder à d'autres dans un cursus universitaire en informatique, ou bien les lectures conseillées de chapitres avant d'aborder d'autres.
Ce genre de graphe est utilisé, par exemple, en compilation, où un source ne peut être compilé que si ses dépendances sont satisfaites... Il faut évidemment vérifier l'absence de cycle !