Vocabulaire : Théorie des graphes

7. Nom du problème visant à trouver le chemin le plus court passant par chaque arête d'un graphe au moins une fois.
9. qualifie une chaîne dans laquelle aucune arête n'est empruntée plusieurs fois
12. nom de l'algorithme permettant de trouver un arbre couvrant minimal en ajoutant successivement des arêtes de poids minimal disponibles sans former de cycle
15. nom de l'algorithme permettant de trouver un arbre couvrant minimal en ajoutant successivement des arêtes de poids minimal qui lient un nouveau sommet à l'arbre en construction
16. nombre de fois qu’un sommet est touché par une arête
18. qualifie une chaîne dans laquelle aucun sommet n'est emprunté plusieurs fois
19. Graphe simple connexe sans cycle
20. qualifie un graphe dont les arêtes possèdent un sens
21. qualifie un graphe non orienté dans lequel on peut se déplacer d'un sommet quelconque à un autre
22. qualifie un graphe contenant une chaîne hamiltonienne, mais pas de cycle hamiltonien.

1. qualifie un graphe simple non orienté dans lequel tous les sommets sont reliés par une arête
2. chaîne simple commençant et terminant au même sommet
3. qualifie un cycle parcourant chaque sommet du graphe exactement une fois (sauf le premier sommet qui est aussi le dernier)
4. qualifie un graphe contenant une chaîne eulérienne mais pas de circuit eulérien
5. qualifie un graphe qui ne contient ni boucle ni arêtes multiples d'un sommet à un autre
6. circuit dans lequel aucun sommet n'est emprunté plusieurs fois
8. qualifie un arbre contenant tous les sommets d'un graphe
10. qualifie un graphe dont les arêtes possèdent un poids (longueur, coût, distance, consommation, temps, etc.)
11. qualifie un circuit qui parcourt chaque arête du graphe exactement une fois
13. se dit de sommets reliés directement par une arête
14. Suite de sommets dans laquelle chaque paire de sommets successifs est formée de sommets adjacents
17. arête partant et revenant au même sommet