Graphe (mathématiques discrètes)

Carte Peu commune · n° 158735

Dans le domaine des mathématiques discrètes, la théorie des graphes définit le graphe, une structure composée d'objets et de relations entre deux de ces objets. Abstraitement, lesdits objets sont appelés sommets (ou nœuds ou points), et les relations entre eux sont nommées arêtes (ou liens ou lignes). On distingue les graphes non orientés, où les arêtes relient deux sommets de manière symétrique, et les graphes orientés, où les arêtes, alors appelées arcs (ou flèches), relient deux sommets de manière asymétrique. Les graphes sont couramment représentés graphiquement à l'aide de cercles pour les sommets et de lignes (éventuellement courbées) pour les arêtes, ces dernières étant munies de flèches s'il y a une orientation. Lorsque les graphes sont très grands, la taille des sommets est souvent fonction du nombre de leurs relations (le degré). Le mot « graph » a été utilisé pour la première fois dans ce sens par James Joseph Sylvester en 1878.

Lire sur Wikipédia · Image AzaToth, Public domain