Exercícios grafos

Prévia do material em texto

CENTRO UNIVERSITÁRIO DE JOÃO PESSOA 
PRÓ-REITORIA DE ENSINO DE GRADUAÇÃO – PR-EG 
CURSO: REDES DE COMPUTADORES 
 LISTA DE EXERCÍCIOS: TERORIA DOS GRAFOS 
PROFESSOR SALATIEL DIAS 
 
 
1. Construir uma representação geométrica do grafo G = (V,E), onde: 
V = {1,2,3,4,5,6} 
E = {(1,3), (1,4), (1,5), (2,3),(2,4),(2,5),(3,5),(4,5)} 
 
 
2. Represente o grafo da questão anterior através de suas matrizes de adjacência e de incidência. 
 
 
3. Identifique se os grafos a seguir são isomorfos: 
 
 a) 
 b) 
 
 c) 
 
 
 
 
 
 
 
 
 
 
4. Sobre o problema das pontes de Königsberg: 
 
 
a) ele tem solução? 
b) Qual o teorema que se reporta a esse problema? 
c) O que teria de ser alterado no cenário de Königsberg para resolver esse problema. Apresente sugestões. 
 
5. Seja I a matriz de Incidência e seja A a matriz de Adjacência de um grafo G. 
 
a) Mostre que a soma de toda coluna de I é 2 
b) O que representa a soma de todas as colunas de A? 
c) As matrizes I e A caracterizam univocamente um grafo? 
 
 
6. Prove o seguinte teorema: 
 
 grau (v) = 2 n, onde n = número de arestas, vV 
 
 
7. Prove o seguinte corolário 
 
Em qualquer grafo, o número de vértices de grau ímpar é sempre par. 
 
8. Existe um grafo simples com cinco vértices dos seguintes graus? Se existir, desenhe um possível grafo. 
a) 3, 3, 3, 3, 2 
b) 1, 2, 3, 4, 5 
c) 1, 2, 3, 4, 4 
d) 3, 4, 3, 4, 3 
e) 0,1, 2, 2, 3 
f) 1, 1, 1, 1, 1 
 
9. Represente através das matrizes de incidência e de adjacência os grafos da questão 8. 
 
10. Em relação ao grafo a seguir. 
a) Qual a ordem do grafo? 
b) Quantas arestas o grafo possui?