Sous-graphe

G₁, G₂ et G₃ sont des sous-graphes de G. G₁ n'est pas un sous-graphe induit car il manque l'arête 2-6. G₂ et G₃ sont des sous-graphes induits.

En théorie des graphes, un sous-graphe est un graphe contenu dans un autre graphe. Formellement, un graphe $H=(V_H,E_H)$ est un sous-graphe de $G=(V_G,E_G)$ si $V_H\subseteq V_G$ et $E_H\subseteq \{(x,y)\in E_G\mid x\in V_H\wedge y\in V_H\}$. L'ensemble des sommets du sous-graphe $H$ est un sous-ensemble de l'ensemble des sommets de $G$ et l'ensemble des arcs de $H$ est un sous-ensemble de l'ensemble des arcs de $G$ ayant leur origine et leur extrémité parmi les sommets de $H$.

Un sous-graphe couvrant ou graphe partiel est un sous-graphe ayant le même ensemble de sommets que le graphe qui le contient. Formellement, $H$ est un sous-graphe couvrant de $G$ (i.e. $H$ couvre $G$) si $V_H=V_G$ et $E_H\subseteq E_G$. Ainsi tout graphe simple à n sommets est un sous-graphe couvrant du graphe complet K_n.

Un sous-graphe induit est un sous-graphe obtenu en restreignant le graphe à un sous-ensemble de sommets et en conservant toutes les arêtes entre sommets de ce sous-ensemble. Formellement, $H$ est un sous-graphe induit de $G$ si, pour tout couple $(x,y)$ de sommets de $H$, $x$ est connecté à $y$ dans $H$ si et seulement si $x$ est connecté à $y$ dans $G$. Autre formulation de la condition : l'ensemble des arcs de $H$ est l'ensemble des arcs de $G$ incidents à deux sommets de $H$.

Voir aussi

• Théorie des graphes