Description.
Un graphe est un ensemble de points dont certaines paires sont directement reliées par un lien.
Ces liens peuvent être orientés, d'un point vers un autre ou vice versa. Dans le cas contraire, les liens sont symétriques,
et le graphe est non-orienté.
Généralement, les points sont appelés les sommets ou les nœuds. Les liens sont appelés arêtes dans les graphes non-orienté
et arcs dans un graphe orienté.
Le but est de cette applete est de s’approprier les différents éléments caractéristiques d’un graphe,
en vue de saisir les algorithmes qui en font usage, comme par exemple, l'algorithme du plus court chemin.
Utilisation comme outil.
Les graphes sont manipulés au quotidien.
Un cas concret peut être un réseau d'amis où chaque sommet est une personne en particulier,
et un lien entre deux personnes met en évidence leur familiarité.
Ainsi, on peut se poser la question comment Alice peut entrer en relation avec Bob, et qui plus est de manière optimum,
autrement dit en limitant le nombre de personnes intermédiaires.
Nous allons manipuler l'interface pour introduire la théorie des graphes (pour avoir l'information sur toutes les fonctionnalités,
passer la souris sur "info>>>").
- Positionner un groupe d'amis, ou "réseau", de 5 personnes. Vous pouvez placer un nom et l'effacer par commandes de clavier
et souris (se référer aux instructions fournies par l'aide),
bouger également la position des personnes sur l'interface.
Nous allons symboliser les liens de familiarité entre chacun par des traits reliant les uns aux autres ou non.
Prenez deux personnes non reliées directement, et chercher à trouver le plus "court chemin" entre ces deux personnes
afin de se connaître, autrement dit, trouver la personne intermédiaire
qui pourrait faire le "pont". Pour trouver ce plus court chemin, nous pouvons nous aider des informations de distance
ou de poids des liens.
- Générer de manière automatique tous les noeuds disponibles et quelques liens.
De la même manière, prenez deux personnes non reliées directement, et chercher à trouver le plus "court chemin" entre
ces deux personnes.
Notons ainsi que ce plus court chemin peut être repéré à l'oeil, tant que le graphe est de taille raisonnable.
Vérifier que le chemin trouvé est exacte avec l'algorithme de l'application
(pour lancer l'algotithme de calcul du plus court chemin entre 2 noeuds: clic gauche + 'b' pour le noeud de départ,
clic gauche + 'e' pour le noeud d'arrivée.)
- Comme nous le disions, plus grand est le réseau, plus difficile il est de déduire de manière visuelle le plus court chemin.
Si le groupe d'amis est de 20 personnes, combien de liens doivent être potentiellement considérés? Et si le groupe est
de 30 personnes?