Subgraf
Articolul prezintă subgrafuri pentru grafuri neorientate. Pentru grafuri orientate, accesați:
Subgraf - Grafuri orientate
Fie G=(X,U) un graf neorientat.
Se numește subgraf al lui G un graf G1=(X1,U1) cu proprietatea că X1 este o submulțime nevidă a lui X, iar U1 conține toate muchiile lui G care au ambele extremități în X1.
Spus altfel, un subgraf al unui graf neorientat conține doar o parte din nodurile grafului inițial, împreună cu toate muchiile nodurilor rămase.
Exemplu de graf neorientat și un subgraf al său:
Subgraful este conex.
Observând subgraful G1, vedem că mulțimea de noduri este X1={1,2,3,4}. Lipsa nodurilor 5, 6 și 7 va provoca dispariția unor muchii ce altfel nu vor avea 2 extremități.
Toate celelalte muchii ale lui G, care au extremități în X1, vor fi păstrate în subgraf.
Numărul de subgrafuri
Numărul total de subgrafuri al unui graf neorientat este 2n-1.
Formula este dedusă din faptul că fiecare nod poate fi prezent sau nu în subgraf, deci avem 2n posibilități. Dintre acestea, trebuie eliminat cazul în care nu avem niciun nod în subgraf.