Introduction à la théorie des graphes/Graphes et sous-graphes
La majorité des problèmes de théorie des graphes consiste en l'étude, l’existence ou l'optimalité de certains sous-objets contenus dans un graphe. Nous allons définir ici ces sous-objets et nous en donnerons quelques exemples.
Sous-graphe et graphe partiel
En ce qui concerne un graphe partiel de G, c’est tout à fait l'inverse. Ici on garde tous les sommets de G et on enlève quelques arêtes. Voici la définition :
On parle aussi de graphe couvrant, particulièrement quand le graphe partiel est un arbre.
Un sous-graphe partiel sera un graphe partiel d'un sous-graphe.
Graphes et sous-graphes particuliers
Stable
Notons qu'un stable est donc 0-régulier. Modèle:Exemple
Clique
Modèle:Définition Modèle:Exemple
Chaine et connexité
Dans un graphe simple, une chaîne pourra être simplement définie par une séquence de sommets.
Cycle
On dit aussi qu'un cycle est une chaîne fermée.