Flashcards: Fondamentaux des graphes et connexité — 20 cards

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.