Qu'est-ce qu'un graphe fini ?
Un graphe fini a un ensemble fini de sommets et d'arêtes.
Qu'est-ce qu'un graphe simple ?
Un graphe simple n'a qu'une arête au plus entre deux sommets et aucune boucle.
Quand un graphe est-il dit connexe ?
Quand on peut rejoindre tous les sommets depuis n'importe quel sommet en suivant les arêtes.
Qu'est-ce qu'un graphe biparti ?
Un graphe dont les sommets se divisent en deux ensembles reliés uniquement entre eux.
Que représentent les sommets dans un graphe d'intervalles ?
Des intervalles de la droite réelle.
Quand deux sommets sont-ils reliés dans un graphe d'intervalles ?
Quand les intervalles correspondants se chevauchent.
Qu'est-ce que le degré d'un sommet v ?
Le nombre d'arêtes incidentes à v, une boucle comptant double.
Quelle est la formule de la somme des degrés des sommets d'un graphe ?
Elle est égale à , où m est le nombre d'arêtes.
Qu'est-ce qu'une chaîne dans un graphe ?
Une suite alternée de sommets et d'arêtes commençant et finissant par un sommet.
Quand une chaîne est-elle élémentaire ?
Quand chaque sommet y apparaît au plus une fois.
Quand une chaîne est-elle simple ?
Quand chaque arête y apparaît au plus une fois.
Qu'est-ce qu'un cycle dans un graphe ?
Une chaîne fermée et simple.
Quelle est la formule du nombre cyclomatique ?
avec m arêtes, n sommets, p composantes connexes.
Quand le nombre cyclomatique est-il nul ?
Si et seulement si le graphe est sans cycle.
Qu'est-ce qu'un graphe eulérien ?
Un graphe possédant un cycle passant une seule fois par chacune de ses arêtes.
Qu'est-ce qu'un graphe hamiltonien ?
Un graphe possédant un cycle passant une seule fois par chacun de ses sommets.
Un graphe avec un sommet de degré 1 peut-il être hamiltonien ?
Non, il ne peut pas être hamiltonien.
Que doivent faire les deux arêtes incidentes à un sommet de degré 2 dans un graphe hamiltonien ?
Elles doivent appartenir au cycle hamiltonien.
Selon le théorème d'Ore, quelle condition garantit qu'un graphe simple d'ordre n>3 est hamiltonien ?
Pour toute paire de sommets non adjacents x et y, on a d(x)+d(y)>n.
Qui a formulé le théorème donnant une condition suffisante pour qu'un graphe soit hamiltonien ?
Ore.
Qu'est-ce qu'un couplage dans un graphe ?
Un ensemble d’arêtes deux à deux non adjacentes.
Quelle propriété caractérise un couplage maximum ?
Il contient le plus grand nombre possible d’arêtes.
Qu'impose un couplage parfait sur les sommets du graphe ?
Il sature tous les sommets du graphe.
Selon le théorème de Berge (1957), quand un couplage est-il maximum ?
S'il n’existe aucune chaîne augmentante relativement à ce couplage.
Qui a formulé le théorème caractérisant les couplages maximum en 1957 ?
Berge.
Quelle est la formule d’Euler pour une carte connexe ?
Que représentent S, A et R dans la formule d’Euler ?
S est le nombre de sommets, A le nombre d’arêtes, R le nombre de régions.
Qui a établi la formule d’Euler en 1752 ?
Euler.
Qu'est-ce qu'un arbre en théorie des graphes ?
Un arbre est un graphe connexe sans cycle.
Comment appelle-t-on un graphe sans cycle mais non connexe ?
Une forêt.
Quelles propriétés sont équivalentes pour un graphe à n sommets ?
Être un arbre, être connexe avec n−1 arêtes, et relier chaque paire de sommets par une unique chaîne simple.
Combien de sommets pendants possède tout arbre fini avec au moins deux sommets ?
Au moins deux sommets pendants.
Comment obtient-on le codage de Prüfer d’un arbre à n sommets ?
En supprimant successivement la feuille de plus petit numéro et en ajoutant son voisin à la suite.
Quelle est la longueur de la suite du codage de Prüfer pour un arbre à n sommets ?
Une suite de n−2 termes.
Quelle formule donne le nombre d’arbres sur n sommets numérotés ?
Le nombre est égal à .
Qui a établi en 1857 la formule du nombre d’arbres sur n sommets ?
Cayley, en 1857.
Qu'est-ce qu'un arbre couvrant d'un graphe ?
Un graphe partiel contenant tous les sommets et formant un arbre.
Comment l'algorithme de Kruskal construit-il un arbre couvrant minimal ?
En triant les arêtes par poids croissant et en ajoutant celles sans cycle jusqu'à n−1 arêtes.
Quelle année a vu la publication de l'algorithme de Kruskal ?
1956.
Qu'impose une coloration des sommets dans un graphe ?
Deux sommets adjacents ont des couleurs différentes.
Qu'est-ce que le nombre chromatique γ(G) d'un graphe ?
Le plus petit nombre de couleurs pour partitionner ses sommets en stables.
Quelle inégalité lie le nombre chromatique γ(G) au degré maximum r ?
Quelle autre inégalité lie γ(G) au nombre de stabilité α(G) et au nombre de sommets n ?
Quelle borne inférieure pour le nombre chromatique γ(G) utilise la taille de la plus grande clique ?
Quelle est la première étape de l'algorithme de Welsh et Powell ?
Classer les sommets par degrés décroissants.
Comment l'algorithme de Welsh et Powell attribue-t-il les couleurs ?
Il colore un sommet non coloré puis tous les sommets non adjacents avec cette couleur.
Quelle affirmation célèbre sur la coloration des graphes planaires a été démontrée par Appel et Haken en 1976 ?
Tout graphe planaire sans boucle se colore avec au plus quatre couleurs.
Comment l'algorithme de Welsh et Powell colore-t-il les sommets ?
Il attribue une nouvelle couleur au premier sommet non coloré puis aux sommets non adjacents déjà colorés avec cette couleur.
Qu'est-ce qu'un graphe parfait selon Claude Berge ?
Un graphe où pour tout sous-graphe induit, le nombre chromatique égale la taille de la plus grande clique.
Qui a défini le concept de graphe parfait en 1960 ?
Claude Berge.
Que garantit le théorème des quatre couleurs d'Appel et Haken ?
Tout graphe planaire sans boucles peut être coloré avec au plus quatre couleurs.
Quelle condition de coloration impose le théorème des quatre couleurs ?
Les extrémités de chaque arête ont des couleurs différentes.
Qu'est-ce que l'indice chromatique d'un graphe ?
Le plus petit nombre de couleurs pour colorer les arêtes sans que deux adjacentes aient la même couleur.
Qu'est-ce qu'un graphe triangulé ?
Un graphe où chaque cycle de plus de trois sommets a une corde.
Quand un sommet est-il simplicial ?
Quand son voisinage forme une clique.
Quelle condition caractérise un graphe connexe triangulé ?
Tout séparateur minimal est une clique.
Quel algorithme reconnaît un graphe triangulé selon Fulkerson et Gross ?
L'algorithme supprimant successivement des sommets simpliciaux.
Que signifie que le graphe résiduel devienne vide dans l'algorithme de Fulkerson et Gross ?
Le graphe initial est triangulé.
Que signifie qu'il reste un graphe sans sommet simplicial dans l'algorithme de Fulkerson et Gross ?
Le graphe initial n'est pas triangulé.
Qui a proposé l'algorithme de reconnaissance des graphes triangulés en 1969 ?
Fulkerson et Gross.
Qu'est-ce qu'un digraphe fini G=(V,E) ?
Un digraphe fini est un graphe avec un ensemble fini de sommets V et d’arcs E, chaque arc étant une paire ordonnée de sommets.
Que compte le degré extérieur d⁺(v) dans un digraphe ?
Le degré extérieur d⁺(v) compte les arcs dont v est l’extrémité initiale.
Que compte le degré intérieur d⁻(v) dans un digraphe ?
Le degré intérieur d⁻(v) compte les arcs dont v est l’extrémité finale.
Quelle relation lie le degré total d(v) aux degrés orientés ?
Le degré total vérifie .
Qu'est-ce qu'un chemin orienté dans un digraphe ?
Un chemin orienté est une suite alternée de sommets et d’arcs commençant et finissant par un sommet, chaque arc allant de son sommet origine vers son sommet destination.
Comment est définie la distance d(x,y) dans un digraphe ?
La distance d(x,y) est la longueur du plus court chemin de x vers y.
Que vaut la distance d(x,y) si aucun chemin de x vers y n’existe ?
La distance vaut ∞ si aucun chemin de x vers y n’existe.
Qu'est-ce qu'un circuit dans un graphe orienté ?
Un circuit est un chemin dont le sommet de départ et de fin coïncident.
Qu'impose la forte connexité dans un digraphe ?
Chaque paire ordonnée de sommets distincts est reliée par au moins un chemin.
Que signifie qu'un sommet soit atteignable dans un digraphe fortement connexe ?
Chaque sommet est atteignable depuis tous les autres sommets.
Qu'est-ce qu'une composante fortement connexe ?
Un sous-graphe induit maximal fortement connexe.
Qu'est-ce qu'un tournoi en théorie des graphes ?
Un digraphe complet.
Quelle propriété importante possède tout tournoi ?
Tout tournoi admet un chemin hamiltonien.
Qui a montré qu'un tournoi admet toujours un chemin hamiltonien ?
Landau en 1953.
Qu'est-ce qu'une matrice d’adjacences d’un digraphe ?
C'est une matrice carrée où l'entrée (i,j) vaut 1 si un arc va de i vers j, sinon 0.
Pourquoi la diagonale d'une matrice d’adjacences d’un digraphe simple contient-elle que des zéros ?
Parce qu'un 1 diagonal représenterait une boucle.
Qu'est-ce qu'un graphe de comparabilité ?
Un graphe dont les arêtes peuvent être orientées transitivement.
Que signifie l'orientation transitive dans un graphe de comparabilité ?
Les arcs i vers j et j vers k entraînent l'existence de l'arc i vers k.
Quelle condition caractérise un digraphe sans circuit ?
Il existe un rang r(v) pour chaque sommet avec r(u)<r(v) pour tout arc (u,v).
Teste tes connaissances avec un QCM de 46 questions sur Introduction à la théorie des graphes.
1. Dans un graphe non orienté, comment une arête reliant deux sommets est-elle représentée ?
2. Quelle propriété caractérise un graphe simple ?
Révisez le cours complet dans la fiche de révision de Introduction à la théorie des graphes.
Voir la fiche →Importe ton cours et l'IA génère des flashcards en 30 secondes.
Générateur de flashcards