Teoria dos Grafos
1ª Lista - Período 2005.1
1. Considere o conjunto de grafos abaixo:
a. Que pares de grafos são isomórficos? Explicite o isomorfismo entre os pares
de grafos.
b. Que grafos são bipartidos? Justifique a sua resposta.
2. Desenhe todos os grafos simples não isomórficos de 3 vértices. Indique a seqüência
de vértices em cada um deles.
3. Qual é o maior número possível de vértices em um grafo com 19 arestas e todos os
vértices com grau pelo menos 3? Explique a sua resposta.
4. 23 é o maior número possível de vértices em um grafo com 35 arestas, em que cada
vértice tem pelo menos grau 3? Justifique a sua resposta.
5. Desenhe um grafo com 5 vértices (v1, v2, v3, v4, v5), em que grau(v1) = 3, v2 é um
vértice ímpar, grau(v3) = 2, e v4 e v5 são adjacentes.
6. Provar que o número de vértices de grau ímpar é par.
7. É possível ter um grafo com seqüência de graus 5, 4, 4, 3, 2, 1.
8. Nos encontros sociais, a forma mais tradicional de cumprimento é o aperto de mão.
Provar que o total de apertos de mão em qualquer ocasião deve ser par.
9. No problema anterior, prove também que o número de pessoas que cumprimenta
um número ímpar de pessoas é par.
10. A propriedade de isomorfismo de grafos é simétrica? Reflexiva? Transitiva?
11. O que são grafos bipartidos?
12. Mostre problemas reais que podem ser modelados usando grafos bipartidos.
13. Subgrafos de um grafo bipartido é bipartido?
14. Qual o número de arestas de um grafo completo com 6 vértices?
15. Determine o complemento de um K6.