Questões-guia:
- Qual a diferença entre indução fraca e indução forte?
- Qual a diferença entre passeio (walk), trilha (trail) e caminho (path)? Como é o uso destes termos no Cormen?
- Todo passeio entre u e v contém um caminho de u a v. Contém também uma trilha? As trilhas de u a v sempre contém caminhos de u a v?
- O que é uma componente conexa de um grafo? Quantas componentes conexas tem um grafo conexo?
- O que é vértice de corte? E aresta de corte? Uma aresta paralela pode ser de corte?
- Um passeio fechado ímpar sempre contém um ciclo ímpar. Um passeio fechado par sempre contém um ciclo par?
- Qual a diferença entre união de grafos e decomposição de grafos?
- Que propriedades deve ter um grafo para podermos desenhá-lo (vértices e arestas) sem tirar o lápis do papel e sem repetir traços? É o mesmo que ser euleriano?
- Para um grafo qualquer, qual o número mínimo de vezes que precisamos tirar o lápis do papel para desenhá-lo, sem repetir traços? Expresse sua resposta em termos de parâmetros do grafo (número de vértices, graus, número de componentes conexas, etc.)
- Qual a diferença entre máximo e maximal? Esta diferença se aplica a números inteiros?
Exercícios:
- Exercício 1.2.1 do West.
- Exercício 1.2.2 do West.
- Diagrama JSP para construir uma trilha de Euler num grafo. Você tem duas opções aqui, uma oriunda da demostração do Teorema 1.2.26 e outra oriunda da demostração alternativa, dada no item 1.2.32, no final da página 29. Para ajudar, veja a seguir a "primeira linha" de cada um destes diagramas:
Páginas 27 e 27:
Páginas 29 e 30:
Nenhum comentário:
Postar um comentário