Subgraf și graf parțial la BAC: diferențe și numărare

Diferența dintre subgraf și graf parțial la BAC privește elementele pe care le elimini. În convenția școlară folosită în această lecție, un graf parțial păstrează toate vârfurile și elimină eventual muchii. Un subgraf se obține eliminând vârfuri împreună cu toate muchiile incidente lor, păstrând muchiile inițiale dintre vârfurile rămase.

Lecția se adresează conținuturilor de grafuri de la matematică-informatică. Precizarea convenției este importantă: în unele surse, termenul general „subgraf” are un sens mai larg, iar obiectul descris aici este numit subgraf indus. La un subiect de BAC, urmează definiția și operația cerute în programa și enunțul folosite.

Un exemplu comun pentru cele două operații

Considerăm vârfurile unu, doi, trei și patru, cu muchiile dintre unu și doi, unu și trei, doi și trei, trei și patru. Primele trei vârfuri formează un triunghi, iar al patrulea este legat numai de trei.

Graful are patru vârfuri și patru muchii. Vom aplica operațiile separat, de fiecare dată pornind de la acest graf inițial. Nu cumulăm eliminările din exemple diferite.

Element	Lista inițială
Vârfuri	1, 2, 3, 4
Muchii	12, 13, 23, 34
Grade	2, 2, 3, 1

În notația muchiilor, două etichete alăturate desemnează perechea de capete, nu un număr zecimal. Muchia dintre unu și trei este aceeași cu muchia dintre trei și unu, deoarece graful este neorientat.

Graful parțial păstrează vârfurile

Eliminăm muchia dintre unu și trei. Rămân toate cele patru vârfuri, iar muchiile sunt dintre unu și doi, doi și trei, trei și patru. Rezultatul este un graf parțial al celui inițial.

Dacă eliminăm și muchia dintre trei și patru, vârful patru rămâne în graf, dar devine izolat. Nu îl ștergem automat doar pentru că nu mai are legături. Mulțimea vârfurilor trebuie să rămână aceeași.

Putem elimina toate muchiile și obținem patru vârfuri izolate. Putem și să nu eliminăm nicio muchie, dacă definiția admite graful inițial printre grafurile sale parțiale. O cerință despre grafuri parțiale proprii poate exclude explicit această ultimă situație.

Subgraful indus păstrează toate legăturile rămase

Eliminăm vârful patru. Dispare și muchia dintre trei și patru, fiind incidentă vârfului șters. Între vârfurile unu, doi și trei rămân toate cele trei muchii ale triunghiului.

Dacă alegem să păstrăm numai vârfurile unu, trei și patru, muchiile rămase sunt dintre unu și trei și dintre trei și patru. Muchiile care aveau capătul doi dispar, fiindcă vârful doi a fost eliminat.

Nu putem păstra aceleași trei vârfuri și elimina suplimentar muchia dintre unu și trei, dacă cerința este exact subgraful indus de ele. Alegerea vârfurilor determină complet muchiile care trebuie păstrate între acestea.

Comparație directă

Operație	Vârfuri păstrate	Muchii păstrate	Clasificare în convenția lecției
Elimină muchia 13	1, 2, 3, 4	12, 23, 34	Graf parțial
Elimină vârful 4	1, 2, 3	12, 13, 23	Subgraf indus
Păstrează vârfurile 1, 4	1, 4	Niciuna	Subgraf indus
Păstrează 1, 2, 3, dar numai muchia 12	1, 2, 3	12	Nu este subgraful indus de aceste vârfuri

Ultimul rând este un subgraf în sensul general mai larg întâlnit în teoria grafurilor, dar nu rezultatul eliminării exclusiv a vârfurilor din exemplul inițial. Această distincție explică de ce trebuie să citești operația, nu doar un termen izolat.

Cum se schimbă matricea de adiacență

Pentru un graf parțial, dimensiunea matricei rămâne aceeași. Eliminarea unei muchii transformă în zero cele două valori unu simetrice care o reprezentau. Nu se elimină linii sau coloane, deoarece vârfurile rămân.

Pentru un subgraf indus, elimini liniile și coloanele vârfurilor șterse. Valorile dintre liniile și coloanele rămase se păstrează. Aceasta reflectă faptul că legăturile dintre vârfurile selectate nu sunt modificate arbitrar.

Dacă renumerotezi vârfurile pentru o implementare, păstrează corespondența cu etichetele inițiale. Un indice nou din matrice nu trebuie confundat cu vechea etichetă, mai ales când răspunsul cere numele vârfurilor.

Numărarea grafurilor parțiale

Pentru un graf cu m muchii distincte, fiecare muchie poate fi păstrată sau eliminată independent. Numărul grafurilor parțiale pe aceeași mulțime de vârfuri este doi la puterea m, dacă sunt incluse graful inițial și graful fără muchii.

În exemplul nostru, cele patru muchii produc șaisprezece grafuri parțiale. Dacă se cer numai cele obținute prin eliminarea a exact două muchii, alegi două dintre cele patru, deci sunt șase.

Etichetele vârfurilor și identitatea muchiilor sunt păstrate. Două rezultate cu același aspect geometric, dar cu muchii între etichete diferite, sunt rezultate diferite în această numărare. Nu grupăm grafurile după izomorfism.

Numărarea subgrafurilor induse

Pentru n vârfuri, fiecare submulțime de vârfuri determină exact un subgraf indus. Dacă este admisă și mulțimea vidă, numărul este doi la puterea n. Dacă se cer numai subgrafuri cu cel puțin un vârf, scazi unu.

În exemplul cu patru vârfuri, sunt șaisprezece alegeri incluzând mulțimea vidă și cincisprezece alegeri nevide. Numărul nu depinde de faptul că graful are patru muchii; depinde de numărul vârfurilor, deoarece acestea sunt alese.

Pentru subgrafuri induse cu exact trei vârfuri, alegi trei dintre cele patru, deci obții patru rezultate. Unele pot avea forme diferite și numere diferite de muchii, dar fiecare alegere de etichete este numărată o singură dată.

Conexitatea nu se păstrează automat

Un graf parțial al unui graf conex poate deveni neconex după eliminarea unor muchii. În exemplu, eliminarea muchiei dintre trei și patru izolează vârful patru, în timp ce triunghiul rămâne conex.

Nici un subgraf indus al unui graf conex nu este obligatoriu conex. Alegerea vârfurilor unu și patru produce două vârfuri izolate, deoarece între ele nu exista muchie. Lanțul care le unea în graful inițial folosea vârful trei, care nu a fost păstrat.

Proprietățile rezultatului trebuie verificate după operație. Această abordare susține învățarea prin înțelegere: identifici exact ce informație a dispărut și ce legături au rămas disponibile.

Exerciții cu răspunsuri

Elimini vârful trei din exemplu. Dispar muchiile 13, 23 și 34. Rămân vârfurile unu, doi, patru și singura muchie 12; vârful patru este izolat.

Păstrezi toate vârfurile și numai muchiile 12 și 34. Obții un graf parțial cu două componente, fiecare formată dintr-o muchie.

Un graf are șase vârfuri și cinci muchii. Are treizeci și două de grafuri parțiale și șaizeci și patru de subgrafuri induse dacă includem alegerile vide relevante. Pentru subgrafuri induse nevide, numărul este șaizeci și trei.

Un graf nu are nicio muchie. Are un singur graf parțial pe aceeași mulțime de vârfuri: el însuși. Alegerile diferite de vârfuri pot produce în continuare subgrafuri induse diferite.

Întrebări frecvente

Un vârf izolat dispare când elimin muchii?

Nu. Într-un graf parțial, vârfurile se păstrează, inclusiv cele devenite izolate. Eliminarea vârfului este o operație separată.

De ce apar două puteri diferite în formule?

La grafuri parțiale alegi muchii, deci exponentul este numărul muchiilor. La subgrafuri induse alegi vârfuri, deci exponentul este numărul vârfurilor.

Cum evit ambiguitatea termenului subgraf?

Precizează dacă păstrezi toate muchiile dintre vârfurile selectate și verifică definiția folosită în materialul de examen. Pentru discutarea unui enunț concret, poți consulta un profesor de informatică.