2 Lista De Exerc Cios Grafos

Teoria dos Grafos
Exercícios e Revisão para Prova
Aulas 1 e 2 - Conceitos Básicos &

Representação de Grafos

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)}
Represente-o através de suas matrizes de adjacência e de incidência.
2) Os amigos João, Pedro, Antônio, Marcelo e Francisco sempre se encontram para botar conversa fora e às vezes jogar dama, xadrez e dominó. As preferências de cada um são as seguintes: João só joga xadrez; Pedro não joga dominó; Antônio joga tudo; Marcelo não joga xadrez e dominó e Francisco não joga nada.
a) Represente através de um grafo bipartido G=(V,E) todas as possibilidades de um amigo jogar com os demais. Defina V e E.
b) Defina um subrafo em que todos, menos Francisco, joguem ao mesmo tempo.
c) A partir do grafo bipartido do item a) construa um grafo rotulado que mostra quem pode jogar com quem o que.
3) Construa representações geométrica de grafos regulares de grau r (r = 1,2,3 e 4).
4) Identifique se os grafos a seguir são isomorfos:
a)

b)

c)

5) Quantos grafos (simples) não isomorfos com 4 vértice existem? Mostre as representações geométricas desses grafos.

6) Exemplifique representações geométricas de grafos completos Kn (n = 1,2,3,4 e 5)
a) Quantas arestas possui um grafo completo Kn ? (Cn,p = n! / (p!(n-p)!), para p=2)
b) Calcule o total de arestas para n = 1,2,3,4 e 5.

7) Mostre que:
a) todo subgrafo induzido de um grafo completo é completo
b) todo subgrafo de um grafo bipartido é também bipartido.
8) 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.
11a) Observe a seguinte planta de uma casa

A

B
E

C
F

D

Fora

G

a) É possível entrar na casa, passar uma vez por todos os quartos e sair para fora? porquê? b) É possível, partindo de fora da casa, passar uma vez