Sous-graphe

L'ensemble des sommets du sous-graphe H {\displaystyle H} est un sous-ensemble de l'ensemble des sommets de G {\displaystyle G} et l'ensemble des arcs de H {\displaystyle H} est un sous-ensemble de l'ensemble des arcs de G {\displaystyle G} ayant leur origine et leur extrémité parmi les sommets de H {\displaystyle 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 {\displaystyle H} est un sous-graphe couvrant de G {\displaystyle G} (i.e. H {\displaystyle H} couvre G {\displaystyle G} ) si V H = V G {\displaystyle V_{H}=V_{G}} et E H ⊆ E G {\displaystyle E_{H}\subseteq E_{G}} . Ainsi tout graphe simple à n sommets est un sous-graphe couvrant du graphe complet Kn. 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 {\displaystyle H} est un sous-graphe induit de G {\displaystyle G} si, pour tout couple ( x , y ) {\displaystyle (x,y)} de sommets de H {\displaystyle H} , x {\displaystyle x} est connecté à y {\displaystyle y} dans H {\displaystyle H} si et seulement si x {\displaystyle x} est connecté à y {\displaystyle y} dans G {\displaystyle G} . Autre formulation de la condition : l'ensemble des arcs de H {\displaystyle H} est l'ensemble des arcs de G {\displaystyle G} incidents à deux sommets de H {\displaystyle H} .