Inducerad delgraf

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

Vänstergraf är ${\textstyle G}$ och högergraf är ${\textstyle D}$

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

• Verfasser., Diestel, Reinhard, 1959-. Graph theory. ISBN 9783662536216. OCLC 1048203362. http://worldcat.org/oclc/1048203362. Läst 12 mars 2019