Représentation graphique d'une fonction.

 Théorie des graphes,

Problème de logique, le berger

Les types de graphes

Un graphe simple G est un ensemble de points S, appelés sommets, reliés ou non entre eux par un ensemble d'arêtes A ; on le note G = (S, A), le nombre des sommets étant noté Card (S) et celui des arêtes Card (A). Un graphe simple est la représentation d'une relation binaire symétrique sur S dont les liens constituent A. Si cette relation n'est pas symétrique, ces liens sont alors des arcs dotés d'une origine et d'une extrémité ; on dit que le graphe est orienté.

S'il existe une succession d'arêtes reliant deux sommets x et y d'un graphe simple G, celle-ci constitue une chaîne entre x et y ; si, de plus, x = y, c'est-à-dire qu'on retourne au point de départ, elle constitue un circuit. Dans un graphe orienté, de semblables successions d'arcs sont appelées respectivement un chemin et un cycle. Pour ces quatre notions, il existe une même mesure, leur longueur, qui est le nombre d'arêtes ou d'arcs parcourus. De plus, chaîne, circuit, chemin ou cycle sont dits élémentaires si on ne repasse pas deux fois par le même sommet et simples si on n'emprunte pas deux fois la même arête.

Si, dans un graphe simple, tout sommet est reliable par un chemin à tout autre, ce graphe est simplement connexe. Un graphe est complet si tout sommet est relié à chacun des autres. Souvent, on cherche à éviter dans un graphe que deux arêtes ne se rencontrent ailleurs qu'en un sommet. Ce n'est pas toujours possible, mais, lorsque c'est le cas, le graphe est planaire. On montre qu'il ne peut y avoir de graphe complet et planaire dès que le nombre de sommets est supérieur à cinq.

L'utilisation des graphes

Elle est courante dans les problèmes de recherche opérationnelle ou lorsqu'il s'agit d'optimiser un ensemble d'opérations. On utilise notamment les graphes dans la modélisation de réseaux téléphoniques, routiers, fluviaux, etc., ou dans l'établissement de plannings de projets.