Graphe — définition ?
Structure de sommets et d’arêtes ou arcs.
Sommet — rôle ?
Représente un point ou un acteur.
Arête — dans non-orienté ?
Connexion bidirectionnelle entre deux sommets.
Arc — dans orienté ?
Connexion avec direction entre deux sommets.
Graphe orienté — caractéristique ?
Arcs avec une direction spécifique.
Graphe non-orienté — caractéristique ?
Arêtes sans direction, relation symétrique.
Ponts de Königsberg — problème ?
Traverser chaque pont une seule fois.
Chemin eulérien — définition ?
Traverse chaque arête une seule fois.
Circuit eulérien — condition ?
Chemin eulérien qui revient au point de départ.
Histoire Euler — origine ?
Problème des ponts de Königsberg.
Exemple de graphe social ?
Facebook ou Twitter, relations entre individus.
Degré d’un sommet — dans non-orienté ?
Nombre d’arêtes incidentes.
Voisinage Γ(v) — définition ?
Sommets directement reliés à v.
Cycle — dans un graphe ?
Chaîne fermée revenant au point de départ.
Chemins et circuits — différence ?
Circuit est un chemin fermé, chemin peut être ouvert.
Forte connexité — dans orienté ?
Chemins dans les deux sens entre tous sommets.
Tri topologique — application ?
Ordre des sommets selon dépendances dans DAG.
Exploration en profondeur — méthode ?
Parcours récursif jusqu’au bout, puis backtracking.
Composante connexe — dans non-orienté ?
Sous-graphe maximal où tous sommets sont reliés.
Graphe fortement connexe — dans orienté ?
Tous sommets accessibles dans les deux sens.
DAG — définition ?
Graphe orienté sans cycle.
Application des graphes — exemples ?
Réseaux, planification, modélisation biologique.
Connexité — importance ?
Segmentation en sous-ensembles reliés.
Sous-graphe — définition ?
Partie du graphe initial avec certains sommets et arêtes.
Testez vos connaissances avec un QCM de 12 questions sur Introduction à la théorie des graphes.
1. Qu'est-ce qu'un graphe dans le contexte des structures mathématiques ?
2. Qui est crédité d’avoir formulé la problématique sur la traversée des ponts de Königsberg, donnant naissance à la théorie des graphes ?
Révisez le cours complet dans la fiche de révision de Introduction à la théorie des graphes.
Voir la fiche →Importe ton cours et l'IA génère des flashcards en 30 secondes.
Générateur de flashcards