De asemenea, putem numi teoria strângerii de mână Teorema Sumei gradelor sau Lema strângerii de mână. Teoria strângerii de mână afirmă că suma gradelor tuturor nodurilor pentru un graf va fi dublu față de numărul de muchii conținute de acel graf. Reprezentarea simbolică a teoriei strângerii de mână este descrisă după cum urmează:
Aici,
„d” este folosit pentru a indica gradul vârfului.
„v” este folosit pentru a indica vârful.
„e” este folosit pentru a indica marginile.
Teorema strângerii de mână:
Există câteva concluzii în teorema de strângere de mână, care trebuie trase, care sunt descrise după cum urmează:
În orice grafic:
- Trebuie să existe numere pare pentru suma gradelor tuturor vârfurilor.
- Dacă există grade impare pentru toate vârfurile, atunci suma gradelor acestor vârfuri trebuie să rămână întotdeauna pară.
- Dacă există unele vârfuri care au un grad impar, atunci numărul acestor vârfuri va fi par.
Exemple de teoria strângerii de mână
Există diverse exemple de teoria strângerii de mână, iar unele dintre exemple sunt descrise după cum urmează:
Exemplul 1: Aici, avem un grafic care are gradul fiecărui vârf ca 4 și 24 de muchii. Acum vom afla numărul de vârfuri din acest grafic.
Soluţie: Cu ajutorul graficului de mai sus, avem următoarele detalii:
Gradul fiecărui vârf = 24
Număr de muchii = 24
Acum vom presupune numărul de vârfuri = n
Cu ajutorul teoremei Handshaking, avem următoarele lucruri:
Suma unui grad al tuturor nodurilor = 2 * Numărul de muchii
Acum vom pune valorile date în formula de mai sus:
ce dimensiune are ecranul monitorului meu
n*4 = 2*24
n = 2*6
n = 12
Astfel, în graficul G, numărul de vârfuri = 12.
Exemplul 2: Aici, avem un grafic care are 21 de muchii, 3 vârfuri de gradul 4 și toate celelalte vârfuri de gradul 2. Acum vom afla numărul total de vârfuri din acest grafic.
Soluţie: Cu ajutorul graficului de mai sus, avem următoarele detalii:
Numărul de vârfuri de gradul 4 = 3
Număr de muchii = 21
Toate celelalte vârfuri au gradul 2
Acum vom presupune numărul de vârfuri = n
Cu ajutorul teoremei Handshaking, avem următoarele lucruri:
Suma gradului tuturor nodurilor = 2 * Numărul de muchii
Acum vom pune valorile date în formula de mai sus:
3*4 + (n-3) * 2 = 2*21
12+2n-6 = 42
2n = 42 - 6
2n=36
n = 18
Astfel, în graficul G, numărul total de vârfuri = 18.
Exemplul 3: Aici, avem un grafic care are 35 de muchii, 4 vârfuri de gradul 5, 5 vârfuri de gradul 4 și 4 vârfuri de gradul 3. Acum vom afla numărul de vârfuri cu gradul 2 din acest grafic.
Soluţie: Cu ajutorul graficului de mai sus, avem următoarele detalii:
Număr de muchii = 35
întreg în șir java
Numărul de vârfuri de gradul 5 = 4
Numărul de vârfuri de gradul 4 = 5
Numărul de vârfuri de gradul 3 = 4
Acum vom presupune numărul de vârfuri de gradul 2 = n
Cu ajutorul teoremei Handshaking, avem următoarele lucruri:
Suma gradului tuturor nodurilor = 2 * Numărul de muchii
Acum vom pune valorile date în formula de mai sus:
4*5 + 5*4 + 4*3 + n*2 = 2*35
20 + 20 + 12 + 2n = 70
52+2n = 70
2n = 70-52
2n = 18
n = 9
Astfel, în graficul G, numărul de vârfuri de gradul 2 = 9.
Exemplul 4: Aici, avem un grafic care are 24 de muchii, iar gradul fiecărui vârf este k. Acum vom afla numărul posibil de vârfuri din opțiunile date.
- cincisprezece
- douăzeci
- 8
- 10
Soluţie: Cu ajutorul graficului de mai sus, avem următoarele detalii:
Număr de muchii = 24
Gradul fiecărui vârf = k
Acum vom presupune numărul de vârfuri = n
Cu ajutorul teoremei Handshaking, avem următoarele lucruri:
Suma gradului tuturor nodurilor = 2 * Numărul de muchii
Acum vom pune valorile date în formula de mai sus:
N*k = 2*24
K = 48/aprox
Este obligatoriu ca un număr întreg să fie conținut de gradul oricărui vârf.
Deci putem folosi doar acele tipuri de valori ale lui n în ecuația de mai sus care ne oferă o valoare întreagă a lui k.
Acum, vom verifica opțiunile date de mai sus punându-le în locul lui n una câte una, astfel:
- Pentru n = 15, vom obține k = 3,2, care nu este un număr întreg.
- Pentru n = 20, vom obține k = 2,4, care nu este un număr întreg.
- Pentru n = 8, vom obține k = 6, care este un număr întreg și este permis.
- Pentru n = 10, vom obține k = 4,8, care nu este un număr întreg.
Astfel, opțiunea corectă este opțiunea C.