Teoria dos Grafos - Exercícios 1

Prévia do material em texto

Página 1 
 1. (1,5) Considere o Grafo G(V, A): V = {1, 2, 3, 4, 5, 6} V = {(1,2), (1,4), (2,3), (3,5), (2,6), (1,6), (5,4), (3,5), (3,2)} Construa uma representação geométrica de G. 2. (1,0) Considere um grafo simples com 7 vértices, x2 , x3 , x4 , x5 , x6 , x7 , x8 , e arestas (xi , xj) se, e somente se, os inteiros i e j possuem um divisor comum diferente de 1. Dê uma representação gráfica para este grafo. 3. É possível existir um grupo de 7 pessoas tal que cada pessoa conheça exatamente 3 outras pessoas neste grupo? Por quê? 4. Os vértices do grafo são as casas de um tabuleiro de xadrez (generalizado) com t linhas e t colunas. Dois vértices são adjacentes se uma dama do jogo de xadrez pode saltar de um deles para o outro em um só movimento. Esse é o grafo dos movimentos da dama, ou simplesmente, o grafo da dama. Para deixar clara as dimensões do tabuleiro, podemos dizer que esse é o grafo da dama t-por-t. Quantos vértices e quantas arestas tem o grafo da dama 3-por-3? 
 Figura 1.1: Tabuleiros de xadrez 8-por-8. A figura da esquerda indica todos os vizinhos do vértice de bolinha escura (Exemplo 1). A da direita indica todos os vizinhos do vértice de bolinha escura no grafo do cavalo (Exemplo 2) 5. Por analogia com o exemplo anterior, definem-se o grafo do rei, o grafo do bispo, o grafo do cavalo e o grafo da torre t-por-t. Quantos vértices e quantas arestas tem o grafo do cavalo 4-por-4? 6. O grafo das palavras é assim definido: cada vértice é uma palavra da língua portuguesa e duas palavras são adjacentes se diferem em exatamente uma posição. Por exemplo, rato e ralo são adjacentes, enquanto ralo e rota não são. Faça uma figura da parte do grafo definida pelas palavras abaixo: caiado cavado cavalo girafa girava ralo ramo rata rato remo reta reto rota vaiado varado virada virado virava 7. Um cubo de dimensão k, ou k-cubo, é o grafo definido da seguinte maneira: os vértices do grafo são todas as sequências b1b2 ... bk em que cada bi pertence a {0, 1}. Dois vértices são adjacentes se diferem em exatamente uma posição. Faça as figuras dos cubos de dimensões 1, 2 e 3. 8. O grafo dos estados do Brasil é definido da seguinte maneira: cada vértice é um dos estados da República Federativa do Brasil; dois estados são adjacentes se têm uma fronteira em comum. Quantos vértices tem o grafo? Quantas arestas? Desenhe o gráfico do grafo, rotulando os vértices com os nomes dos estados. 
 
 
 
 
Data 
Período 
 
Professor Disciplina 
Curso 
 
 
Nota 
Nome do aluno 
 Lista de Exercícios 1 
Tipo de Avaliação 
 RA 
 
 Página 2 
 9. A grade p-por-q é o grafo definido da seguinte forma: o conjunto de vértices é o produto cartesiano {0, 1, 2, ..., p}×{0, 1, 2, ..., q} e dois vértices (ݔଵ, ݕଵ) e (ݔଶ, ݕଶ) de V são adjacentes se ݔଵ = ݔଶ e |ݕଵ − ݕଶ| = 1 ou se ݕଵ = ݕଶ e |ݔଵ − ݔଶ| = 1. Veja a figura abaixo. Dessa forma, construa algumas grades e responda: Quantas arestas tem a grade p-por-q? 
 10. (1,0) O grafo abaixo representa respostas à pergunta: “Quais são os colegas de quem você mais gosta?” dada por uma turma do 1º grau de uma escola. a) Use a notação e a nomenclatura convenientes para indicar a existência de líder(es), amizades recíprocas, problemas de relacionamento e isolamento. b) Por que podemos chamar a representação abaixo de dígrafo? Qual a diferença entre dígrafos e grafos em termos de pares ordenados e pares não ordenados? c) Identifique no dígrafo associado às respostas dos alunos, se houver, uma fonte e um sumidouro. 
 11. Faça a figura de um K3, de um K4 e de um K5. Quantas arestas possui um Kn? 12. Verifique se os grafos abaixo são isomorfos. Se houver isomorfismo, explicite-o analiticamente e, em seguida, verifique se a adjacência de arestas é preservada. Caso não seja isomorfismo, utilize a Teoria dos Grafos para lhe fornecer um argumento válido: a) 
 b) 
 13. Quais dos grafos abaixo são isomorfos entre si? 
1 2
3 4
5
67
8
 
 Página 3 
 14. (2,0) Considere o dígrafo a seguir: 
 Então, classifique as afirmativas abaixo em VERDADEIRAS (V) ou FALSAS (F), justificando quando forem falsas: I. O grafo associado ao dígrafo é simples, já que possui loops e arestas paralelas. II. c é divergente a u. III. a é convergente a e. IV. u e w são adjacentes. V. a e f são adjacentes. 
u v
wx
a
b
c
d
ef
g