calculo de engenharia dg

Prévia do material em texto

- **Problema:** Determine se o grafo \( G \) é planar: \( G = (V, E) \), onde \( V = \{1, 2, 3, 
4, 5\} \) e \( E = \{\{1, 2\}, \{1, 3\}, \{1, 4\}, \{2, 3\}, \{2, 4\}, \{3, 5\}, \{4, 5\}\} \). 
 - **Resposta:** O grafo é planar. 
 
68. **Teorema de Ramsey:** 
 - **Problema:** Mostre que \( R(3, 3) = 6 \), ou seja, em qualquer coloração dos arestas 
de um grafo completo de 6 vértices com 2 cores, pelo menos um triângulo é 
monocromático. 
 - **Resposta:** Use o princípio da casa dos pombos para mostrar que em qualquer 
coloração dos 6 vértices com 2 cores, há um triângulo monocromático. 
 
69. **Combinatória (Binômio de Newton):** 
 - **Problema:** Qual é o coeficiente binomial \( \binom{20}{5} \)? 
 - **Resposta:** \( \binom{20}{5} = \frac{20 \times 19 \times 18 \times 17 \times 16}{5 
\times 4 \times 3 \times 2 \times 1} \). 
 
70. **Teorema de Pigeonhole:** 
 - **Problema:** Em um grupo de 13 pessoas, pelo menos quantas delas têm a mesma 
idade em meses (considerando que um ano tem 12 meses)? 
 - **Resposta:** Pelo menos 2 pessoas têm a mesma idade em meses, pois há mais 
pessoas do que meses. 
 
71. **Teoria dos Grafos (Árvores):** 
 - **Problema:** Quantas árvores distintas podem ser formadas com 6 vértices? 
 - **Resposta:** Existem \( 6^{6-2} = 6^4 = 1296 \) árvores distintas. 
 
72. **Recorrências (Não Homogêneas):** 
 - **Problema:** Resolva a recorrência \( a 
 
_n = 3a_{n-1} - 2a_{n-2} \) com \( a_0 = 1 \) e \( a_1 = 2 \). 
 - **Resposta:** A solução é \( a_n = \frac{2^{n+1} - (-1)^n}{3} \). 
 
73. **Teoria dos Grafos (Conectividade):** 
 - **Problema:** Qual é o número mínimo de arestas em um grafo conectado com 7 
vértices? 
 - **Resposta:** O número mínimo de arestas é 6. 
 
74. **Teoria dos Números (Teorema Fundamental da Aritmética):** 
 - **Problema:** Mostre que todo número natural maior que 1 é um produto de números 
primos. 
 - **Resposta:** Use o teorema fundamental da aritmética para mostrar a 
decomposição do número em fatores primos. 
 
75. **Geometria Discreta (Poliedros):** 
 - **Problema:** Quantos vértices, arestas e faces tem um cubo? 
 - **Resposta:** Um cubo tem 8 vértices, 12 arestas e 6 faces. 
 
76. **Teoria dos Grafos (Emparelhamento Máximo):** 
 - **Problema:** Em um grafo bipartido \( G = (U, V, E) \), qual é o tamanho do 
emparelhamento máximo? 
 - **Resposta:** O tamanho do emparelhamento máximo é igual ao número máximo de 
vértices em um caminho alternante de \( U \) para \( V \). 
 
77. **Teoria dos Grafos (Ciclos Hamiltonianos):** 
 - **Problema:** Dado um grafo não direcionado \( G \), como podemos determinar se \( 
G \) contém um ciclo hamiltoniano? 
 - **Resposta:** Verifique se há um ciclo que passe por todos os vértices do grafo 
exatamente uma vez. 
 
78. **Teoria dos Grafos (Coloração):** 
 - **Problema:** Qual é o número cromático do grafo completo \( K_6 \)? 
 - **Resposta:** \( \chi(K_6) = 6 \). 
 
79. **Teorema de Menger:** 
 - **Problema:** No grafo \( G \), qual é o número mínimo de vértices cuja remoção 
desconectaria um par específico de vértices \( s \) e \( t \)?