Lorsqu’il existe une chaîne entre toute paire de sommets
Explicación
Un graphe est connexe si chaque paire de sommets peut être reliée par une chaîne. Le fait d’avoir une composante ou d’être orienté ne suffit pas à définir la connexité.
Un graphe dans lequel, pour toute paire de sommets, il existe une chaîne permettant de passer de l’un à l’autre.
Explicación
Un graphe est connexe si, pour toute paire de sommets, il existe une chaîne permettant de passer de l’un à l’autre, ce qui garantit une connexion globale.
Des sous-ensembles de sommets où la connexité existe à l’intérieur de chaque sous-ensemble
Explicación
Les composantes connexes sont des groupes de sommets tels que tout sommet du groupe est relié aux autres par des chaînes. Elles décrivent la structure d’un graphe non connexe sans parler de cycles ou de chemins minimaux.
Il existe une chaîne reliant toute paire de sommets.
Explicación
Un graphe est connexe si, pour toute paire de sommets, il existe une chaîne permettant de passer de l’un à l’autre, ce qui garantit une connexion globale.
La suite des sommets découverts ou ouverts pendant le parcours
Explicación
L’ordre de prévisite correspond à l’ordre dans lequel les sommets sont découverts, donc ouverts. L’ordre de postvisite, lui, concerne les sommets fermés.
Explorer le graphe couche par couche en utilisant une file FIFO.
Explicación
Le parcours en largeur sert principalement à explorer un graphe couche par couche en utilisant une file FIFO, ce qui permet aussi de déterminer la connexité et de calculer les plus courts chemins dans un graphe non orienté.
Successeur
Explicación
Dans un graphe orienté, on parle de successeur pour un sommet atteignable directement en suivant un arc. La notion de voisin direct est donc remplacée par celle de successeur.
Au début du cours, lors de la présentation de la structure de données
Explicación
Le recours à une file FIFO dans le parcours en largeur a été présenté dès l'introduction de cette méthode, pour assurer l'exploration progressive par couches.
Elle garantit que les sommets sont traités dans l'ordre d'arrivée, assurant une exploration par couches.
Explicación
La file FIFO assure que les sommets sont traités dans l'ordre d'arrivée, ce qui permet une exploration par couches dans le parcours en largeur, essentiel pour découvrir le graphe niveau par niveau.
E. F. Moore
Explicación
Le parcours en largeur a été formulé par E. F. Moore en 1959, permettant d'explorer systématiquement un graphe par couches.
Elle garantit que les sommets sont explorés par ordre de proximité depuis le point de départ.
Explicación
L'utilisation d'une file FIFO dans le parcours en largeur permet d'explorer les sommets par ordre de proximité, ce qui garantit une exploration couche par couche. Les autres options ne reflètent pas précisément cette propriété.
Memoriza las respuestas con 9 tarjetas de memoria sobre Introduction aux graphes et parcours.
Connexité — définition ?
Un graphe est connexe si toute paire de sommets est reliée par une chaîne.
Graphes connexes
Chaîne entre tout couple de sommets.
Composantes connexes — rôle ?
Sous-ensembles maximaux de sommets où la connexité est assurée.
Lee la hoja de repaso completa sobre Introduction aux graphes et parcours.
Ver hoja de repaso →Importa tu curso y la IA genera cuestionarios con correcciones en 30 segundos.
Generador de cuestionarios