També podem anomenar la teoria de l'encaixada com el teorema de la suma de graus o el lema de l'enganxament de mans. La teoria del handshaking estableix que la suma de graus de tots els vèrtexs d'un gràfic serà el doble del nombre d'arestes que conté aquest gràfic. La representació simbòlica de la teoria de l'enganxament de mans es descriu de la següent manera:
Aquí,
java llegir el fitxer línia per línia
'd' s'utilitza per indicar el grau del vèrtex.
'v' s'utilitza per indicar el vèrtex.
'e' s'utilitza per indicar les vores.
Teorema de l'encaixada:
Hi ha algunes conclusions en el teorema de la connexió de mans, que cal extreure, que es descriuen de la següent manera:
En qualsevol gràfic:
- Hi ha d'haver nombres parells per a la suma de graus de tots els vèrtexs.
- Si hi ha graus senars per a tots els vèrtexs, aleshores la suma de graus d'aquests vèrtexs ha de romandre sempre parell.
- Si hi ha alguns vèrtexs que tenen un grau senar, el nombre d'aquests vèrtexs serà parell.
Exemples de teoria de l'encaixada de mans
Hi ha diversos exemples de teoria de l'enganxament de mans, i alguns dels exemples es descriuen de la següent manera:
Exemple 1: Aquí tenim un gràfic que té el grau de cada vèrtex com a 4 i 24 arestes. Ara descobrirem el nombre de vèrtexs en aquest gràfic.
Solució: Amb l'ajuda del gràfic anterior, tenim els detalls següents:
Grau de cada vèrtex = 24
Nombre d'arestes = 24
Ara assumirem el nombre de vèrtexs = n
Amb l'ajuda del teorema de Handshaking, tenim les coses següents:
Suma d'un grau de tots els vèrtexs = 2 * Nombre d'arestes
Ara posarem els valors donats a la fórmula d'enllaç anterior:
n*4 = 2*24
n = 2*6
n = 12
java ordenant una llista de matrius
Així, al gràfic G, el nombre de vèrtexs = 12.
Exemple 2: Aquí tenim un gràfic que té 21 arestes, 3 vèrtexs de grau 4 i tots els altres vèrtexs de grau 2. Ara descobrirem el nombre total de vèrtexs d'aquest gràfic.
Solució: Amb l'ajuda del gràfic anterior, tenim els detalls següents:
Nombre de vèrtexs de grau 4 = 3
Nombre d'arestes = 21
Tots els altres vèrtexs tenen el grau 2
Ara assumirem el nombre de vèrtexs = n
Amb l'ajuda del teorema de Handshaking, tenim les coses següents:
Suma de graus de tots els vèrtexs = 2 * Nombre d'arestes
Ara posarem els valors donats a la fórmula d'enllaç anterior:
3*4 + (n-3) * 2 = 2*21
12+2n-6 = 42
2n = 42 - 6
2n=36
n = 18
Així, al gràfic G, el nombre total de vèrtexs = 18.
char i int java
Exemple 3: Aquí tenim un gràfic que té 35 arestes, 4 vèrtexs de grau 5, 5 vèrtexs de grau 4 i 4 vèrtexs de grau 3. Ara descobrirem el nombre de vèrtexs de grau 2 en aquest gràfic.
Solució: Amb l'ajuda del gràfic anterior, tenim els detalls següents:
Nombre d'arestes = 35
Nombre de vèrtexs de grau 5 = 4
Nombre de vèrtexs de grau 4 = 5
Nombre de vèrtexs de grau 3 = 4
Ara assumirem el nombre de vèrtexs de grau 2 = n
Amb l'ajuda del teorema de Handshaking, tenim les coses següents:
Suma de graus de tots els vèrtexs = 2 * Nombre d'arestes
Ara posarem els valors donats a la fórmula d'enllaç anterior:
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
Així, al gràfic G, nombre de vèrtexs de grau 2 = 9.
Exemple 4: Aquí tenim un gràfic que té 24 arestes i el grau de cada vèrtex és k. Ara descobrirem el nombre possible de vèrtexs a partir de les opcions donades.
- 15
- 20
- 8
- 10
Solució: Amb l'ajuda del gràfic anterior, tenim els detalls següents:
convenció de nomenclatura de java
Nombre d'arestes = 24
Grau de cada vèrtex = k
Ara assumirem el nombre de vèrtexs = n
Amb l'ajuda del teorema de Handshaking, tenim les coses següents:
Suma de graus de tots els vèrtexs = 2 * Nombre d'arestes
Ara posarem els valors donats a la fórmula d'enllaç anterior:
N*k = 2*24
K = 48/aprox
És obligatori que un nombre sencer estigui contingut pel grau de qualsevol vèrtex.
Per tant, només podem utilitzar aquells tipus de valors de n a l'equació anterior que ens proporcionen un valor complet de k.
Ara, comprovarem les opcions anteriors posant-les al lloc de n una per una així:
- Per a n = 15, obtindrem k = 3,2, que no és un nombre sencer.
- Per a n = 20, obtindrem k = 2,4, que no és un nombre sencer.
- Per a n = 8, obtindrem k = 6, que és un nombre enter, i està permès.
- Per a n = 10, obtindrem k = 4,8, que no és un nombre sencer.
Per tant, l'opció correcta és l'opció C.