Graphes
Les graphes sont utilisés dans de nombreux domaines, à commencer par les réseaux.
Historiquement, on attribue à Euler, mathématicien suisse la première utilisation d’un graphe pour résoudre le problème des ponts de Königsberg:
Le problème consiste à déterminer s’il existe ou non une promenade dans les rues de Königsberg permettant, à partir d’un point de départ au choix, de passer une et une seule fois par chaque pont, et de revenir à son point de départ, étant entendu qu’on ne peut traverser le Pregel qu’en passant sur les ponts.(wikipedia)
Les points sont appelés des sommets alors que les liaisons sont appelées des arêtes. Deux sommets reliés par une arête sont dits voisins, et le degré d’un sommet est son nombre de voisins.
Cours
- NoteBook Jupyter: Introduction aux graphes avec NetworkX.
- Activité débranchée: Introduction débranchée aux graphes: réseau social.
- Le cours sur les graphes- Structure de donnée (pdf).
- Le cours sur le parcours de graphe (pdf).
Le problème du fermier, de la chèvre, du loup et de la salade peut se modéliser par un graphe. La solution n’est pas donnée par l’illustration ci-contre. (Du site XKCD)