Théorie des graphes : C’est une discipline mathématique et informatique qui étudie les graphes.
Définition d’un graphe : Un graphe est un ensemble de points données nommés nœuds (ou sommets ou cellules) reliés par des traits (segments) ou des flèches nommées arêtes (ou liens ou arcs). L’ensemble des arêtes entre les nœuds forme donc une forme similaire à un réseau.
Les arêtes peuvent être orientées ou non orientées, la relation ne va que dans un seul sens et est donc asymétrique, le graphe est donc dit orienté.
Les origines: Un article du mathématicien suisse Leonhard Euler, présenté à l’académie de Saint-Pétersbourg en 1735 puis publié en 1741, traitait du « problème des sept ponts de Königsberg ».
Le problème consistait à trouver une promenade en partant d’un point donné qui fasse revenir à ce même point en passant une fois est une seule par chaque pont.
Un chemin passant par toute arête exactement une fois fut nommé chemin eulérien, ou circuit eulérien s’il finit là où il a commencé. Un graphe comportant un circuit eulérien est donc appelé graphe eulérien, ce qui constitue donc le premier cas de propriété d’un graphe. On accorde donc à Euler l’origine de la théorie des graphes parce qu’il fut le premier à proposer un traitement mathématique de la question. Par la suite d’autres problèmes se posèrent comme celui de trouver le trajet le plus court entre deux points, ce qui donnera naissance par exemple à l’algorithme du plus court chemin de Dijkstra.
Les algorithmes élaborés pour résoudre des problèmes concernant les graphes ont de nombreuses applications dans tous les domaines liés à la notion de réseau (réseau social, réseau informatique, télécommunications, routier, etc…) et bien d’autres domaines (ex : la génétique).
sources: théorie des graphes – Wikipédia
théorie des graphes – Larousse
Graphes et Algorithmes 