Grafos

Teoria dos 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