Inducerad delgraf

Vänstergraf är $G$ och högergraf är $D$

Inom grafteorin är en inducerad delgraf $D$ en graf som består av en delmängd av en graf $G$:s hörnmängd med tillhörande kantmängd.

Definition

Låt $G=(K,H)$ vara en godtycklig graf, och låt $S\in H$. Då är den inducerad delgrafen $G[S]$ grafen vars hörnmängd med $S$ och kantmängder sådana att $(H_1,H_2)\in S$ och $H_1,H_2\in H$.

Referenser

• Mall:Bokref