Rankų paspaudimo teoriją taip pat galime vadinti laipsnio sumos teorema arba rankų paspaudimo lema. Rankų paspaudimo teorija teigia, kad visų grafo viršūnių laipsnių suma bus dvigubai didesnė už tame grafe esančių briaunų skaičių. Simbolinis rankos paspaudimo teorijos vaizdavimas apibūdinamas taip:
Čia
„d“ naudojamas viršūnės laipsniui nurodyti.
„v“ naudojamas viršūnei nurodyti.
„e“ naudojamas kraštams nurodyti.
Rankos paspaudimo teorema:
Rankų paspaudimo teoremoje yra keletas išvadų, kurias reikia padaryti, ir kurios aprašomos taip:
Bet kurioje diagramoje:
- Visų viršūnių laipsnių sumai turi būti lyginiai skaičiai.
- Jei visoms viršūnėms yra nelyginiai laipsniai, tai šių viršūnių laipsnių suma visada turi likti lygi.
- Jei yra keletas viršūnių, turinčių nelyginį laipsnį, tada šių viršūnių skaičius bus lyginis.
Rankos paspaudimo teorijos pavyzdžiai
Yra įvairių rankų paspaudimo teorijos pavyzdžių, o kai kurie pavyzdžiai aprašyti taip:
1 pavyzdys: Čia turime grafiką, kurio kiekvienos viršūnės laipsnis yra 4 ir 24 briaunos. Dabar išsiaiškinsime šio grafiko viršūnių skaičių.
Sprendimas: Aukščiau pateikto grafiko pagalba gavome tokią informaciją:
eilė ir prioritetinė eilė Java
Kiekvienos viršūnės laipsnis = 24
Kraštų skaičius = 24
Dabar darysime prielaidą, kad viršūnių skaičius = n
Pasitelkę rankų paspaudimo teoremą, turime šiuos dalykus:
Visų viršūnių laipsnio suma = 2 * Kraštinių skaičius
Dabar mes įtrauksime pateiktas reikšmes į aukščiau pateiktą rankų paspaudimo formulę:
n*4 = 2*24
n = 2*6
n = 12
Taigi grafe G viršūnių skaičius = 12.
2 pavyzdys: Čia mes turime grafą, turintį 21 briauną, 3 4 laipsnio viršūnes ir visas kitas 2 laipsnio viršūnes. Dabar išsiaiškinsime bendrą šio grafiko viršūnių skaičių.
Sprendimas: Aukščiau pateikto grafiko pagalba gavome tokią informaciją:
4 laipsnio viršūnių skaičius = 3
Kraštų skaičius = 21
Visos kitos viršūnės turi 2 laipsnį
Dabar darysime prielaidą, kad viršūnių skaičius = n
Pasitelkę rankų paspaudimo teoremą, turime šiuos dalykus:
Visų viršūnių laipsnio suma = 2 * Kraštinių skaičius
Dabar mes įtrauksime pateiktas reikšmes į aukščiau pateiktą rankų paspaudimo formulę:
3*4 + (n-3) * 2 = 2*21
12+2n-6 = 42
2n = 42–6
2n = 36
n = 18
Taigi grafe G bendras viršūnių skaičius = 18.
3 pavyzdys: Čia yra grafas, turintis 35 briaunas, 4 5 laipsnio viršūnes, 5 4 laipsnio viršūnes ir 4 3 laipsnio viršūnes. Dabar išsiaiškinsime viršūnių, turinčių 2 laipsnį, skaičių šiame grafe.
Sprendimas: Aukščiau pateikto grafiko pagalba gavome tokią informaciją:
Kraštų skaičius = 35
5 laipsnio viršūnių skaičius = 4
4 laipsnio viršūnių skaičius = 5
3 laipsnio viršūnių skaičius = 4
Dabar darysime prielaidą, kad 2 laipsnio viršūnių skaičius = n
Pasitelkę rankų paspaudimo teoremą, turime šiuos dalykus:
Visų viršūnių laipsnio suma = 2 * Kraštinių skaičius
Dabar mes įtrauksime pateiktas reikšmes į aukščiau pateiktą rankų paspaudimo formulę:
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
Taigi grafe G 2 laipsnio viršūnių skaičius = 9.
4 pavyzdys: Čia turime grafiką, turintį 24 briaunas, o kiekvienos viršūnės laipsnis yra k. Dabar iš pateiktų variantų išsiaiškinsime galimą viršūnių skaičių.
- penkiolika
- dvidešimt
- 8
- 10
Sprendimas: Aukščiau pateikto grafiko pagalba gavome tokią informaciją:
Kraštų skaičius = 24
Kiekvienos viršūnės laipsnis = k
Dabar darysime prielaidą, kad viršūnių skaičius = n
Pasitelkę rankų paspaudimo teoremą, turime šiuos dalykus:
Visų viršūnių laipsnio suma = 2 * Kraštinių skaičius
Dabar mes įtrauksime pateiktas reikšmes į aukščiau pateiktą rankų paspaudimo formulę:
N*k = 2*24
K = 48 / apytiksliai
Privaloma, kad sveikasis skaičius būtų įtrauktas į bet kurios viršūnės laipsnį.
Taigi aukščiau pateiktoje lygtyje galime naudoti tik tuos n reikšmių tipus, kurie suteikia mums visą k reikšmę.
Dabar mes patikrinsime aukščiau pateiktas parinktis, įdėdami jas į n vietą po vieną taip:
- Jei n = 15, gausime k = 3,2, o tai nėra sveikas skaičius.
- Jei n = 20, gausime k = 2,4, o tai nėra sveikas skaičius.
- Jei n = 8, gausime k = 6, kuris yra sveikas skaičius, ir tai leidžiama.
- Jei n = 10, gausime k = 4,8, o tai nėra sveikas skaičius.
Taigi teisingas variantas yra C variantas.