Grafos
Exercícios
Módulos 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)}
[pic]
Represente-o através de suas matrizes de adjacência e de incidência.
Matriz de adjacência Matriz de incidência
[pic] [pic]
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.
V{(J(oão), P(edro), A(ntônio), M(arcelo), F(rancisco), Da(ma), X(adrez), Do(minó)}
E={(J,X), (P,Da), (P, X), (A,X), (A,DA), (A,Do), (M,Da)},
[pic]
b) Defina um subgrafo em que todos, menos Francisco, joguem ao mesmo tempo.
[pic]
c) A partir do grafo bipartido do item a) construa um grafo rotulado que mostra quem pode jogar com quem o que.
[pic]
3) Construa representações geométricas de grafos regulares de grau r (r = 1,2,3 e 4).
[pic]
4) Identifique se os grafos a seguir são isomorfos:
a) b)
c)
Os pares em a) e b) são isomorfos. c) não, pois o vértice com laço à esquerda tem um vizinho de grau 4 e o vértice com laço à direita não tem. Observe que um isomorfismo deve manter as vizinhanças.
5) Quantos grafos (simples) não isomorfos com 4 vértices existem? Mostre as representações geométricas desses grafos
[pic]
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 ? Resp. vide questão