Também podemos chamar a teoria do aperto de mão como teorema da soma dos graus ou Lema do aperto de mão. A teoria do aperto de mão afirma que a soma dos graus de todos os vértices de um gráfico será o dobro do número de arestas contidas nesse gráfico. A representação simbólica da teoria do aperto de mão é descrita a seguir:
java contém substring
Aqui,
'd' é usado para indicar o grau do vértice.
'v' é usado para indicar o vértice.
'e' é usado para indicar as bordas.
Teorema do aperto de mão:
Existem algumas conclusões no teorema do aperto de mão, que devem ser tiradas, que são descritas a seguir:
Em qualquer gráfico:
- Deve haver números pares para a soma dos graus de todos os vértices.
- Se houver graus ímpares para todos os vértices, então a soma dos graus desses vértices deve sempre permanecer par.
- Se houver alguns vértices com grau ímpar, o número desses vértices será par.
Exemplos de teoria do aperto de mão
Existem vários exemplos de teoria do aperto de mão, e alguns dos exemplos são descritos a seguir:
Exemplo 1: Aqui, temos um gráfico que tem o grau de cada vértice como 4 e 24 arestas. Agora vamos descobrir o número de vértices neste gráfico.
Solução: Com a ajuda do gráfico acima, obtivemos os seguintes detalhes:
Grau de cada vértice = 24
Número de arestas = 24
Agora vamos assumir o número de vértices = n
Com a ajuda do teorema do aperto de mão, temos o seguinte:
Soma de um grau de todos os vértices = 2 * Número de arestas
Agora colocaremos os valores fornecidos na fórmula de handshake acima:
n*4 = 2*24
n = 2*6
n = 12
Assim, no gráfico G, o número de vértices = 12.
Exemplo 2: Aqui, temos um gráfico que possui 21 arestas, 3 vértices de grau 4 e todos os outros vértices de grau 2. Agora descobriremos o número total de vértices neste gráfico.
Solução: Com a ajuda do gráfico acima, obtivemos os seguintes detalhes:
Número de vértices de grau 4 = 3
Número de arestas = 21
processamento de hackers
Todos os outros vértices têm grau 2
Agora vamos assumir o número de vértices = n
Com a ajuda do teorema do aperto de mão, temos o seguinte:
Soma do grau de todos os vértices = 2 * Número de arestas
Agora colocaremos os valores fornecidos na fórmula de handshake acima:
3*4 + (n-3) * 2 = 2*21
12+2n-6 = 42
2n = 42 - 6
2n=36
n = 18
Assim, no gráfico G, o número total de vértices = 18.
objeto para json em java
Exemplo 3: Aqui, temos um gráfico que possui 35 arestas, 4 vértices de grau 5, 5 vértices de grau 4 e 4 vértices de grau 3. Agora descobriremos o número de vértices com grau 2 neste gráfico.
Solução: Com a ajuda do gráfico acima, obtivemos os seguintes detalhes:
Número de arestas = 35
Número de vértices do grau 5 = 4
Número de vértices de grau 4 = 5
Número de vértices de grau 3 = 4
Agora vamos assumir o número de vértices de grau 2 = n
Com a ajuda do teorema do aperto de mão, temos o seguinte:
Soma do grau de todos os vértices = 2 * Número de arestas
Agora colocaremos os valores fornecidos na fórmula de handshake acima:
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
Assim, no gráfico G, número de vértices de grau 2 = 9.
Exemplo 4: Aqui, temos um gráfico que possui 24 arestas e o grau de cada vértice é k. Agora descobriremos o número possível de vértices das opções fornecidas.
- quinze
- vinte
- 8
- 10
Solução: Com a ajuda do gráfico acima, obtivemos os seguintes detalhes:
Número de arestas = 24
Grau de cada vértice = k
Agora vamos assumir o número de vértices = n
Com a ajuda do teorema do aperto de mão, temos o seguinte:
estrutura na estrutura de dados
Soma do grau de todos os vértices = 2 * Número de arestas
Agora colocaremos os valores fornecidos na fórmula de handshake acima:
N*k = 2*24
K = 48/aprox.
É obrigatório que um número inteiro esteja contido no grau de qualquer vértice.
Portanto, podemos usar apenas os tipos de valores de n na equação acima que nos fornecem um valor inteiro de k.
Agora, verificaremos as opções fornecidas acima, colocando-as no lugar de n, uma por uma, assim:
- Para n = 15, obteremos k = 3,2, que não é um número inteiro.
- Para n = 20, obteremos k = 2,4, que não é um número inteiro.
- Para n = 8, obteremos k = 6, que é um número inteiro e é permitido.
- Para n = 10, obteremos k = 4,8, que não é um número inteiro.
Assim, a opção correta é a opção C.