Pentru a înțelege gradul interior și exterior al unui vârf, trebuie mai întâi să învățăm despre conceptul de grad al unui vârf. După aceea, putem înțelege cu ușurință gradul interior și gradul exterior al unui vârf. Ar trebui să știm că gradul de intrare și gradul de exterior poate fi determinat doar în graficul direcționat. Putem calcula gradul unui vârf cu ajutorul unui grafic nedirecționat. În graficul nedirecționat, nu putem calcula gradul de intrare și gradul exterior al unui vârf.
Gradul unui vârf
Dacă vrem să aflăm gradul fiecărui vârf dintr-un grafic, în acest caz, trebuie să numărăm numărul de relații care sunt stabilite de un anumit vârf cu celălalt vârf. Cu alte cuvinte, putem determina gradul unui vârf cu ajutorul calculului numărului de muchii care se conectează la acel vârf. Gradul unui vârf este indicat cu ajutorul deg(v). Dacă există un grafic simplu, care conține n număr de vârfuri, în acest caz, gradul oricărui vârf va fi:
Deg(v) = n-1 ∀ v ∈ G
Un vârf are capacitatea de a forma o muchie cu toate celelalte vârfuri dintr-un grafic, cu excepția lui însuși. Deci, într-un grafic simplu, gradul unui vârf se va afla după numărul de vârfuri dintr-un grafic minus 1. Aici 1 este folosit pentru vârful de sine deoarece nu face o buclă de la sine. Dacă graficul conține vârfurile care au bucla proprie, atunci acel tip de grafic nu va fi un simplu grafic.
Exemplu:
În acest exemplu, avem un grafic care are 6 vârfuri, adică a, b, c, d, e și f. Vârful „a” are gradul 5, iar toate celelalte vârfuri au gradul 1. Dacă vreun vârf are gradul 1, atunci acel tip de vârf va fi cunoscut drept „vârful de capăt”.
Există două cazuri de grafice în care putem lua în considerare gradul unui vârf, care sunt descrise după cum urmează:
- Grafic nedirecționat
- Graficul dirijat
Acum vom afla în detaliu gradul unui vârf într-un graf direcționat și gradul unui vârf într-un graf nedirecționat.
Gradul unui vârf într-un graf nedirecționat
Dacă există un grafic nedirecționat, atunci în acest tip de grafic nu va exista o muchie direcționată. Exemplele pentru a determina gradul unui vârf într-un grafic nedirecționat sunt descrise după cum urmează:
Exemplul 1: În acest exemplu, vom lua în considerare un grafic nedirecționat. Acum vom afla gradul fiecărui vârf din acel grafic.
Soluţie: În graficul nedirecționat de mai sus, există un total de 5 numere de vârfuri, adică a, b, c, d și e. Gradul fiecărui vârf este descris după cum urmează:
- Graficul de mai sus conține 2 muchii, care se întâlnesc la vârful „a”. Prin urmare, Deg(a) = 2
- Acest grafic conține 3 muchii, care se întâlnesc la vârful „b”. Prin urmare, Deg(b) = 3
- Graficul de mai sus conține o muchie, care se întâlnește la vârful „c”. Prin urmare, Deg(c) = 1. Vârful c este cunoscut și sub denumirea de vârf suspendat.
- Graficul de mai sus conține 2 muchii, care se întâlnesc la vârful „d”. Prin urmare, Deg(d) = 2.
- Graficul de mai sus conține 0 muchii, care se întâlnesc la vârful „e”. Prin urmare, Deg(a) = 0. Vârful e poate fi numit și vârf izolat.
Exemplul 2: În acest exemplu, vom lua în considerare un grafic nedirecționat. Acum vom afla gradul fiecărui vârf din acel grafic.
Soluţie: În graficul nedirecționat de mai sus, există un total de 5 numere de vârfuri, adică a, b, c, d și e. Gradul fiecărui vârf este descris după cum urmează:
Gradul vârfului a = deg(a) = 2
Gradul vârfului b = deg(b) = 2
Gradul vârfului c = deg(c) = 2
Gradul vârfului d = deg(d) = 2
Gradul vârfului e = deg(e) = 0
În acest grafic, nu există un vârf suspendat, iar vârful „e” este un vârf izolat.
Gradul de vârf în graficul direcționat
Dacă graficul este un grafic direcționat, atunci în acest grafic, fiecare vârf trebuie să aibă un grad în interior și un grad în exterior. Să presupunem că există un grafic direcționat. În acest grafic, putem folosi următorii pași pentru a afla gradul interior, gradul exterior și gradul unui vârf.
În gradul unui vârf
Gradul în interior al unui vârf poate fi descris ca un număr de muchii cu v, unde v este folosit pentru a indica vârful terminal. Cu alte cuvinte, îl putem descrie ca un număr de muchii care ajung la vârf. Cu ajutorul sintaxei deg-(v), putem scrie gradul in al unui vârf. Dacă vrem să determinăm gradul în interior al unui vârf, pentru aceasta, trebuie să numărăm numărul de muchii care se termină la vârf.
Gradul în afara unui vârf
Gradul de exterior al unui vârf poate fi descris ca un număr de muchii cu v, unde v este folosit pentru a indica vârful inițial. Cu alte cuvinte, îl putem descrie ca un număr de muchii care ies din vârf. Cu ajutorul sintaxei deg+(v), putem scrie gradul de exterior al unui vârf. Dacă vrem să determinăm gradul de exterior al unui vârf, pentru aceasta, trebuie să numărăm numărul de muchii care pornesc de la vârf.
Gradul unui vârf
Gradul unui vârf este indicat cu ajutorul gradului (v), care este egal cu adăugarea gradului în interior al unui vârf și a gradului în exterior al unui vârf. Reprezentarea simbolică a gradului unui vârf este descrisă după cum urmează:
Deg(v) = deg-(v) + deg+(v)
Exemplul 1: În acest exemplu, avem un grafic și trebuie să determinăm gradul fiecărui vârf.
Soluţie: Pentru aceasta, vom afla mai întâi gradul unui vârf, gradul în interior al unui vârf și apoi gradul în exterior al unui vârf.
După cum putem vedea că graficul de mai sus conține totalul de 6 vârfuri, adică v1, v2, v3, v4, v5 și v6.
În grad:
În gradul unui vârf v1 = deg(v1) = 1
În gradul unui vârf v2 = deg(v2) = 1
În gradul unui vârf v3 = deg(v3) = 1
În gradul unui vârf v4 = deg(v4) = 5
În gradul unui vârf v5 = deg(v5) = 1
În gradul unui vârf v6 = deg(v6) = 0
În afara gradului:
Gradul în afara unui vârf v1 = deg(v1) = 2
Gradul în afara unui vârf v2 = deg(v2) = 3
Gradul în afara unui vârf v3 = deg(v3) = 2
Gradul în afara unui vârf v4 = deg(v4) = 0
Gradul în afara unui vârf v5 = deg(v5) = 2
Gradul în afara unui vârf v6 = deg(v6) = 0
Gradul unui vârf
Cu ajutorul definiției descrise mai sus, știm că gradul unui vârf Deg(v) = deg-(v) + tu+(v). Acum îl vom calcula cu ajutorul acestei formule astfel:
Gradul unui vârf v1 = deg(v1) = 1+2 = 3
Gradul unui vârf v2 = deg(v2) = 1+3 = 4
Gradul unui vârf v3 = deg(v3) = 1+2 = 3
Gradul unui vârf v4 = deg(v4) = 5+0 = 5
Gradul unui vârf v5 = deg(v5) = 1+2 = 3
Gradul unui vârf v6 = deg(v6) = 0+0 = 0
Exemplul 2:
În acest exemplu, avem un grafic direcționat cu 7 vârfuri. Vârful „a” conține 2 muchii, adică „ad” și „ab”, care merg spre exterior. Prin urmare, vârful 'a' conţine gradul de ieşire, care este 2. În mod similar, vârful 'a' are şi o muchie 'ga', care se îndreaptă spre acest vârf 'a'. Prin urmare, vârful „a” conține gradul în, care este 1.
Soluţie: Gradul în și în exterior al tuturor vârfurilor de mai sus sunt descrise după cum urmează:
În grad:
În gradul unui vârf a = deg(a) = 1
În gradul unui vârf b = deg(b) = 2
În gradul unui vârf c = deg(c) = 2
În gradul unui vârf d = deg(d) = 1
În gradul unui vârf e = deg(e) = 1
În gradul unui vârf f = deg(f) = 1
În gradul unui vârf g = deg(g) = 0
În afara gradului:
Gradul în afara unui vârf a = deg(a) = 2
Gradul în afara unui vârf b = deg(b) = 0
Gradul în afara unui vârf c = deg(c) = 1
Gradul în afara unui vârf d = deg(d) = 1
Gradul în afara unui vârf e = deg(e) = 1
Gradul în afara unui vârf f = deg(f) = 1
Gradul în afara unui vârf g = deg(g) = 2
Gradul fiecărui vârf:
Știm că gradul unui vârf Deg(v) = deg-(v) + tu+(v). Acum îl vom calcula cu ajutorul acestei formule astfel:
Gradul unui vârf a = deg(a) = 1+2 = 3
Gradul unui vârf b = deg(b) = 2+0 = 2
Gradul unui vârf c = deg(c) = 2+1 = 3
Gradul unui vârf d = deg(d) = 1+1 = 2
Gradul unui vârf e = deg(e) = 1+1 = 2
Gradul unui vârf f = deg(f) = 1+1 = 2
tuplu java
Gradul unui vârf g = deg(g) = 0+2 = 2
Exemplul 3: În acest exemplu, avem un grafic direcționat cu 5 vârfuri. Vârful „a” conține 1 muchie, adică „ae”, care se îndreaptă spre exterior. Prin urmare, vârful „a” conține un grad în afara, care este 1. În mod similar, vârful „a” are și o muchie „ba”, care se îndreaptă spre acest vârf „a”. Prin urmare, vârful „a” conține gradul în, care este 1.
Soluţie: Gradul în și în afara tuturor vârfurilor de mai sus sunt descrise după cum urmează:
În grad
În gradul unui vârf a = deg(a) = 1
În gradul unui vârf b = deg(b) = 0
În gradul unui vârf c = deg(c) = 2
În gradul unui vârf d = deg(d) = 1
În gradul unui vârf e = deg(e) = 1
În afara gradului:
Gradul în afara unui vârf a = deg(a) = 1
Gradul în afara unui vârf b = deg(b) = 2
Gradul în afara unui vârf c = deg(c) = 0
Gradul în afara unui vârf d = deg(d) = 1
Gradul în afara unui vârf e = deg(e) = 1
Gradul fiecărui vârf:
Știm că gradul unui vârf Deg(v) = deg-(v) + tu+(v). Acum îl vom calcula cu ajutorul acestei formule astfel:
Gradul unui vârf a = deg(a) = 1+1 = 2
Gradul unui vârf b = deg(b) = 0+2 = 2
Gradul unui vârf c = deg(c) = 2+0 = 2
Gradul unui vârf d = deg(d) = 1+1 = 2
Gradul unui vârf e = deg(e) = 1+1 = 2
Exemplul 4: În acest exemplu, avem un grafic și trebuie să determinăm gradul, gradul în interior și gradul exterior al fiecărui vârf.
Soluţie: Pentru aceasta, vom afla mai întâi gradul de intrare al unui vârf și apoi gradul de exterior al unui vârf.
După cum putem vedea că graficul de mai sus conține totalul de 8 vârfuri, adică 0, 1, 2, 3, 4, 5 și 6.
În grad:
În gradul unui vârf 0 = deg(0) = 1
În gradul unui vârf 1 = deg(1) = 2
În gradul unui vârf 2 = deg(2) = 2
În gradul unui vârf 3 = deg(3) = 2
În gradul unui vârf 4 = deg(4) = 2
În gradul unui vârf 5 = deg(5) = 2
În gradul unui vârf 6 = deg(6) = 2
În afara gradului:
Gradul în afara unui vârf 0 = deg(0) = 2
Gradul în afara unui vârf 1 = deg(1) = 1
Gradul în afara unui vârf 2 = deg(2) = 3
Gradul în afara unui vârf 3 = deg(3) = 2
Gradul în afara unui vârf 4 = deg(4) = 2
Gradul în afara unui vârf 5 = deg(5) = 2
Gradul în afara unui vârf 6 = deg(6) = 1
Gradul fiecărui vârf:
Știm că gradul unui vârf Deg(v) = deg-(v) + tu+(v). Acum îl vom calcula cu ajutorul acestei formule astfel:
Gradul unui vârf 0 = deg(0) = 1+2 = 3
Gradul unui vârf 1 = deg(1) = 2+1 = 3
Gradul unui vârf 2 = deg(2) = 2+3 = 5
Gradul unui vârf 3 = deg(3) = 2+2 = 4
Gradul unui vârf 4 = deg(4) = 2+2 = 4
Gradul unui vârf 5 = deg(5) = 2+2 = 4
Gradul unui vârf 6 = deg(5) = 2+1 = 3
Secvența de grade a unui grafic
Pentru a determina succesiunea de grade a unui grafic, trebuie mai întâi să determinăm gradul fiecărui vârf dintr-un grafic. După aceea, vom scrie aceste grade în ordine crescătoare. Această ordine/secvență poate fi numită șirul de grade a unui grafic.
De exemplu: În acest exemplu, avem trei grafice care au 3, 4 și 5 vârfuri, iar secvența de grade a tuturor graficelor este 3.
În graficul de mai sus, există 3 vârfuri. Gradul unei secvențe a acestui grafic este descris după cum urmează:
În graficul de mai sus, există 4 vârfuri. Secvența de grade a acestui grafic este descrisă după cum urmează:
În graficul de mai sus, există 5 vârfuri. Secvența de grade a acestui grafic este descrisă după cum urmează: