Graphes

Les graphes sont utilisés dans de nombreux domaines, à commencer par les réseaux.
Hitoriquement, 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)

Voici une modélisation de la situation par un graphe de degré 4.

Image

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


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-dessous. (Du site XKCD).

Image