Lista de exercícios - Teoria dos Grafos

Prévia do material em texto

Data
 Disciplina de:
Professora
 
Teoria dos Grafos
Tipo de Avaliação
Nota
Período
Curso
 	 
 Lista de Exercícios 1
Nome do aluno
RA
(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.
(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.
É possível existir um grupo de 7 pessoas tal que cada pessoa conheça exatamente 3 outras pessoas neste grupo? Por quê?
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)
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?
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
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.
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.
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?
(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. 
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.
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?
Identifique no dígrafo associado às respostas dos alunos, se houver, uma fonte e um sumidouro.
Faça a figura de um K3, de um K4 e de um K5. Quantas arestas possui um Kn?
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:
Quais dos grafos abaixo são isomorfos entre si?
(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.
	Página 1