Graf parțial
Acest material se referă la grafuri neorientate. Pentru grafuri orientate vezi: Graf parțial - Grafuri orientate.
Fie un graf neorientat.
Se numește graf parțial al lui un graf , format din aceeași mulțime de noduri și o submulțime a muchiilor lui .
Cu alte cuvinte, graful parțial are aceleași noduri ca graful inițial, având doar mai puține muchii.
Publicitate
Un exemplu de graf parțial pentru un graf neorientat:
Graful parțial obținut nu mai este un graf conex.
Publicitate
Numărul de grafuri parțiale
Numărul de grafuri parțiale total posibile pentru un graf neorientat este .
Intuiția apare din faptul că fiecare muchie poate fi prezentă sau nu în graful parțial. Formula include atât graful nul, cât și graful inițial.