Flashcards: Introduction à la théorie des graphes — 24 cards

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.