J’ai découvert à mes dépens cette semaine que la terminologie de la théorie des graphes est loin d’être unifiée. C’est particulièrement problématique pour la traduction des concepts fondamentaux utilisés dans presque toutes les démonstrations et descriptions. Il s’agit des concepts de sous graphe et de chemin. En effet, il n’y a presque pas de correspondance entre les termes anglais et français, mais il y a beaucoup de recoupement.

Voici la situation pour les sous graphes.

• sous graphe [induced subgraph] (retrait de sommets, et conséquemment des arêtes incidentes)
• graphe partiel [subgraph] (mêmes sommets, mais retrait d’arêtes)
• sous graphe partiel [spanning subgraph] (retrait de sommets (+ arrêtes incidentes), mais aussi retrait d’arête)
• Une clique [NON TRADUIT] (uniquement un sous graphe complet)
• Un stable [NON TRADUIT] (uniquement des sommets, pas d’arête)

Enfin, la situation est pire pour les chemins. Voici l’état des choses:

• Une chaîne [walk] (orienté: chemin)
• Une chaîne simple [path] (orienté: chemin simple) (arêtes distinctes)
• Une chaîne élémentaire [trail] (orienté: chemin élémentaire) (sommets distincts, par conséquent arêtes distinctes, donc est chaîne simple)
• Une chaîne fermée (orienté: chemin fermé) (se terminant par le sommet de départ)
• Un circuit [cycle = close path] (G orienté: cycle)(se terminant par le sommet de départ et arêtes distinctes – chaîne simple fermée)
• NON TRADUIT [circuit = close trail] (terminé par le sommet de départ et sommets distincts)

Ainsi, produire un lexique avec une correspondance entre le français et l’anglais ne sera pas une chose facile. Néanmoins, je vais peut-être tenter le coup.