NEW
Font size
WorksheetsChaines et cycles (Introduction)
Total questions: 73
Worksheet time: 37mins
Dans l’organisation de ce chapitre de théorie des graphes, quelle section est annoncée comme la première à être étudiée avant les suivantes (Graphes connexes, Arbres, Graphe Eulérien, Graphes Hamiltonien, Coloration des sommets d’un graphe, Graphes spéciaux, Problèmes) ?
Chaines et cycles
Graphes connexes
Arbres
Graphe Eulérien
Dans un graphe G, une chaîne entre v et w est définie comme une séquence finie alternant sommets et arêtes. Laquelle des écritures capture correctement cette définition formelle ?
v = v0, e1, v1, e2, v2, …, en, vn = w avec ei reliant vi−1 et vi
v = v0, v1, v2, …, vn = w sans mention des arêtes
v = e0, e1, e2, …, en avec chaque ei reliant e(i−1) et ei
v = v0, e1, e2, …, en, vn = w avec les arêtes ne reliant aucun sommet
Dans le contexte des graphes, quelle est la règle concernant la répétition des sommets et des arêtes dans une chaîne ?
Ils peuvent se répéter
Seuls les sommets peuvent se répéter, pas les arêtes
Seules les arêtes peuvent se répéter, pas les sommets
Ni les sommets ni les arêtes ne peuvent se répéter
Deux chaînes v0, e1, v1, …, en, vn et u0, f1, u1, …, fm, um sont considérées comme équivalentes si et seulement si :
n = m, vi = ui et ei = fi pour 0 ≤ i ≤ n
n = m uniquement, sans tenir compte des sommets et des arêtes
elles possèdent les mêmes sommets, peu importe l'ordre
elles possèdent les mêmes arêtes, l'ordre peut varier
Quel terme désigne une séquence qui débute et se termine au même point ?
Chaîne fermée
Parcours
Chemin élémentaire
Cycle impair
Quelle est la définition de la longueur d’une chaîne donnée ?
Le nombre d’arêtes dans la chaîne
Le nombre de sommets distincts dans la chaîne
La somme des degrés des sommets visités
La distance géométrique entre les extrémités
Une séquence où aucune arête n’est répétée est désignée par :
Parcours (chaîne simple)
Chemin (chaîne élémentaire)
Circuit
Chaîne fermée
Quel terme désigne un parcours qui commence et se termine au même sommet ?
Circuit
Cycle
Chemin élémentaire
Chaîne fermée non simple
Une séquence dans laquelle aucun nœud n’est répété (et donc aucune connexion n’est répétée) est désignée par :
Chemin ou chaîne élémentaire
Parcours ou chaîne simple
Cycle pair
Circuit fermé non élémentaire
Quel terme désigne un chemin qui relie spécifiquement les sommets u et v ?
Chemin u − v
Parcours u → v
Cycle u ↺ v
Chaîne fermée u ↔ v
Dans un chemin a − b, quels sont les sommets qui se trouvent entre a et b ?
Sommets intermédiaires
Sommets terminaux
Sommets pendants
Sommets isolés
Quel terme désigne un chemin qui commence et se termine au même sommet ?
Cycle
Parcours
Chaîne fermée uniquement
Chemin élémentaire
Dans un graphe simple G, comment désigne-t-on un cycle qui contient k sommets ?
k-cycle dans G
Ck sans référence à G
Cycle de longueur k uniquement si k est pair
Chemin élémentaire de taille k
Dans le cadre de la théorie des graphes, qu'est-ce qui caractérise un cycle impair ?
Lorsque le nombre de sommets est impair
Lorsque le nombre de sommets est pair
Lorsqu’il contient au moins une arête répétée
Lorsqu’il contient au moins un sommet répété
Quelle relation hiérarchique correcte est explicitement énoncée entre chemin, parcours et chaîne ?
Un chemin est aussi un parcours, et un parcours est aussi une chaîne
Un parcours est aussi un cycle, et un cycle est aussi une chaîne
Une chaîne est toujours un chemin, mais pas un parcours
Un cycle est toujours un parcours, mais jamais une chaîne
[Application] Lequel des suivants est un parcours qui n’est pas un chemin, d’après les résultats donnés?
T = (e, c, b, a, f, c, d)
T = (e, b, c, d)
T = (b, c, e, d)
T = (e, d, c, b, a)
DoK 1 — Rappel: Dans un graphe orienté G, quel énoncé décrit correctement un chemin orienté de v à w ?
Une suite quelconque de sommets reliant v et w, sans contrainte d’orientation des arêtes
Une séquence finie de sommets et d’arcs de G allant de v à w, où chaque arc est orienté de son sommet précédent vers le suivant
Une suite infinie d’arcs alternant les sens pour finir à w
Un ensemble non ordonné d’arcs incident aux sommets v et w
DoK 2 — Application de la définition: Considérons la séquence v0, a1, v1, a2, v2, a3, v3 avec v0 = v et v3 = w dans un graphe orienté. Laquelle des conditions suivantes doit être vraie pour que cette séquence soit une chaîne orientée de v à w ?
Chaque arc ai est un arc allant de vi à vi−1
Chaque arc ai est un arc allant de vi−1 à vi
Il suffit qu’au moins un arc ai soit orienté de vi−1 à vi
Les arcs peuvent être non orientés si les sommets sont distincts
DoK 2 — Concept relié: Parmi les termes suivants, lequel est spécifiquement associé aux graphes orientés selon le texte ?
Parcours orienté
Parcours eulérien non orienté
Arbre couvrant minimal
Couplage maximal
DoK 3 — Raisonnement: Quelle méthode peut-on utiliser pour garantir qu'un chemin orienté est construit de manière correcte entre deux sommets v et w ?
Prendre n'importe quelle séquence de sommets de v à w et ajouter des arêtes non orientées là où il manque des connexions
À chaque étape i, choisir un arc orienté existant de vi−1 vers vi et continuer jusqu'à atteindre w
Permettre des allers-retours en inversant le sens des arcs pour optimiser la séquence
Accepter des arcs multiples, en ignorant ceux dont l'orientation est opposée, car seule la présence d'un lien est importante
Rappel: Un graphe (simple) avec trois sommets ou plus est biparti si et seulement s’il n’a pas de cycles impairs. Laquelle des affirmations décrit correctement la contraposée utile pour détecter qu’un graphe n’est pas biparti?
S’il y a un cycle pair, alors le graphe n’est pas biparti.
S’il existe au moins un cycle impair, alors le graphe n’est pas biparti.
S’il n’y a aucun cycle, alors le graphe n’est pas biparti.
S’il y a un chemin de longueur paire, alors le graphe n’est pas biparti.
Quelle condition est nécessaire et suffisante pour qu’un graphe simple à au moins trois sommets soit biparti selon le théorème de caractérisation?
Il peut être colorié avec trois couleurs distinctes.
Il n’a pas de cycles de longueur 4.
Il ne contient aucun cycle impair.
Tous ses degrés de sommets sont égaux.
Considérez un graphe biparti avec des sommets alternant entre deux ensembles. Quel principe fondamental est illustré par la structure de ce graphe?
Dans un graphe biparti, tout cycle doit être de longueur impaire pour alterner les parties.
Dans un graphe biparti, un cycle peut alterner entre deux ensembles de sommets, donc sa longueur est paire.
Dans un graphe biparti, l’alternance entre les ensembles est impossible sur un cycle.
Dans un graphe biparti, seuls les cycles de longueur 3 sont autorisés.
La figure indique « Figure 3: Dans un graphe bipartie, les cycles sont pairs ». Quelle conclusion correcte en découle pour un cycle C7 (longueur 7) apparaissant dans un graphe G?
G est biparti car 7 est premier.
G n’est pas biparti car il contient un cycle impair.
G est biparti seulement si C7 est isolé du reste du graphe.
On ne peut rien conclure sur la bipartition de G à partir d’un C7.
Dans le graphe complet biparti K2,3, quelle caractéristique fondamentale peut-on observer?
Il existe une arête entre deux sommets de la même partie.
Toutes les arêtes relient un sommet de la partie X à un sommet de la partie Y.
Chaque sommet de Y a exactement deux arêtes sortantes vers Y.
Le graphe contient un triangle reliant deux sommets de X et un sommet de Y.
Dans le contexte des réseaux d’ordinateurs, quel est l'objectif principal de la connectivité des graphes ?
À évaluer la robustesse et la sécurité
À optimiser le flux de données
À sécuriser les échanges entre utilisateurs
À attribuer des couleurs aux nœuds avec un nombre minimal de teintes
Dans un graphe non orienté, quelle condition doit être remplie pour qu'une paire de sommets soit considérée comme connectée ?
Il doit exister un chemin reliant ces deux sommets
Ils doivent avoir le même degré
Ils doivent partager un voisin commun
Ils doivent appartenir à des composants distincts
Complétez la définition: Un graphe G est dit connexe si et seulement si ______.
toutes les paires de sommets de G sont connectées
chaque sommet a au moins deux voisins
il n’existe aucun cycle simple
son nombre d’arêtes est maximal
Quel est un trait distinctif d'un graphe qui n'est pas connexe ?
Il peut être divisé en plusieurs sous-ensembles de sommets
Il ne présente ni cycles ni boucles
Tous ses sommets ont un degré identique
Il existe un chemin unique entre chaque paire de sommets
Dans un graphe non‑connexe, que désigne formellement un « composant » ?
Le plus grand sous‑graphe connexe
Un sommet de degré maximal
Une arête critique séparant deux cycles
Un chemin simple de longueur minimale
Énonce correcte: « Un graphe est connexe si et seulement si le nombre de ses composants est… »
un
deux
au moins deux
égal au nombre de sommets
Dans un graphe orienté, qu'est-ce qui définit une forte connexité ?
S'il existe un chemin orienté entre chaque paire de sommets
Si chaque arête a une direction unique
S'il existe un chemin non orienté entre tous les sommets
S'il contient au moins un cycle hamiltonien
Qu’est‑ce qu’une composante fortement connexe d’un graphe orienté G ?
Un sous‑graphe de G où, pour tous u et v de ce sous‑graphe, il existe un chemin orienté entre u et v
Un sous‑graphe sans arêtes sortantes
Le sous‑graphe induit par les sommets de degré maximal
Un sous‑graphe acyclique couvrant
Dans un graphe non orienté, si tous les sommets sont connectés par des arêtes, quelle propriété globale est vérifiée ?
Chaque paire de sommets est reliée par au moins un chemin
Le graphe se décompose en plusieurs composants disjoints
Il existe au moins un cycle dans ce graphe
Toutes les arêtes sont orientées dans une seule direction
Dans un graphe G = (V, E), quel terme désigne un sous-ensemble F ⊆ E qui, lorsqu'il est retiré, laisse le graphe G avec plus d'un composant connexe ?
Un ensemble de déconnexion
Un sous-graphe générateur
Un couplage maximal
Un découpage par sommets
Dans un graphe, si F est un ensemble de déconnexion constitué d’une seule arête f, quel est le terme approprié pour désigner f ?
Pont (ou isthme)
Arête multiple
Boucle
Arête coupante par sommet
La connectivité d’arêtes λ(G) d’un graphe G est définie comme :
La taille minimale d’un ensemble de déconnexion de G
Le degré maximal des sommets de G
Le nombre total d’arêtes moins le nombre de sommets
La taille maximale d’un couplage dans G
Quelle est la définition correcte de λ(G) dans le contexte des graphes ?
λ(G) représente le nombre minimal d’arêtes dont la suppression rend G non connexe
λ(G) correspond au nombre d’arêtes incidentes au sommet ayant le degré maximal
λ(G) est toujours supérieur à zéro pour tous les graphes
λ(G) est identique au diamètre du graphe G
Dans quel cas λ(G) est-il égal à 0 selon la définition fournie ?
Si et seulement si G est non connexe ou trivial (K1)
Uniquement lorsque G est un cycle simple
Lorsque G est complet sur au moins deux sommets
Si et seulement si G est biparti et connexe
Considérez un graphe avec des arêtes étiquetées de a à e. Parmi les ensembles suivants, lequel constitue un ensemble de déconnexion de taille 2 ?
{a, b}
{a, c}
{a, d}
{d, e}
Pour le graphe illustré (carré avec une diagonale), quel est le nombre de connectivité d’arêtes λ(G) ?
2
1
3
4
Quelle écriture correcte exprime λ(G) en fonction des ensembles de déconnexion F ?
λ(G) = min(|F| : G − F non connexe)
λ(G) = max(|F| : G − F connexe)
λ(G) = min(|F| : G − F connexe)
λ(G) = max(|F| : G − F non connexe)
Rappel: On considère un graphe G = (V, E). Comment est défini un ensemble de séparation W dans G ?
Un sous-ensemble de sommets dont la suppression rend G − W avec plus d’un composant
Un sous-ensemble d’arêtes dont la contraction réduit le degré minimum
Un sous-ensemble de sommets induisant un sous-graphe complet
Un sous-ensemble d’arêtes dont la suppression crée exactement un cycle
Quel terme désigne un ensemble de séparation constitué d’un seul sommet w dans un graphe G ?
Sommet d’articulation
Sommet dominant
Sommet coupure d’arêtes
Sommet isolé
Quelle est la définition correcte du nombre de connexité κ(G) d’un graphe G ?
La taille minimale d’un ensemble de séparation de G
Le nombre maximal de composantes de G
Le degré minimum des sommets de G
Le nombre d’arêtes nécessaires pour rendre G eulérien
Théorème (Inégalité de Whitney). Complétez l’énoncé correct: pour tout graphe G,
κ(G) ≤ λ(G) ≤ δ(G)
δ(G) ≤ λ(G) ≤ κ(G)
λ(G) ≤ κ(G) ≤ δ(G)
κ(G) = λ(G) = δ(G)
Selon la définition donnée, qu’est-ce qu’un graphe acyclique (aussi appelé forêt) ?
Un graphe sans cycles
Un graphe complet et connexe
Un graphe orienté avec au moins un cycle
Un graphe biparti avec cycles autorisés
Quelle affirmation caractérise correctement un arbre dans la théorie des graphes présentée ?
Un arbre est un graphe connexe acyclique
Un arbre est un graphe avec exactement un cycle
Un arbre est un graphe connexe contenant tous les cycles possibles
Un arbre est un graphe orienté fortement connexe
D’après les propriétés énoncées, laquelle des propositions suivantes est vraie à propos d’une forêt et de ses composants ?
Chaque composant d’une forêt est un arbre, et tout arbre est une forêt connexe
Chaque composant d’une forêt est un cycle, et tout arbre contient un cycle
Une forêt ne peut pas être décomposée en arbres
Tout arbre est forcément non connexe
Parmi les énoncés suivants, lequel correspond à un exemple d’application des arbres mentionné ?
Déterminer le chemin le plus court dans un réseau de transport
Chiffrer des messages par substitution monoalphabétique
Calculer la transformée de Fourier discrète
Rendre un graphe complet par ajout d’arêtes minimales
Le texte précise qu’un chemin P_n est :
Un arbre particulier
Un cycle élémentaire
Un graphe biparti complet
Une composante non connexe
Quel énoncé est conforme aux définitions données concernant les classes de graphes ?
Un arbre est un graphe simple et un type particulier de graphe biparti
Un arbre est toujours orienté et non simple
Tout graphe biparti est un arbre simple
Un graphe simple contient nécessairement au moins un cycle
En observant la figure inférieure montrant un triangle entre les sommets 1–2–3 et un sommet 4 isolé, pourquoi ce graphe n’est-il pas un arbre?
Parce qu’il possède au moins deux composantes et aucun cycle
Parce qu’il contient un cycle et n’est pas connexe
Parce qu’il est trop dense et contient toutes les arêtes possibles
Parce qu’il est biparti et possède un pont
Parmi les énoncés suivants, lequel définit correctement un arbre dans le cadre de la théorie des graphes?
Un graphe connexe et sans cycle
Un graphe où tous les sommets ont le même degré
Un graphe avec exactement un cycle
Un graphe complet de n sommets
Selon le théorème des propriétés des arbres, quelles sont deux conditions équivalentes caractérisant un arbre en termes de connexité et du nombre d’arêtes m et de sommets n?
G est connexe et m = n − 1
G est acyclique et m = n + 1
G est 2-connexe et m = n − 2
G est eulérien et m = n − 1
Choisissez l’énoncé correct à propos de la suppression d’une arête dans un arbre.
La suppression de n’importe quelle arête déconnecte le graphe
La suppression d’une arête réduit le nombre de cycles mais conserve la connexité
La suppression d’une arête augmente le degré de deux sommets
La suppression d’une arête ne change jamais le nombre de composantes
Le théorème affirme qu’entre deux sommets quelconques d’un arbre:
Il existe exactement une seule chaîne élémentaire
Il existe au moins deux chemins disjoints
Il n’existe aucun chemin si les sommets sont de degré 1
Il existe un nombre infini de chemins distincts
Laquelle des affirmations suivantes est équivalente au fait qu’un graphe est un arbre en ajoutant une arête?
Le graphe est acyclique, mais si on ajoute une arête, un cycle apparaît
Le graphe est connexe, et l’ajout d’une arête le déconnecte
Le graphe est complet, et l’ajout d’une arête réduit m
Le graphe contient déjà un cycle, et l’ajout d’une arête le supprime
Parmi les propositions suivantes, laquelle montre qu’un graphe n’est pas nécessairement un arbre même si m = n − 1?
Un graphe non connexe composé de deux chemins disjoints dont le total des arêtes vérifie m = n − 1
Un graphe connexe avec un cycle et m = n − 1
Un graphe complet K_n avec m = n − 1
Un graphe régulier de degré 2 avec m = n − 1
On considère un graphe simple G satisfaisant m = n − 1. Laquelle des conditions suivantes suffit, avec cette égalité, pour garantir que G est un arbre selon le théorème?
G est connexe
G est hamiltonien
G est 2-régulier
G est biparti complet
Selon la page intitulée « Graphe Eulerien », quel est le meilleur énoncé qui décrit le rôle de cette section dans un cours de théorie des graphes ?
Elle introduit la quatrième section principale consacrée aux graphes eulériens.
Elle résume l’ensemble du chapitre en présentant toutes les définitions clés.
Elle détaille les algorithmes de coloration des sommets et leurs preuves.
Elle compare en profondeur les graphes hamiltoniens et les graphes spéciaux.
Selon l’introduction, quelle application illustre la nécessité de parcourir un graphe d’une façon particulière ?
La délivrance du courrier
La compression de fichiers
Le tri rapide (quicksort)
La gestion de mémoire virtuelle
Quel principe décrit la méthode la plus simple pour traverser un graphe dans ce contexte ?
Passer chaque arête au moins deux fois pour vérifier la connectivité
Passer les rues une seule fois si c’est possible
Ignorer les sommets de degré impair
Minimiser le nombre de sommets visités
Que permet explicitement le modèle de graphe mentionné dans le texte ?
Uniquement un graphe simple sans boucles
Plusieurs arêtes entre une paire de sommets (multi-graphe)
Des arêtes dirigées uniquement
Des sommets avec degré zéro interdit
Quelle affirmation correspond à la définition d’un graphe eulérien telle qu’introduite implicitement ?
Il possède une chaîne qui visite chaque sommet exactement une fois
Il admet un cycle qui parcourt chaque arête exactement une fois
Il minimise le nombre d’arêtes entre sommets
Il contient au moins deux sommets de degré impair
Quel énoncé capture l’idée d’une chaîne eulérienne ?
Un parcours ouvert qui traverse chaque arête exactement une fois
Un parcours fermé qui répète certaines arêtes
Un parcours qui maximise le nombre de cycles
Un parcours qui évite les sommets de degré pair
Un graphe semi-eulérien est le mieux décrit par lequel des choix suivants ?
Il possède un cycle eulérien mais pas de chaîne eulérienne
Il possède au moins une chaîne eulérienne mais pas de cycle eulérien
Il possède plusieurs cycles hamiltoniens
Il ne permet pas de multi-arêtes
Dans le contexte des applications citées, quel objectif opérationnel correspond à un cycle ou une chaîne eulérienne ?
Réduire la profondeur de recherche dans un arbre
Parcourir les rues (arêtes) sans répétition pour optimiser une tournée
Maximiser le degré moyen du graphe
Transformer un graphe en une matrice d’adjacence creuse
Quel est le critère nécessaire pour qu'un graphe soit un arbre ?
Il doit contenir au moins un cycle
Il doit être connexe et acyclique
Il doit être biparti
Il doit avoir exactement un cycle
Dans un graphe orienté, quel est le degré sortant d'un sommet ?
Le nombre d'arêtes sortantes de ce sommet
Le nombre total d'arêtes incidentes à ce sommet
Le nombre de sommets adjacents à ce sommet
Le nombre d'arêtes entrantes de ce sommet
Quel est le degré d'un sommet dans un graphe si ce sommet est relié à tous les autres sommets ?
Degré minimal
Degré maximal
Degré complet
Degré nul
Dans un graphe orienté, quel terme désigne un chemin qui passe par chaque arête exactement une fois ?
Chemin simple
Chemin fermé
Chemin hamiltonien
Chemin eulérien
Quel est le nombre maximal d'arêtes dans un graphe complet avec n sommets ?
n(n-1)/2
n^2
n(n+1)/2
n-1
