Lista de exercícios de grafos

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.

...