Possiamo anche chiamare la teoria dell'handshaking come teorema della somma dei gradi o lemma dell'handshaking. La teoria dell'handshaking afferma che la somma dei gradi di tutti i vertici di un grafico sarà il doppio del numero di archi contenuti in quel grafico. La rappresentazione simbolica della teoria dell'handshaking è descritta come segue:
Qui,
'd' viene utilizzato per indicare il grado del vertice.
'v' viene utilizzato per indicare il vertice.
'e' viene utilizzato per indicare i bordi.
Teorema dell'handshake:
Ci sono alcune conclusioni da trarre dal teorema dell'handshaking, descritte come segue:
In qualsiasi grafico:
- Devono esserci numeri pari per la somma dei gradi di tutti i vertici.
- Se ci sono gradi dispari per tutti i vertici, la somma dei gradi di questi vertici deve sempre rimanere pari.
- Se ci sono alcuni vertici che hanno un grado dispari, allora il numero di questi vertici sarà pari.
Esempi di teoria dell'Handshaking
Esistono vari esempi di teoria dell'handshaking e alcuni degli esempi sono descritti come segue:
Esempio 1: Qui abbiamo un grafico che ha il grado di ciascun vertice come 4 e 24 spigoli. Ora scopriremo il numero di vertici in questo grafico.
Soluzione: Con l'aiuto del grafico sopra, abbiamo ottenuto i seguenti dettagli:
Grado di ciascun vertice = 24
Numero di bordi = 24
Ora assumeremo il numero di vertici = n
numero primo in Java
Con l'aiuto del teorema dell'handshaking, abbiamo le seguenti cose:
Somma di un grado di tutti i vertici = 2 * Numero di bordi
Ora inseriremo i valori indicati nella formula di handshake sopra:
n*4 = 2*24
n = 2*6
n = 12
Pertanto, nel grafo G, il numero di vertici = 12.
Esempio 2: Qui abbiamo un grafico che ha 21 spigoli, 3 vertici di grado 4 e tutti gli altri vertici di grado 2. Ora scopriremo il numero totale di vertici in questo grafico.
Soluzione: Con l'aiuto del grafico sopra, abbiamo ottenuto i seguenti dettagli:
Numero di vertici di grado 4 = 3
Numero di bordi = 21
Tutti gli altri vertici hanno grado 2
Ora assumeremo il numero di vertici = n
stringa intera
Con l'aiuto del teorema dell'handshaking, abbiamo le seguenti cose:
Somma dei gradi di tutti i vertici = 2 * Numero di bordi
Ora inseriremo i valori indicati nella formula di handshake sopra:
3*4 + (n-3) * 2 = 2*21
12+2n-6 = 42
2n = 42 - 6
2n=36
n = 18
Pertanto, nel grafo G, il numero totale di vertici = 18.
Esempio 3: Qui abbiamo un grafico che ha 35 spigoli, 4 vertici di grado 5, 5 vertici di grado 4 e 4 vertici di grado 3. Ora scopriremo il numero di vertici di grado 2 in questo grafico.
Soluzione: Con l'aiuto del grafico sopra, abbiamo ottenuto i seguenti dettagli:
Numero di bordi = 35
Java legge il file CSV
Numero di vertici di grado 5 = 4
Numero di vertici di grado 4 = 5
Numero di vertici di grado 3 = 4
Ora assumeremo il numero di vertici di grado 2 = n
Con l'aiuto del teorema dell'handshaking, abbiamo le seguenti cose:
Somma dei gradi di tutti i vertici = 2 * Numero di bordi
Ora inseriremo i valori indicati nella formula di handshake sopra:
4*5 + 5*4 + 4*3 + n*2 = 2*35
ordina un array in Java
20+20+12+2n = 70
52+2n = 70
2n = 70-52
2n = 18
n = 9
Pertanto, nel grafo G, numero di vertici di grado 2 = 9.
Esempio 4: Qui abbiamo un grafico che ha 24 archi e il grado di ciascun vertice è k. Ora scopriremo il possibile numero di vertici dalle opzioni fornite.
- quindici
- venti
- 8
- 10
Soluzione: Con l'aiuto del grafico sopra, abbiamo ottenuto i seguenti dettagli:
Numero di bordi = 24
Grado di ciascun vertice = k
Linux modificare un file
Ora assumeremo il numero di vertici = n
Con l'aiuto del teorema dell'handshaking, abbiamo le seguenti cose:
Somma dei gradi di tutti i vertici = 2 * Numero di bordi
Ora inseriremo i valori indicati nella formula di handshake sopra:
N*k = 2*24
K = 48/ca
È obbligatorio che un numero intero sia contenuto nel grado di qualsiasi vertice.
Quindi possiamo usare solo quei tipi di valori di n nell'equazione precedente che ci forniscono un valore intero di k.
Ora controlleremo le opzioni sopra indicate inserendole al posto di n una per una in questo modo:
- Per n = 15 otterremo k = 3,2, che non è un numero intero.
- Per n = 20 otterremo k = 2,4, che non è un numero intero.
- Per n = 8 otterremo k = 6, che è un numero intero ed è consentito.
- Per n = 10 otterremo k = 4,8, che non è un numero intero.
Pertanto, l’opzione corretta è l’opzione C.