Teoria Dos 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)}

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) Mostrar que:

a) se G é um grafo simples, então: n  C m,2

Onde: n = número de arestas

m = número de vértices

b) se G é um grafo completo, então: n = C m,2

8) Mostre que todo grafo simples com n vértices é isomorfo a um subgrafo de Kn.

9) Mostre que:

a) todo subgrafo induzido de um grafo completo é completo

b) todo subgrafo de um grafo bipartido é também bipartido.

10) Mostre que um grafo bipartido G=(V1  V2, E) com número ímpar de vértices não pode ser hamiltoniano (i.é. possuir ciclo hamiltoniano).

11) 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) É 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 por cada porta? porque?

12) 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?

d) A um mesmo grafo podem corresponder a diferentes matrizes I e A?

13) Prove o seguinte teorema:

 grau (v) = 2 n, onde n = número de arestas

v V

Dica!! Observar a matriz de incidência

14) Prove o seguinte corolário

Em qualquer grafo, o número de vértices de grau ímpar é sempre par.

15) Descreva uma situação que possa ser modelada por:

a) um grafo bipartido não completo;

b) um grafo bipartido completo

Apresente esses grafos

16) Apresente um exemplo de um grafo qualquer e seu respectivo grafo complemento

17) Apresente exemplos de subgrafos (G2 e G3) de um grafo bipartido G1 que sejam cliques.

18) Mostre um exemplo de um subgrafo que represente um conjunto independente de vértices.

19) O que é subgrafo gerador G2 de um grafo G1. Apresente um exemplo.

20) Exemplifique através de um grafo rotulado o relacionamento entre 5 dos seus melhores amigos (relacionamento = conhece)

Módulo 3 - Caminhos e Conexidade

1) Apresente um grafo, com no mínimo 5 vértices. Apresente suas matrizes de adjacência e de incidência. Mostre exemplos de :

a) percurso

b) caminho (simples)

c) trajeto (trilha)

d) ciclo

e) caminhos e ciclos hamiltonianos e eulerianos

f) a conectividade K(G)

2) Em todo grafo G, dois caminhos de comprimento máximo possuem, pelo menos, um vértice comum. Provar ou apresentar contra exemplos para os seguintes casos:

a) G é desconexo