Graphe
Figure
formée de points, appelés sommets, et de
segments de droite ou de courbe reliant deux sommets entre eux, qui sont
appelés arêtes. Voici deux graphes :
A, B, C, ... sont les sommets.
AB, BC, CD, ... sont les arêtes. Certaines situations peuvent être
représentées par un graphe. Citons les récréations de parcours du cavalier,
de coloriage, de
transvasement, les jeux où il faut
parcourir une chaîne ou un chemin allant d'une position initiale à une
position finale gagnante.
Certaines récréations connues
peuvent être résolues par application de la théorie des graphes : le voyageur
de commerce, les ponts de Königsberg,
les
utilités, l'icosien,
et le problème du loup, de la chèvre et du chou.
Le graphe peut également jouer le rôle d'un tablier
dans un jeu. Les sommets sont les positions tandis que les arêtes déterminent
les mouvements possibles selon les règles données. Le graphe peut être biparti, généalogique,
gracieux et planaire.
Comme un réseau, il peut être valué.
© Charles-É. Jean
Index
: G
