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.

Definition

Låt ${\displaystyle G=(K,H)}$ vara en godtycklig graf, och låt ${\displaystyle S\in H}$. Då är den inducerad delgrafen ${\displaystyle G[S]}$ grafen vars hörnmängd med ${\displaystyle S}$ och kantmängder sådana att ${\displaystyle (H_{1},H_{2})\in S}$ och ${\displaystyle 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