Podgraf

Podgraf, pojam iz teorije grafova.

Graf je u gruboj definiciji skup objekata: vrhova, točaka ili čvorova koje povezuju bridovi odnosno crte (linije). Brid spaja dva čvora i to je odnos koji definira graf. Ako vrhove povezuje brid, grafove se prikazuje crtanjem točaka za svaki vrh i povlačenjem luka između dvaju vrhova.^[1]

Da bi graf G', koji ima skup vrhova V(G') i skup bridova E(G') bio podgraf grafa G,^[1]

grafa G koji ima skup vrhova V(G) i skupom bridova E(G),^[1]

ako je V(G') podskup od V(G) i E(G′) podskup od E(G).^[1]

Ako podgraf G' ima isti skup vrhova kao i graf G',

tad je G' je razapinjući podgraf grafa G. ^[1]

Vidi

Inducirani podgraf

Izvori

↑ ^1,0 ^1,1 ^1,2 ^1,3 ^1,4 math.e, hrvatski matematički elektronički časopis Maja Fošner i Tomaž Kramberger: Teorija grafova i logistika br. 14, ISSN ISSN 1334-6083 (pristupljeno 23. prosinca 2019.)

subgraph

[E-math-1] 1,0 ^1,1 ^1,2 ^1,3 ^1,4 math.e, hrvatski matematički elektronički časopis Maja Fošner i Tomaž Kramberger: Teorija grafova i logistika br. 14, ISSN ISSN 1334-6083 (pristupljeno 23. prosinca 2019.)

[1]