Grade interioare și exterioare la BAC: matrice și arce

Într-un graf orientat, gradul exterior numără arcele care pleacă dintr-un vârf, iar gradul interior numără arcele care sosesc în el. Dacă matricea folosește convenția „linia este plecarea, coloana este sosirea”, suma unei linii dă gradul exterior, iar suma unei coloane dă gradul interior. Această convenție rezolvă majoritatea confuziilor de la exercițiile scurte pentru BAC.

Lecția se adresează profilului matematică-informatică, inclusiv intensiv informatică, pentru capitolul grafuri orientate. Verifică programa aplicabilă sesiunii tale. Exemplele sunt originale și folosesc grafuri fără bucle și fără arce multiple; între două vârfuri pot exista ambele arce opuse.

Cum citești corect un arc?

Arcul (2,5) pleacă din vârful doi și ajunge în vârful cinci. El contribuie cu unu la gradul exterior al lui doi și cu unu la gradul interior al lui cinci. Nu contribuie la gradul interior al lui doi numai pentru că eticheta lui apare în pereche.

Arcul opus, (5,2), este alt arc. Poate exista simultan sau poate lipsi. Prin urmare, nu completezi automat matricea simetric, cum ai face pentru un graf neorientat. Ordinea extremităților face parte din informația problemei.

O verificare simplă este să formulezi fiecare pereche cu verbele „pleacă” și „ajunge”. Această traducere scurtă este utilă când enunțul folosește o diagramă cu săgeți mici, apropiate între ele. Copiază întâi arcele într-o listă și abia apoi însumează.

Schema de legătură dintre matrice și grade

Notăm matricea cu A. Elementul A[i][j] este unu dacă există arcul de la i la j și zero în caz contrar. Nu lucrăm aici cu ponderi sau cu numărul de arce paralele.

Informația cerută	Ce inspectezi	Interpretarea rezultatului
Grad exterior al lui i	Linia i	Câte arce pleacă din i
Grad interior al lui i	Coloana i	Câte arce sosesc în i
Numărul total de arce	Toată matricea	Fiecare arc apare o singură dată
Arc de la i la j	Elementul de pe linia i, coloana j	Valoarea unu confirmă arcul

Diagonala este zero deoarece am exclus buclele. O matrice simetrică este posibilă și la un graf orientat: înseamnă că fiecare arc prezent are și opusul prezent. Simetria nu transformă perechile ordonate în muchii neorientate.

Exemplu complet cu cinci vârfuri

Considerăm arcele (1,2), (1,3), (2,3), (3,1), (3,4), (5,4). Matricea este:

0 1 1 0 0
0 0 1 0 0
1 0 0 1 0
0 0 0 0 0
0 0 0 1 0

Prima linie are două valori unu, deci gradul exterior al vârfului unu este doi. Prima coloană are o singură valoare unu, corespunzătoare arcului din trei spre unu, deci gradul său interior este unu. Aplicăm aceeași citire tuturor vârfurilor.

Vârf	Grad exterior	Grad interior
1	2	1
2	1	1
3	2	2
4	0	2
5	1	0

Suma gradelor exterioare este șase, exact numărul arcelor. Și suma gradelor interioare este șase. Dacă ai aduna toate cele zece grade din tabel, ai obține doisprezece: fiecare arc contribuie o dată la fiecare tip de grad.

Ce înseamnă un grad zero?

Vârful patru nu are arce care pleacă din el, dar primește două arce. Nu este izolat. Vârful cinci nu primește arce, însă are un arc spre patru; nici el nu este izolat. Un vârf izolat are ambele grade zero.

Termenii „sursă” și „destinație finală” pot avea convenții diferite între materiale; în rezolvarea unei cerințe cu grade este mai sigur să scrii proprietatea exactă. De exemplu, „grad interior zero și grad exterior pozitiv” identifică fără ambiguitate situația vârfului cinci.

Dacă exercițiul cere vârfuri fără succesori direcți, selectezi gradul exterior zero. Dacă cere vârfuri fără predecesori direcți, selectezi gradul interior zero. Nu confunda vecinul direct cu un vârf accesibil prin mai multe arce.

Cum se schimbă gradele după modificarea grafului?

Adăugăm arcul (4,5), absent inițial. Gradul exterior al lui patru crește de la zero la unu, iar gradul interior al lui cinci crește de la zero la unu. Celelalte grade rămân neschimbate. Numărul arcelor devine șapte.

Dacă eliminăm în schimb vârful trei din graful inițial, dispar patru arce: cele două care intră și cele două care ies. Nu există buclă la trei, deci listele nu se intersectează. Rămân numai (1,2) și (5,4).

Această regulă de eliminare folosește suma celor două grade, nu numai unul dintre ele. Ea trebuie adaptată dacă un enunț permite bucle, fiindcă o buclă ar apărea în ambele numărători. Ipotezele stabilite la început justifică formula folosită aici.

De ce nu împărțim la doi suma unei singure categorii?

La grafurile neorientate, suma gradelor este dublul numărului muchiilor. La cele orientate, suma numai a gradelor exterioare este deja numărul arcelor. Împărțirea ei la doi ar înjumătăți greșit răspunsul.

În exemplul nostru, fiecare dintre cele șase arce are exact un punct de plecare. Când adunăm gradele exterioare, îl numărăm la acel punct și nicăieri altundeva. Acesta este argumentul, nu o excepție de memorat fără explicație.

Pentru a exersa înțelegerea unei reguli înaintea memorării, urmărește un singur arc în toate cele trei sume: exterioare, interioare și reunite. Vei vedea unde apare o dată și unde apare de două ori.

Patru aplicații cu răspunsuri explicate

1. În exemplul inițial, care vârf are grad interior mai mare decât gradul exterior? Răspunsul este patru: primește două arce și nu trimite niciunul. Vârful trei are grade egale, chiar dacă participă la mai multe arce.
2. Câte arce lipsesc pentru a avea toate arcele posibile între vârfuri distincte? Există cinci alegeri pentru plecare și patru pentru sosire, deci douăzeci de arce posibile. Lipsesc paisprezece din cele douăzeci.
3. Dacă inversăm toate arcele, care sunt gradele exterioare? Ele devin gradele interioare vechi: unu, unu, doi, doi, zero. Numărul total de arce rămâne șase.
4. Poate un graf cu mai mult de un vârf și un vârf de grad exterior zero să fie tare conex? Nu: din acel vârf nu poate porni un drum spre altul. Existența unor arce care intră în el nu rezolvă lipsa deplasării în sens invers.

Întrebări frecvente

Este suficientă egalitatea sumelor pentru a verifica un tabel?

Este un control necesar, dar nu suficient. Poți greși două grade în sensuri opuse și păstra suma. Verifică întâi fiecare linie și coloană, apoi totalurile; cele două controale urmăresc erori diferite.

Gradul maxim este numărul vârfurilor minus unu?

Pentru fiecare dintre cele două tipuri de grad, da, în modelul fără bucle și fără arce multiple. Suma gradului interior și exterior poate ajunge la dublul acestei valori, deoarece arcele opuse sunt distincte.

Cum continui pregătirea pentru BAC?

Alege o matrice mică din arhiva de subiecte BAC, reconstruiește lista arcelor și calculează gradele în ambele reprezentări. Dacă rezultatele diferă, marchează primul arc numărat greșit. Pentru o verificare ghidată, compară anunțurile de meditații la informatică și pregătește tabelul tău, nu doar răspunsul final.