Graf parţial şi subgraf, lanţ şi ciclu, componente conexe. Aplicatii
Notiunile de graf partial si subgraf
Definitie: Fie G=(X,U). Un graf partial al lui G, este un graf G1=(X,V). Un graf partial G1 este chiar G, sau se obtine din G pastrând toate vârfurile si suprimând niste muchii.
Exemplu:
Pentru graful G=(X,U) de mai jos, construim alaturat graful partial obtinut prin eliminarea muchiilor ce trec prin vârful 4. Acesta este G1=(X,V) (s-au eliminat muchiile u3 si u4 care trec prin nodul 4).
Definitie: Fie graful G=(X,U). Un subgraf al lui G, este un graf G1=(Y,T), unde V va contine numai muchiile care au ambele extremitati în Y. Altfel spus, un subgraf G1 se obtine din G eliminând niste vârfuri si pastrând doar acele muchii care au ambele extremitati în multimea vârfurilor ramase.
Exemplu:
Pentru graful G=(X,U) din figura , construim subgraful obtinut prin eliminarea vârfurilor 1 si 6 . Acesta este G1=(Y,T). (s-au eliminat nodurile 1 si 6, precum si muchiile u1 si u5 care trec prin aceste noduri).
Exemplu:
Pentru graful G=(X,U) din figura , construim subgraful obtinut prin eliminarea vârfurilor 1 si 6 . Acesta este G1=(Y,T). (s-au eliminat nodurile 1 si 6, precum si muchiile u1 si u5 care trec prin aceste noduri).