Lista 1 1

UFPI – CCN - DC
Disciplina: Teoria e Aplicações em Grafos
Prof. Antonio Costa

1ª lista de exercícios

1. Esboce o diagrama de cada um dos seguintes grafos G = (V,E):
a) V = {1, 2, 3, 4, 5, 6} e E = {{1,2}, {1,3}, {1,4}, {2,5}, {2,6}, {3,5}, {3,6}, {4,5}, {4,6}}.
b) V = {1, 2, 3, 4, 5} e E = {{1,2}, {1,4}, {2,3}, {2,4}, {2,5}, {3,4}, {3,5}}.
c) V = {1, 2, 3, 4, 5} e E = {{1,2}, {1,4}, {1,5}, {2,3}, {3,4}, {4,4}}.
d) V = {1, 2, 3, 4, 5, 6} e E = {{1,2}, {1,4}, {1,4}, {2,3}, {2,5}, {3,5}}.

2. Identifique os grafos simples na questão 1. Se um grafo simples é identificado, determine se ele é i) grafo bipartido, ii) grafo completo, iii) grafo bipartido completo, ou iv) grafo não bipartido completo.
3. Determine o número de arestas em um grafo completo com n vértices.
4. Encontre o número de arestas em um grafo bipartido completo k m, n.
5. Mostre que a soma dos graus de um grafo é duas vezes o seu número de arestas.
6. Mostre que todo grafo tem um número par de vértices impar.
7. Encontre que número máximo de arestas em um grafo bipartido.
8. Encontre o menor número de vértices necessários para construir um grafo completo com pelo menos 1000 arestas.
9. Mostre que os vértices do grafo bipartido G = (X, Y, E) com m vértices em X e n vértices em Y podem ser enumerados de modo que a matriz de adjacência tenha a forma:

0 A
At 0

onde A é uma matriz m x n no qual cada elemento é 0 ou 1, At é a transposta de A e 0 é a matriz nula.
10. Teste se [ 5 4 3 3 3 3 3 2] é uma seqüência de graus de um grafo. Caso positivo, esboce o grafo correspondente.
11. Teste se [ 6 6 5 4 3 3 1] é uma seqüência de graus de um grafo.
12. Encontre x de modo que [ 8 x 7 6 6 5 4 3 3 1 1 1] seja uma seqüência de graus de um grafo.
13. Mostre que não existe um grafo simples com seis vértices no qual os graus de cinco vértices são 5, 5, 3, 2 e 1.
14. Mostre que um vetor finito estritamente decrescente não pode ser uma seqüência de graus de um grafo.
15.