Graful complet la BAC: grade și muchii lipsă

Un graf complet simplu neorientat are o muchie între orice două vârfuri distincte. La BAC, această definiție permite calcularea numărului de muchii, recunoașterea matricei de adiacență și aflarea numărului de muchii care lipsesc până la completare. Contează însă să folosești modelul neorientat și să nu numeri aceeași pereche de două ori.

Lecția privește grafurile de la matematică-informatică. Toate vârfurile sunt distincte, buclele sunt excluse și între două vârfuri există cel mult o muchie. După înțelegerea formulelor, verifică pe un subiect de BAC dacă se cere un graf complet, unul conex sau o componentă completă; proprietățile nu sunt identice.

De la perechi de vârfuri la muchii

Fiecare vârf poate fi unit cu celelalte n minus unu vârfuri. Dacă înmulțești n cu n minus unu, numeri fiecare muchie de două ori, câte o dată de la fiecare capăt. Împărțirea la doi elimină această dublare.

Numărul de muchii este astfel n înmulțit cu n minus unu, împărțit la doi. Pentru cinci vârfuri, obții zece muchii. Pentru șase vârfuri, obții cincisprezece.

Poți verifica și printr-o numărare succesivă: primul vârf se leagă de toate celelalte, al doilea numai de cele încă nenumerate, iar ultimul nu mai adaugă nicio pereche nouă. Suma este patru plus trei plus doi plus unu pentru cinci vârfuri.

Gradele unui graf complet

Fiecare vârf are exact n minus unu vecini, deci toate gradele sunt n minus unu. Pentru un graf simplu cu n vârfuri, dacă fiecare grad este n minus unu, graful este complet: fiecare vârf este deja legat de toate celelalte.

Un singur vârf cu grad n minus unu nu este suficient. Într-o stea cu cinci vârfuri, centrul are gradul patru, dar frunzele au gradul unu. Graful este conex, însă între două frunze nu există muchie.

Graf cu 5 vârfuri	Grade	Complet?
Toate perechile unite	4, 4, 4, 4, 4	Da
Stea	4, 1, 1, 1, 1	Nu
Ciclu cu cinci vârfuri	2, 2, 2, 2, 2	Nu

Egalitatea tuturor gradelor nu garantează singură completitudinea. Ciclul din tabel are grade egale, dar fiecare vârf are doar doi vecini, nu patru.

Matricea de adiacență

În matricea unui graf complet, diagonala principală are zerouri, iar toate celelalte elemente sunt unu. Nu există muchii de la un vârf la el însuși, dar orice două etichete diferite sunt adiacente.

Pentru trei vârfuri, liniile sunt zero, unu, unu; unu, zero, unu; unu, unu, zero. Matricea are șase valori unu și reprezintă trei muchii, fiecare prezentă simetric de două ori.

O matrice plină cu valori unu, inclusiv pe diagonală, nu reprezintă modelul simplu fără bucle folosit aici. Diagonala trebuie verificată separat de existența tuturor legăturilor dintre vârfuri distincte.

Câte muchii lipsesc până la completare

Dacă un graf simplu neorientat are n vârfuri și m muchii, numărul muchiilor lipsă este numărul perechilor posibile minus m. Adică din n înmulțit cu n minus unu, împărțit la doi, scazi numărul muchiilor existente.

Pentru șase vârfuri și opt muchii, lipsesc șapte muchii. Acestea sunt exact perechile de vârfuri distincte care nu sunt unite. Nu trebuie să adaugi vârfuri și nici să dublezi muchii deja existente.

În matrice, ai putea număra zerourile strict deasupra diagonalei principale. Fiecare astfel de zero corespunde unei muchii lipsă. Zerourile de pe diagonală nu se numără, deoarece buclele nu sunt necesare pentru completare.

Completarea pe grade

La un vârf de grad d lipsesc n minus unu minus d legături până când acesta ar avea toți vecinii posibili. Dacă aduni aceste lipsuri pentru toate vârfurile, fiecare muchie absentă apare de două ori, la cele două capete.

Prin urmare, împărțirea sumei lipsurilor la doi trebuie să dea același rezultat ca diferența dintre numărul maxim de muchii și m. Aceasta oferă un control independent când enunțul furnizează gradele unui graf deja existent.

Pentru cinci vârfuri cu gradele trei, trei, doi, doi, doi, suma gradelor este doisprezece și există șase muchii. Lipsurile față de gradul patru sunt unu, unu, doi, doi, doi; suma lor este opt, deci lipsesc patru muchii.

Eliminarea unui vârf dintr-un graf complet

Când elimini un vârf, dispar toate muchiile incidente lui. În graful complet cu n vârfuri sunt n minus unu asemenea muchii. Între celelalte vârfuri rămân toate legăturile, deci rezultatul este tot un graf complet, cu un vârf mai puțin.

Din graful complet cu șase vârfuri și cincisprezece muchii, eliminarea unui vârf șterge cinci muchii. Rămân cinci vârfuri și zece muchii. Diferența coincide cu formula pentru noul graf.

Eliminarea unei singure muchii este altă operație: păstrează toate vârfurile, dar graful nu mai este complet. Pentru cel puțin trei vârfuri, el rămâne conex, fiindcă între capetele muchiei eliminate există un traseu printr-un al treilea vârf.

Aflarea numărului de vârfuri

Dacă un graf complet are douăzeci și opt de muchii, cauți un număr natural n pentru care n înmulțit cu n minus unu este cincizeci și șase. Perechea de numere consecutive șapte și opt are acest produs, deci n este opt.

Nu orice număr de muchii corespunde unui graf complet. Douăsprezece muchii se află între cele zece ale grafului complet cu cinci vârfuri și cele cincisprezece ale celui cu șase. Nu există un număr întreg de vârfuri intermediar care să producă douăsprezece muchii.

O rezolvare prin ecuație trebuie să păstreze numai soluțiile naturale admise pentru numărul vârfurilor. O rădăcină negativă a ecuației nu are interpretare în problemă.

Câte grafuri diferite poți forma pe etichete fixe

Pe n vârfuri etichetate există câte o decizie independentă pentru fiecare pereche: muchia este prezentă sau absentă. Dacă numărul perechilor este p, numărul grafurilor simple neorientate este doi la puterea p.

Pentru trei vârfuri, există trei perechi posibile și opt grafuri. Graful complet este unul singur dintre ele, cel în care toate muchiile sunt prezente. Graful fără muchii este un altul.

Etichetele sunt importante: două desene care se obțin unul din altul prin schimbarea numelor vârfurilor pot reprezenta grafuri etichetate diferite. Numărarea până la izomorfism este o altă problemă și nu folosește automat aceeași formulă.

Exerciții cu răspunsuri

Un graf complet are șapte vârfuri. Are douăzeci și unu de muchii, iar fiecare vârf are gradul șase.

Un graf cu opt vârfuri are douăzeci de muchii. Pentru completare lipsesc opt muchii, deoarece maximul este douăzeci și opt.

Dintr-un graf complet cu șapte vârfuri elimini două vârfuri. Rămâne un graf complet cu cinci vârfuri și zece muchii. Au dispărut unsprezece muchii, nu douăsprezece: muchia dintre vârfurile eliminate nu se numără de două ori.

Toate gradele unui graf simplu cu șase vârfuri sunt cinci. Graful este complet. Dacă toate ar fi doi, concluzia nu ar mai fi valabilă.

Întrebări frecvente

Complet înseamnă același lucru cu conex?

Nu. Un graf complet nevid este conex, dar un graf conex poate avea multe muchii lipsă. Un lanț cu cel puțin trei vârfuri oferă un exemplu simplu.

De ce împart la doi la numărarea muchiilor?

Pentru că perechea formată din vârfurile a și b este aceeași muchie neorientată ca perechea b și a. Această justificare nu se transferă fără schimbări arcelor orientate.

Cum învăț formulele fără să le amestec?

Pornește de la perechi, grade și operația cerută, conform principiului de învățare prin înțelegere. Pentru verificarea unei rezolvări, poți consulta un profesor de informatică.