Graphe — définition ?
Représentation mathématique de sommets reliés par des arêtes.
Graphe orienté — rôle ?
Les arêtes ont une direction, indiquée par une flèche.
Degré d’un sommet — dans un graphe orienté ?
Nombre d’arcs entrant ou sortant, séparément.
Connexité — dans un graphe non orienté ?
Tous les sommets reliés par une chaîne.
Forte connexité — dans un graphe orienté ?
Chaque sommet accessible depuis tout autre.
Chemin — définition ?
Séquence d’arcs reliant deux sommets sans répétition.
Circuit — autre nom ?
Cycle, chemin fermant sur lui-même.
Représentation matricielle — principale ?
Matrice d’adjacence ou d’incidence.
Matrice d’incidence — rôle ?
Représente liens entre sommets et arcs/arêtes.
Matrice d’adjacence — dans un graphe orienté ?
a_ij = nombre d’arcs de i vers j.
Composante connexe — dans un graphe ?
Sous-ensemble maximal de sommets reliés.
Composante fortement connexe — dans un graphe orienté ?
Sous-ensemble où chaque sommet est accessible depuis tout autre.
Parcours en largeur — principe ?
Exploration par niveaux, utilisant une file.
Parcours en profondeur — principe ?
Exploration en profondeur, utilisant une pile ou récursion.
Algorithme de Kosaraju — objectif ?
Trouver les composantes fortement connexes.
Bellman-Ford — utilité ?
Trouver plus courts chemins, même avec poids négatifs.
Floyd-Warshall — utilité ?
Calculer tous les plus courts chemins entre paires.
Plus court chemin — dans un graphe pondéré ?
Chemin avec somme de poids minimale.
Cycle de poids négatif — définition ?
Circuit dont la somme des poids est négative.
Degré d’un sommet — dans un graphe non orienté ?
Nombre d’arêtes incidentes.
Teste tes connaissances avec un QCM de 10 questions sur Fondamentaux des graphes et connexité.
1. Quelle est la conséquence principale de la recherche de composantes fortement connexes dans un graphe orienté ?
2. Qu'est-ce que la théorie des graphes ?
Révisez le cours complet dans la fiche de révision de Fondamentaux des graphes et connexité.
Voir la fiche →Importe ton cours et l'IA génère des flashcards en 30 secondes.
Générateur de flashcards