QCM : Introduction à la théorie des graphes — 46 questions

Explication

Une arête non orientée est une paire non ordonnée, car ses deux extrémités n’ont pas de sens imposé. La représentation par un couple ordonné caractérise plutôt une arête orientée.

Explication

Un graphe simple n’a ni boucle ni arêtes multiples entre une même paire de sommets. La présence obligatoire d’une arête entre chaque paire correspondrait à une propriété de graphe complet.

Explication

La connexité signifie qu’un chemin permet de relier chaque sommet à chacun des autres. Une connexité ne nécessite ni degrés égaux, ni arêtes directes entre toutes les paires, ni cycle commun.

Explication

Dans un graphe biparti, les extrémités de chaque arête appartiennent à des ensembles différents. Les ensembles n’ont pas besoin d’avoir la même taille, et toutes les liaisons entre eux ne sont pas requises.

Explication

Le degré compte les arêtes incidentes au sommet, avec une boucle comptée deux fois. Le nombre de voisins ou de chemins peut différer du degré, notamment en présence de boucles ou de chemins multiples.

Explication

Chaque arête contribue deux aux degrés de ses extrémités, donc la somme vaut $2m=2\times7=14$. La valeur $7$ compterait chaque arête une seule fois, ce qui ne correspond pas à la somme des degrés.

Explication

Une chaîne alterne les sommets et les arêtes, chaque arête étant encadrée par ses extrémités, avec un sommet au début et à la fin. Une simple liste d’arêtes ne précise pas les incidences nécessaires à cette structure.

Explication

Une chaîne élémentaire ne répète aucun sommet, alors qu’une chaîne simple ne répète aucune arête. La fermeture n’est pas le critère de définition de ces deux propriétés, même si un cycle est une chaîne fermée et simple.

Explication

Un graphe eulérien contient un cycle qui utilise chaque arête exactement une fois. Le parcours de chaque sommet une seule fois définit plutôt la propriété hamiltonienne.

Explication

Un graphe hamiltonien possède un cycle passant exactement une fois par chacun de ses sommets. Le parcours exact de toutes les arêtes relève de la propriété eulérienne, et des degrés égaux ne suffisent pas à garantir l’hamiltonicité.

Explication

Le théorème d’Ore exige que la somme des degrés dépasse $n$ pour toute paire de sommets non adjacents. La condition portant sur chaque sommet avec un degré supérieur à $n/2$ relève de l’idée de Dirac, tandis que les autres formulations ciblent mal les paires concernées.

Explication

Un couplage est constitué d’arêtes qui ne partagent aucun sommet, ce qui revient à former un sous-graphe partiel 1-régulier. Un sous-graphe quelconque peut contenir des arêtes adjacentes et ne respecte donc pas cette condition.

Explication

Un couplage maximum possède autant d’arêtes que possible, alors qu’un couplage parfait touche tous les sommets du graphe. Ces deux propriétés peuvent coïncider, mais aucune ne définit automatiquement l’autre.

Explication

Le théorème de Berge affirme qu’un couplage est maximum si et seulement s’il n’existe pas de chaîne augmentante relativement à lui. La saturation de tous les sommets décrit plutôt un couplage parfait et n’est pas nécessaire pour être maximum.

Explication

La formule d’Euler donne $S-A+R=2$, donc $R=2-S+A=2-8+12=6$. La valeur $R=5$ résulterait d’une soustraction incorrecte des arêtes.

Explication

Un arbre combine la connexité et l’absence de cycle. Une forêt conserve l’absence de cycle, mais elle peut comporter plusieurs composantes connexes.

Explication

Un graphe à $n$ sommets est un arbre si et seulement s’il est connexe avec $n-1$ arêtes, entre autres caractérisations équivalentes. La présence d’un cycle ou de plusieurs chaînes entre une même paire de sommets contredit la structure arborescente.

Explication

Le codage de Prüfer contient $n-2$ termes, produits par les suppressions successives de feuilles. Le nombre $n-1$ correspond au nombre d’arêtes d’un arbre, et non à la longueur du codage.

Explication

Un arbre couvrant est un graphe partiel qui conserve tous les sommets du graphe initial et qui est connexe sans cycle. Il ne doit donc pas contenir toutes les arêtes ni plusieurs chemins distincts entre une même paire.

Explication

Kruskal examine les arêtes dans l’ordre croissant de leur poids et conserve une arête lorsqu’elle ne forme pas de cycle, jusqu’à obtenir $n-1$ arêtes. Un ordre arbitraire ou décroissant ne garantit pas un poids total minimal.

Explication

Une coloration valide exige que les extrémités de chaque arête aient des couleurs différentes. Des sommets non adjacents peuvent partager une couleur, car ils ne sont pas directement en conflit.

Explication

Le nombre chromatique est le minimum de couleurs nécessaire pour répartir les sommets en ensembles stables. Une coloration particulière peut employer davantage de couleurs sans atteindre ce minimum.

Explication

Les deux inégalités donnent $\gamma(G)\le r+1=5$ et $\gamma(G)\le n+1-\alpha(G)=8$. La borne issue du degré maximal et celle issue du nombre de stabilité sont donc respectivement 5 et 8.

Explication

Les sommets d’une clique sont deux à deux adjacents et doivent donc recevoir des couleurs distinctes, ce qui impose $\gamma(G)\ge\omega(G)=6$. Cette information ne suffit pas à établir une égalité ou une borne supérieure.

Explication

Welsh et Powell commence par trier les sommets selon des degrés décroissants, puis attribue une couleur au premier sommet non coloré et la réutilise sur des sommets compatibles. Ce procédé fournit une coloration, mais ne garantit pas forcément le nombre chromatique minimal.

Explication

La perfection impose, pour tout sous-graphe induit $G'$, l’égalité $\gamma(G')=\omega(G')$. Une égalité vérifiée par le graphe initial ne suffit pas pour conclure que le graphe est parfait.

Explication

Le théorème concerne la coloration des sommets d’un graphe planaire et assure une utilisation d’au plus quatre couleurs avec des couleurs différentes aux extrémités de chaque arête. Il ne porte pas directement sur la coloration des arêtes ou des faces.

Explication

L’indice chromatique concerne les arêtes : deux arêtes adjacentes, c’est-à-dire incidentes à un même sommet, doivent avoir des couleurs différentes. La coloration des sommets relève du nombre chromatique $\gamma(G)$.

Explication

Dans un graphe triangulé, chaque cycle de longueur supérieure à trois contient une corde, c’est-à-dire une arête entre deux sommets non consécutifs du cycle. Une arête du cycle lui-même ne constitue donc pas une corde.

Explication

Un sommet est simplicial lorsque tous les sommets de son voisinage sont deux à deux adjacents, de sorte que $N(v)$ est une clique. Un faible degré ne garantit pas cette adjacence complète entre voisins.

Explication

Un graphe connexe est triangulé si et seulement si chacun de ses séparateurs minimaux est une clique. Les autres propriétés ne décrivent pas cette équivalence et confondent séparateurs et cycles ou cliques.

Explication

L’algorithme supprime successivement des sommets simpliciaux ; si un graphe résiduel non vide n’en possède aucun, le graphe initial n’est pas triangulé. La suppression complète jusqu’au graphe vide est au contraire le critère de reconnaissance.

Explication

Un digraphe fini comprend un ensemble fini de sommets et un ensemble d’arcs, chaque arc étant une paire ordonnée de sommets. Une matrice ou une collection de chemins peut représenter un digraphe, mais ne constitue pas sa définition.

Explication

Le degré intérieur compte les arcs entrants, c’est-à-dire ceux dont le sommet v est l’extrémité finale. Le degré extérieur compte au contraire les arcs sortants dont v est l’extrémité initiale.

Explication

Un chemin orienté suit chaque arc dans son sens, de l’origine vers la destination. Le retour au sommet de départ caractérise un circuit, tandis que l’inversion du sens concerne une chaîne non orientée.

Explication

Un circuit est un chemin dont le sommet initial et le sommet final sont identiques. Passer par tous les sommets décrit plutôt un chemin hamiltonien, tandis que les autres réponses concernent des propriétés de connexité ou de complétude.

Explication

La forte connexité exige qu’un chemin existe entre chaque paire ordonnée de sommets distincts, donc dans les deux directions selon les sommets considérés. La présence d’arcs sortants ne garantit pas cette propriété, et elle tient précisément compte de l’orientation.

Explication

L’entrée (i,j) vaut 1 si le digraphe contient l’arc orienté de i vers j, et 0 sinon. Inverser i et j décrit l’arc opposé, qui n’est pas automatiquement présent dans un digraphe orienté.

Explication

Un graphe de comparabilité est un graphe dont les arêtes peuvent être orientées de manière transitive : les arcs de i vers j et de j vers k imposent alors un arc de i vers k. Le classement par degrés ou la réversibilité des arcs ne définit pas cette notion.

Explication

Un digraphe est sans circuit si et seulement s’il admet un rang strictement croissant le long de chaque arc. Un tel rang interdit le retour à un sommet déjà atteint, tandis que les relations entre degrés ne suffisent pas à exclure les circuits.

Explication

Dijkstra calcule les plus courts chemins dans un graphe pondéré dont les poids d’arcs sont positifs. La présence de poids négatifs peut invalider sa sélection gloutonne, même si le graphe reste connexe.

Explication

Dijkstra examine les successeurs du sommet sélectionné et améliore leurs distances par relaxation. Choisir la plus grande distance ou modifier globalement toutes les distances ne fait pas partie de cette procédure.

Explication

Un réseau PERT représente chaque tâche par un arc pondéré par sa durée, tandis que les sommets représentent les événements. Inverser les rôles des arcs et des sommets constitue la confusion classique sur cette modélisation.

Explication

Un circuit imposerait qu’une tâche précède et suive simultanément une autre tâche, ce qui crée une dépendance impossible à ordonnancer. Il ne signifie pas que toutes les activités deviennent critiques ni qu’elles perdent leur durée.

Explication

La date au plus tôt d’un sommet est le maximum des dates de ses prédécesseurs augmentées des durées des arcs correspondants, avec $\delta_1=0$. Le minimum est utilisé dans le calcul des dates au plus tard en remontant le réseau.

Explication

Un chemin critique va de 1 à n et est composé uniquement d’arcs critiques ; le retard d’une activité critique retarde la fin du projet. Une durée minimale ou un grand nombre de successeurs ne suffit pas à définir ce chemin.