Grafos

Disponível somente no TrabalhosFeitos
  • Páginas : 10 (2345 palavras )
  • Download(s) : 0
  • Publicado : 12 de março de 2013
Ler documento completo
Amostra do texto
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ênciaMatriz 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) Apartir 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 degrau 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ãoseguinte
b) Calcule o total de arestas para n = 1,2,3,4 e 5.


[pic]


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


PROVA: Item b): C m,2 significa o número de combinações possíveis entre pares de elementos distintos de m. Sem é o número de vértices de um grafo completo, entre cada par de elementos de m haverá uma aresta. Portanto n = C m,2.
Item a); Como todo grafo G com m vértices, tem no máximo, o mesmo número de arestas do que K(m), é claro que se n é o número de G valerá n ( C m,2


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

PROVA: Seja G=(V,E) um grafo simplescom n vértices. A partir dos vértices de G podemos formar o grafo completo K(n)=(V, E0). Como este grafo é contém todas arestas possíveis entre os vértices, necessariamente E ( E0.

9) Mostre que:

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

a) Como em um subgrafo induzido todas arestas do grafo originalentre os vértices do subgrafo são mantidas e o grafo original é completo, o subgrafo também será completo.
b) Basta manter os dois partidos do grafo original

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).

Para haver um ciclo hamiltoniano em um grafo bipartido, este deve retornar ao mesmopartido da origem. Um caminho de retorno ao partido da origem necessitará um número par de passos (pois a cada passo muda-s de partido) Se o ponto de destino for distinto da origem um número par de passos (arestas) determinará um número ímpar de vértices. Para ser um ciclo, o vértice destino coincidirá com o vértice origem, portanto teremos um vértice a menos. Ou seja, um número par de vértices....
tracking img