Revisão

Lista de Exercícios diversos sobre TEORIA DE GRAFOS
1. Desenhe todos os grafos simples que é possível construir com 1, 2, 3, e 4 vértices.
2. Desenhe um grafo G com vértices V = { u1, u2, u3, u4, u5 } e tal que |E| é o maior possível.
3. Escreva o número de vértices, número de arestas e os graus de cada vértice dos grafos abaixo: 4. John gosta de Joan, Jean e Jane; Joe gosta de Jane e Joan; Jean e Joan gostam-se entre eles. Desenhe um grafo ilustrando essas relações entre os 5 personagens. Determine o conjunto de vértices, o conjunto de arestas, o grau de cada vértice e a seqüência de graus do grafo.
5. Cobra come sapo e pássaros; pássaros e aranhas comem insetos; sapos comem caracol, aranhas e insetos. Desenhe um grafo ilustrando esse comportamento predatório. Determine o conjunto de vértices, o conjunto de arestas, o grau de cada vértice e a seqüência de graus do grafo.
6. Calcule a seqüência de graus dos grafos abaixo. 7. Relacione os vértices isolados, terminais, ímpares e pares dos grafos do exercício 6, se existirem.
8. Desenhe dois grafos distintos, regulares de grau 3.
9. Desenhe um grafo N5
10. Desenhe dois grafos K5
11. Dê exemplo, se existir, de um grafo exibindo as seguintes propriedades: i ) todo vértice é adjacente a dois outros vértices ii ) toda aresta é adjacente a outras duas arestas
12. Dê exemplo (se existir) de:
· um grafo 0-regular que não é completo,
· um grafo 1-regular que não é completo,
· um grafo 2-regular que não é completo,
· um grafo 3-regular que não é completo.
13. Dê exemplo (se existir) de:
· um grafo sem vértices ímpares,
· um grafo sem vértices pares,
· um grafo com exatamente um vértice ímpar,
· um grafo com exatamente um vértice par,
· um grafo com exatamente dois vértices ímpares,
· um grafo com exatamente dois vértices pares.

14. Mostre que não existem grafos com vértices de grau 2, 3, 3, 4, 4 e 5.

15. Desenhe o complemento dos grafos abaixo.