Vi kan også kalle handshaking-teorien som Sum of degree-teoremet eller Handshaking Lemma. Handshaking-teorien sier at summen av graden av alle toppunktene for en graf vil være dobbelt så mange kanter som grafen inneholder. Den symbolske representasjonen av handshaking-teori er beskrevet som følger:
Her,
'd' brukes til å angi graden av toppunktet.
'v' brukes for å indikere toppunktet.
'e' brukes til å indikere kantene.
Handshaking Theorem:
Det er noen konklusjoner i handshaking-teoremet, som må trekkes, som er beskrevet som følger:
java string.format
I hvilken som helst graf:
- Det må være partall for summen av grad av alle toppunktene.
- Hvis det er oddetallsgrader for alle toppunktene, må summen av grad av disse toppunktene alltid forbli partall.
- Hvis det er noen toppunkter som har en oddetallsgrad, vil antallet av disse toppunktene være partall.
Eksempler på Handshaking-teori
Det er ulike eksempler på håndtrykkteori, og noen av eksemplene er beskrevet som følger:
Eksempel 1: Her har vi en graf som har graden av hvert toppunkt som 4 og 24 kanter. Nå skal vi finne ut antall toppunkter i denne grafen.
Løsning: Ved hjelp av grafen ovenfor har vi følgende detaljer:
Grad av hvert toppunkt = 24
Antall kanter = 24
Nå vil vi anta antall toppunkter = n
Ved hjelp av Handshaking-teoremet har vi følgende ting:
Summen av en grad av alle toppunkter = 2 * Antall kanter
Nå vil vi sette de gitte verdiene inn i håndtrykkformelen ovenfor:
n*4 = 2*24
n = 2*6
n = 12
Således, i graf G, er antall toppunkter = 12.
Eksempel 2: Her har vi en graf som har 21 kanter, 3 toppunkter av grad 4, og alle andre toppunkter av grad 2. Nå skal vi finne ut det totale antallet toppunkter i denne grafen.
Løsning: Ved hjelp av grafen ovenfor har vi følgende detaljer:
Antall grader 4 hjørner = 3
Antall kanter = 21
understreng i bash
Alle andre toppunkter har grad 2
Nå vil vi anta antall toppunkter = n
Ved hjelp av Handshaking-teoremet har vi følgende ting:
Summen av grad av alle toppunkter = 2 * Antall kanter
Nå vil vi sette de gitte verdiene inn i håndtrykkformelen ovenfor:
3*4 + (n-3) * 2 = 2*21
12+2n-6 = 42
2n = 42 - 6
2n=36
n = 18
Dermed, i graf G, er det totale antallet toppunkter = 18.
Eksempel 3: Her har vi en graf som har 35 kanter, 4 toppunkter på grad 5, 5 toppunkter på grad 4 og 4 toppunkter på grad 3. Nå skal vi finne ut antall toppunkter med grad 2 i denne grafen.
Løsning: Ved hjelp av grafen ovenfor har vi følgende detaljer:
Antall kanter = 35
: i java
Antall grader 5 hjørner = 4
Antall grader 4 hjørner = 5
Antall grader 3 toppunkter = 4
Nå vil vi anta antall grader 2 toppunkter = n
Ved hjelp av Handshaking-teoremet har vi følgende ting:
Summen av grad av alle toppunkter = 2 * Antall kanter
Nå vil vi sette de gitte verdiene inn i håndtrykkformelen ovenfor:
4*5 + 5*4 + 4*3 + n*2 = 2*35
20 + 20 + 12 + 2n = 70
52+2n = 70
filtrerende python
2n = 70-52
2n = 18
n = 9
Således, i graf G, er antall grader 2 toppunkter = 9.
Eksempel 4: Her har vi en graf som har 24 kanter, og graden av hvert toppunkt er k. Nå vil vi finne ut mulig antall toppunkter fra de gitte alternativene.
- femten
- tjue
- 8
- 10
Løsning: Ved hjelp av grafen ovenfor har vi følgende detaljer:
Antall kanter = 24
Grad av hvert toppunkt = k
Nå vil vi anta antall toppunkter = n
Ved hjelp av Handshaking-teoremet har vi følgende ting:
Summen av grad av alle toppunkter = 2 * Antall kanter
Nå vil vi sette de gitte verdiene inn i håndtrykkformelen ovenfor:
N*k = 2*24
K = 48/ca
latex liste
Det er obligatorisk at et helt tall er inneholdt av graden av ethvert toppunkt.
Så vi kan bare bruke de typene verdier av n i ligningen ovenfor som gir oss en hel verdi av k.
Nå vil vi sjekke alternativene ovenfor ved å sette dem i stedet for n en etter en slik:
- For n = 15 vil vi få k = 3,2, som ikke er et helt tall.
- For n = 20 vil vi få k = 2,4, som ikke er et helt tall.
- For n = 8 vil vi få k = 6, som er et helt tall, og det er tillatt.
- For n = 10 vil vi få k = 4,8, som ikke er et helt tall.
Dermed er det riktige alternativet alternativ C.