iz H ima iste krajeve u H kao što ih ima u G, onda kažemo da je H podgraf od G. Neka je G = \ left ( V, E \ right ) i E ^ \ prime \ subseteq E .
od G. Neka je G = \ left ( V, E \ right ) i E ^ \ prime \ subseteq E . Podgraf od G čiji je skup vrhova V i skup bridova E \ setminus E ^ \ prime
. Komponenta povezanosti grafa G je maksimalni povezani podgraf od G, tj. povezani podgraf koji nije sadržan ni u jednom
grafa G je maksimalni povezani podgraf od G, tj. povezani podgraf koji nije sadržan ni u jednom drugom povezanom podgrafu. Za
podgraf koji nije sadržan ni u jednom drugom povezanom podgrafu . Za broj komponenti povezanosti grafa G koristimo se
rekurzivne metode Označimo s G neki molekularni graf, a sa k podgraf koji čini Kekuléovu strukturu, tj. koji se sastoji od
poslužit ćemo se linearnim rekurzijama na grafu i njegovim podgrafovima . Od samih početaka pa sve do danas, metode za prebrojavanje
sa skupom vrhova V ( G ' ) i skupom bridova E ( G ' ). Tada je G ' podgraf grafa G ako je V ( G ' ) podskup od V ( G ) i E ( G ' ) podskup od E ( G
ako je V ( G ' ) podskup od V ( G ) i E ( G ' ) podskup od E ( G ) . Podgraf G ' je razapinjući podgraf grafa G ako ima isti skup vrhova
od V ( G ) i E ( G ' ) podskup od E ( G ). Podgraf G ' je razapinjući podgraf grafa G ako ima isti skup vrhova kao i G. Na Slici 5 vidimo graf
kao i G. Na Slici 5 vidimo graf ( na lijevoj strani ) i njegov podgraf ( na desnoj strani ). Slika 5: Graf i podgraf. 3 Šetnja i
strani ) i njegov podgraf ( na desnoj strani ). Slika 5: Graf i podgraf . 3 Šetnja i duljina u grafu Šetnja je alternirajući niz
, neusmjeren graf. Razapinjuće stablo u tom grafu je podgraf koji je stablo i razapinje taj graf. Jedan graf može imati
po jednom i vratiti se nazad u početni vrh. Povezan graf bez ( podgrafova ) ciklusa zove se stablo ( tree ). Spanning tree je takav
) ciklusa zove se stablo ( tree ). Spanning tree je takav podgraf datog grafa koji je tree i pokriva sve vrhove. Znači može se