Sous-graphe

En théorie des graphes, un sous-graphe est un graphe contenu dans un autre graphe. Formellement, un graphe ${\displaystyle H=(V_{H},E_{H})}$ est un sous-graphe de ${\displaystyle G=(V_{G},E_{G})}$ si ${\displaystyle V_{H}\subseteq V_{G}}$ et ${\displaystyle 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 ${\displaystyle H}$ est un sous-ensemble de l'ensemble des sommets de ${\displaystyle G}$ et l'ensemble des arcs de ${\displaystyle H}$ est un sous-ensemble de l'ensemble des arcs de ${\displaystyle G}$ ayant leur origine et leur extrémité parmi les sommets de ${\displaystyle H}$.

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.

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, ${\displaystyle H}$ est un sous-graphe couvrant de ${\displaystyle G}$ (i.e. ${\displaystyle H}$ couvre ${\displaystyle G}$) si ${\displaystyle V_{H}=V_{G}}$ et ${\displaystyle 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, ${\displaystyle H}$ est un sous-graphe induit de ${\displaystyle G}$ si, pour tout couple ${\displaystyle (x,y)}$ de sommets de ${\displaystyle H}$, ${\displaystyle x}$ est connecté à ${\displaystyle y}$ dans ${\displaystyle H}$ si et seulement si ${\displaystyle x}$ est connecté à ${\displaystyle y}$ dans ${\displaystyle G}$. Autre formulation de la condition : l'ensemble des arcs de ${\displaystyle H}$ est l'ensemble des arcs de ${\displaystyle G}$ incidents à deux sommets de ${\displaystyle H}$.

Voir aussi

• Théorie des graphes

• Portail de l'informatique théorique