Théorie des graphes Flashcards
C’est quoi un graphe (non orienté) ? Comment cela est noté ?
Ce sont deux ensemble :
- Un semble de sommets, noté V (Vertices)
- Un ensemble d’arrêtes, noté E (Edges)
Donner un exemple de boucle
Arrête uu
C’est quoi un multigraphe ?
Graphe ou la présence de plusieurs arêtes est autorisée entre chaque paire de sommets.
C’est quoi un voisin de u ?
v est voisins de u si l’arrête uv existe.
C’est quoi le voisinage de u ? Comment cela est noté ?
C’est l’ensemble des voisins de u dans G :
N_g = {u : uv dans E}
C’est quoi le degré d’un sommet u ? Comment cela est noté ?
C’est le nombre de voisin / Cardinal du voisinage d’un sommet
Noté d_G(u)
C’est quoi une feuille / sommet pendant ?
C’est un sommet de degré 1 = exactement un voisin
Comment sont noté le degré maximal et minimal d’un graphe ?
Max = DELTAMAJUSCULE_G
Min = deltaminuscule_g
C’est quoi un graphe de type cycle ? Comment cela est noté ?
Graphe dont chaque sommet et lié à un suivant afin de faire un cycle.
Noté C_n
C’est quoi un graphe complet ? Comment cela est noté ?
Graphe dont chaque sommet est lié à tous les autres.
Noté K_n
C’est quoi une grille ? Comment cela est noté ?
Graphe dont chaque sommet est lié à 4 voisins sauf les extrémités qui sont lié soit à 3 soit à deux pour les coins
GR_{pxq}
C’est quoi un tor ? Comment cela est noté ?
Grille où les “extremités” sont liées entre elle, donc chaque sommet à exactement 4 voisins
TR_{pxq}
Exprimer la somme des degré des sommets d’un graphe en fonction du nombre d’arrête
https://imgbox.com/1YTLeJiC
Donner un encadrement du nombre d’arrête en fonction du nombre de sommet
https://imgbox.com/WKX0cPzR
C’est quoi un graphe partiel ?
Un graphe partiel de G est obtenu en gardant tous les sommets de G et en retirant certaines de ses arrêtes
C’est quoi un sous-graphe de G induit par S dans V ? Comment est il noté ?
C’est un graphe obtenu en ne gardant que les sommets de S et les arrêtes de G entre les sommets de S.
G[S]
C’est quoi un chemin ? C’est quoi les extrémités du chemin ?
Un chemin entre deux sommet u et v de G est une suite d’arêtes telle que deux arrête successives partagent un sommet comment.
Les extrémités sont les premières et dernière arête du chemin.
On peut aussi noter un chemin sur les sommets.
C’est quoi la longueur d’un chemin ?
C’est le nombre d’arête d’un chemin.
S’il n’y en a aucune, la longueur vaut 0.
= NbsommetChemin -1
C’est quoi un graphe partiel de G ?
Il est obtenu en gardant tous les sommets de G et en retirant certaines arêtes
C’est quoi un sous-graphe de G induit par S inclus dans V ? Comment est t-il noté ?
Il est obtenu en ne gardant que les sommets de S et les arrête de G entre les sommets de S.
Il est noté G[S]
C’est quoi un chemin entre deux sommet u et v ? C’est quoi les extrémité de ce chemin ?
C’est une suite d’arêtes où deux arrête successive partagent un sommet commun.
Les extrémités du chemin sont les sommet à la base et à la fin du chemin (ici u et v)
On peut aussi noter un chemin comme une suite de sommet.
C’est quoi la longueur d’un chemin ?
C’est son nombre d’arête. Un chemin composé de 0 arête (entre u et u) est de longueur 0
C’est quoi un chemin simple ?
Un chemin est dit simple si les arête de cette suite sont unique.
C’est quoi un chemin élémentaire ?
Un chemin est dit élémentaire si les sommet de cette suite sont unique.
Qu’implique le fait d’être élementaire pour un chemin ?
Il est aussi simple
Qu’implique le fait d’être simple pour un chemin ?
Rien.
C’est quoi un cycle ?
C’est un chemin de longueur au moins 3 où les deux extrémités sont lié par une arrête.
C’est quoi un graphe connexe ?
Un graphe est connexe si pour tout sommet u,v il existe un chemin de u à v
C’est quoi une composante connexe ?
C’est un sous-ensemble S maximal de V tel que le sous-graphe induit par S est connexe.
A noter que si G est déjà connexe il ne contient qu’une seule composante connexe composée de tous ses sommets
C’est quoi une clique ?
Sous-ensemble de sommet de G induisant un graphe complet dans G.
C’est quoi un sommet isolé ?
Sommet de degré 0
C’est quoi un graphe vide ?
Graphe dont tous les sommets sont de degré 0 (E vide)
C’est quoi un stable (ou indépendant) ?
Sous ensemble de sommets de G induisant un graphe vide
Quelle relation y a t’il entre les clique et les stables dans un graphe G ?
Clique dans G barre = stable dans G et inversement
Avec G barre, le complémentaire de G
C’est quoi un arbre ?
C’est un graphe connexe sans cycle
Soit T = (V, E) un arbre à n sommets donner l’ensemble des propositions équivalente
- T est connexe et a n-1 arête
- T est sans cycle et a n -1 arête
- T est sans cycle et quelle que soit l’arête que l’on ajoute à T cela créer un cycle = Sans cycle maximal
- T est connexe et quelle que soit l’arête que l’on supprime on obtient un graphe non connexe = Connexe minimal
- Pour toute paire de sommet u,v T contient exactement un chemin entre u et v
Donner une façon alternative de prouver qu’un graphe est connexe
S’il contient un arbre couvrant qui contient tout ses sommet (Réciproque vraie)
“Si on peut lui enlever des arrête pour enlever les cycles en trop”
C’est quoi un arbre couvrant ?
Graphe partiel qui est un arbre
Soit T un arbre à n sommets. Donner un encadrement de son nombre de feuilles en fonction de n
2 <= nbFeuille <= n - 1
