Subgraf orientat

Acest material se referă la grafuri orientate. Pentru grafuri neorientate vezi: Subgraf - Grafuri neorientate.

Fie G=(X,E)G=(X,E) un graf orientat.

Se numește subgraf al lui GG un graf G1=(X1,E1)G_{1}=(X_{1}, E_{1}), cu proprietatea X1X_{1} este o submulțime a lui XX și E1=EE_{1}=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).

Publicitate

Un exemplu de graf orientat și un subgraf al său:

Subgraf graf orientat

G1G_{1} este doar unul din subgrafurile posibile pentru GG. După ce am eliminat nodurile {3,6,9}\{3,6,9\}, au rămas doar acele arce care nu aveau ca extremitate unul din nodurile acestea.

Publicitate

Numărul maxim de subgrafuri

Pentru un graf orientat cu nn noduri se pot forma un maxim de 2n−12^{n}-1 subgrafuri.

Totalul de cazuri apare din posibilitatea de a păstra, sau nu, fiecare din nodurile grafului; prin urmare 2n2^{n} cazuri. Din acestea, scădem cazul în care nu păstrăm niciun nod (caz invalid deoarece un graf are mulțimea nodurilor nevidă).

de Echipa EZinfo · Actualizat:

Ai găsit o greșeală? Raportează
Publicitate

În articol: