Flashcards: Introduction aux graphes et leurs propriétés — 18 cards

Ponts de Königsberg — circuit eulérien ?

Pas d’existence dans le problème classique.

Graphe — définition ?

Structure de sommets et arêtes reliant certains sommets.

Arête — définition ?

Liaison non ordonnée entre deux sommets.

Graphe planaire — rôle ?

Peut être dessiné sans croisements d’arêtes.

Graphe simple — caractéristiques ?

Pas de boucle ni d’arêtes multiples entre deux sommets.

Graphe connexe — propriété ?

Tout sommet accessible depuis n’importe quel autre.

Degré d’un sommet — définition ?

Nombre d’arêtes incidentes à ce sommet.

Sous-graphe induit — définition ?

Sous-ensemble de sommets avec toutes les arêtes entre eux.

Isomorphisme — rôle ?

Bijection préservant l’adjacence entre deux graphes.

Chaîne — définition ?

Suite alternant sommets et arêtes, connectant deux sommets.

Cycle — caractéristique ?

Chaîne fermée, simple, de longueur ≥ 1.

Graphe connexe — propriété ?

Existe une chaîne entre chaque paire de sommets.

Matrice d’adjacences — rôle ?

Représente les adjacences par un tableau.

Liste d’adjacences — rôle ?

Représente chaque sommet avec ses voisins.

Graphe planaire vs non planaire

Planaires : pas de croisements, non planaires : croisements possibles.

Graphe simple vs multigraphe

Simple : pas de boucle ni arêtes multiples, multigraphe : autorise.

Degré d’un graphe — définition ?

Maximum des degrés de ses sommets.

Composantes connexes — définition ?

Sous-graphes maximaux connexes.