Vocabulaire CM 1 Flashcards
Def graphe non orienté
Composé de relations symétriques
Def graphe simple
Il n’existe pas de boucle (rel a vers a)
Def arêtes “incidentes” + nom version sommet
Ayant une extrémité en commun (ex ces relations sont incidences à a)
Sommet adjacents
Def voisin d’un sommet
Tous les sommets reliés par une arête au sommet donné
Def degré d’un sommet
Nb de sommets voisins d’un sommet donné
Def degré du graphe
Degré max du graphe (delta)
Def
-chemin
-longueur
-nom des sommets de départ et d’arrivée
Suite de sommets reliés
Nn de sommet inclus
Origine et extrémité
Def distance
Plus court chemin entre 2 sommets
Def excentricité
Max(distance entre un sommet et tous les autres)
Def rayon
Min(excentricité de chacun des sommets)
Def diamètre
Max(excentricité de chacun des sommets)
Def graphe connexe
Il existe un chemin entre toute paire de sommets
Def isthme
Une arête qui assure la connexité d’un graphe
Def cycle
Dans graphe nn orienté, chemin avec origine et extrémité confondus
Def graphe partiel
Graphe auquel on a enlevé arête par rapport à un autre graphe
