TrabalhosGratuitos.com - Trabalhos, Monografias, Artigos, Exames, Resumos de livros, Dissertações
Pesquisar

Lista de exercícios de grafos

Por:   •  24/4/2015  •  Pesquisas Acadêmicas  •  578 Palavras (3 Páginas)  •  1.226 Visualizações

Página 1 de 3

4ª Lista de exercícios

  1. Desenhe um grafo com quatro nós e ciclos de comprimento 1, 2, 3 e 4.
  2. Desenhe um grafo não completo com quatro nós, cada um de grau 4.
  3. Desenhe um grafo com quatro nós de graus 2, 3, 3 e 4, respectivamente, ou explique por que não existe tal grafo.
  4. Desenhe um grafo com quatro nós de graus 2, 3, 3 e 3, respectivamente, ou explique por que não existe tal grafo.
  5. Demonstre que se um grafo de n nós existe, então a seqüência (d1, d2, ..., dn) de inteiros não negativos que corresponde à seqüência de graus do grafo é tal que [pic 1] é par.

* Considere a seguinte definição para as quatro questões seguintes: Um grafo G é k-regular se todo vértice de G possui grau k.

  1. Um grafo completo é regular? Justifique.
  2. Um grafo bipartido completo é regular? Justifique.
  3. Sejam A e B grafos isomorfos. Se A é k-regular, então B também é k-regular? Justifique.
  4. Quantas arestas possui um grafo k-regular com n vértices?

***************Isomorfismo*****************************

* Considere os três grafos abaixo para as próximas três questões.

[pic 2]

  1. Os grafos (a) e (b)  são isomorfos? Demonstre que são isomorfos, se o forem; caso contrário, justifique porque não o são.
  2. Os grafos (a) e (c)  são isomorfos? Demonstre que são isomorfos, se o forem; caso contrário, justifique porque não o são.
  3. Os grafos (b) e (c)  são isomorfos? Demonstre que são isomorfos, se o forem; caso contrário, justifique porque não o são.
  4. Os grafos abaixo são isomorfos? Justifique.

[pic 3]

  1. Os grafos abaixo são isomorfos? Justifique.

[pic 4]

  1. Prove que se dois grafos são isomorfos, então possuem o mesmo número de vértices e o mesmo número de arestas.
  2. Na questão anterior pode-se dizer que a recíproca é verdadeira?
  3. Prove que se dois grafos são isomorfos, então possuem a mesma seqüência de graus.
  4. Na questão anterior pode-se dizer que a recíproca é verdadeira?
  5. Desenhe todos os grafos não-isomorfos simples com quatro nós.

**************planares***********************

  1. Prove que K4 é um grafo planar.
  2. A condição [pic 5], onde ‘a’ é o número de arcos e ‘n’ é o número de nós, é uma condição necessária para que um grafo de três ou mais nós seja planar. Ela é suficiente? Por quê?
  3. Prove que o grafo k2,3 é um grafo planar.
  4. Se todos os nós de um grafo planar simples e conexo têm grau 4 e se o número de arcos é 12, em quantas regiões ele divide o plano?
  5. O grafo abaixo é planar?

[pic 7][pic 6]

  1. O grafo abaixo é planar?

        [pic 9][pic 8]

  1. O grafo abaixo é planar?

[pic 11][pic 10]

  1. Todo subgrafo de um grafo planar é planar? Justifique.
  2. Todo subgrafo de um grafo não-planar é não-planar. Justifique.
  3. Todo grafo que contém um grafo planar (como subgrafo) é planar. Justifique.
  4. Todo grafo que contém um grafo não-planar (como subgrafo) é não-planar. Justifique.

...

Baixar como (para membros premium)  txt (3 Kb)   pdf (170.8 Kb)   docx (50.5 Kb)  
Continuar por mais 2 páginas »
Disponível apenas no TrabalhosGratuitos.com