Subgraf
Articolul prezintă subgrafuri pentru grafuri orientate. Pentru grafuri neorientate, accesați:
Subgraf - Grafuri neorientate
Fie G=(X,E) un graf orientat.
Se numește subgraf al lui G un graf G1=(X1,E1), cu proprietatea X1 este o submulțime a lui X și E1=E.
Astfel, subgraful conține mai puține noduri decât graful inițial, păstrând toate arcele care există între nodurile rămase (care au ambele extremități în submulțimea aleasă de noduri).
Un exemplu de graf orientat și un subgraf al său:
Exemplul arată unul din subgrafurile posibile pentru graful G.
În exemplu, dacă eliminăm nodurile divizibile cu 3, ne rămâne mulțimea de noduri X1={1,2,4,5,7,8,10}.
Odată cu dispariția nodurilor 3, 6 și 9, dispar și arcele care au extremitățile în aceste noduri.
Numărul maxim de subgrafuri ale unui graf orientat cu n noduri este 2n-1.