Graf parțial, orientat

Acest material se referă la grafuri orientate. Pentru grafuri neorientate vezi: Graf parțial - Grafuri neorientate.

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

Se numește graf parțial al lui $G$ un graf $G_{1}=(X_{1}, E_{1})$ , cu proprietatea că $X_{1}=X$ și $E_{1}$ este o submulțime a mulțimii $E$ .

Deducem că un graf parțial conține aceleași noduri, dar mai puține arce decât graful inițial.

Publicitate

Exemplu de graf parțial pentru un graf orientat:

$G_{1}$ este doar un exemplu dintre toate grafurile parțiale posibile pentru $G$ .

Publicitate

Numărul maxim de grafuri parțiale ale unui graf orientat cu $m$ arce este $2^{m}$ .

Pentru deducerea formulei, ne gândim că fiecare arc din graful inițial poate exista, sau nu, în graful parțial format.

de Echipa EZinfo · Actualizat: 1 februarie 2026

În articol: