Les Graphes (spé) Flashcards
Les points sont
Les sommets du graphe
Les lignes sont appelées
Arêtes (ou arc)
Une boucle est
Une arête dont les extrémités sont confondues
Deux sommets sont adjacents si ..
Ils sont reliés par une arête
Un sommet pendant..
N’est relié qu’à un autre point. Il n’a qu’un seul voisin
Un sommet isolé
N’est relié à aucun autre
Si deux sommets sont reliés par plusieurs arêtes ..
Chacune est une arête multiple
Un graphe est complet si..
Deux sommets quelconques sont reliés par une arête
L’ordre d’un graphe est égal
Au nombre de sommets
Le degré d’un sommet est ..
Le nombre d’arêtes ayant ce sommet pour extrémité
Définition graphes et matrice
La matrice associée à un graphe d’ordre n dont les sommets sont numérotés de 1 à n est la matrice carrée d’ordre n où l’intersection de la i-ème ligne et de la j-ème colonne aij est égal au nombre d’arêtes reliant les sommets i et j
La somme des degrés de tous les sommets d’un graphe ..
Est égale à deux fois le nombre d’arêtes
La somme des degrés de tous les sommets d’un graphe ..
Est toujours un nombre pair
Le nombre de sommets de degré impair..
Est un nombre pair
Un graphe est connexe si
Deux sommets quelconques sont toujours reliés par une chaîne
Un graphes complet est obligatoirement..
Connexe
On appelle chaîne eulérienne d’un graphe…
Toute chaîne qui contient une et une seule fois toutes les arêtes du graphe
On appelle cycle eulérien..
Une chaîne eulérienne fermée
Un graphe admet une chaîne eulérienne si et seulement si
Le nombre de sommets de degré impair est 0 ou 2
Une chaîne est
Une suite ordonnée de sommets reliés par des arêtes
La longueur d’une chaîne est
Le nombre d’arêtes qui la compose
Une chaîne est simple si
Elle n’utilise pas plus d’une fois une même arête
Une chaîne est fermée si
L’origine et l’extrémité sont confondues.
Une chaîne est élémentaire si
Elle n’utilise pas plus d’une fois le même sommet
Une chaîne eulérienne est
Une chaîne contenant toute les arêtes du graphe une et une seule fois
Un cycle est
Une chaîne fermée simple
Le terme aij à l’intersection de la i-ème ligne et j-ème colonne de la matrice A^k (k entier strictement positif) est..
Le nombre de chaînes de longueur k reliant le sommet I au sommet j
Un graphe est ..
Un ensemble de points éventuellement reliés par des lignes
