Quetionário teoria de grafos unip

Prévia do material em texto

Bacharelado em Ciência da Computação e Sistemas de Informação 3o.
Lista de Exercícios – Teoria dos Grafos
	Nome: 
Jonathan Fernando Almeida Silva 
	RA.:
D7954H-0
	Curso: 
CIÊNCIA DA COMPUTAÇÃO
	Turma:
CC4
	
Questão 1: (0,5 ponto) Para o grafo direcionado ilustrado, apresente:
a) (0,25 pontos) a função g que é parte definição formal do grafo;
RESPOSTAS:
G={V,A ,g}
 V={1,2,3}
 A={x, y, z}
 A={{1,2,x},{1,3,y},{2,3,z},{2,2,t}}
b) (0.25 pontos) a matriz e a lista de adjacência;
 (
x
1
2
z
3
)
t
y
 RESPOSTAS: MATRIZ DE ADJAÊNCICAS 
 
LISTA DE ADJACENCICAS
1=2,3
2=2,3
3={}
Questão 2: ( 0,25 pontos) Considere as seguintes afirmações:
I - A teoria dos grafos é aplicável a diversos problemas de interesse prático. Confira-se o que Roger Pressman afirma: “o teste do software começa criando um grafo de objetos importantes e suas relações e então imaginando uma série de testes que abrangerá o grafo de forma que cada projeto e relação sejam exercitados e os erros sejam descobertos Para executar esses passos, você começa criando um grafo – uma coleção de
nós que representam objetos, ligações que representam as relações entre objetos, pesos de nó que descrevem as propriedades de um nó, (por exemplo o valor específico de um dado ou comportamento de estado) e pesos de ligação (link weights ) que descrevem alguma característica de uma ligação. (Pressman, R. 2011, Engenharia de Software Uma Abordagem Profissional ).
II - A teoria dos grafos é aplicável a diversos problemas de interesse prático. Um exemplo diz respeito ao gerenciamento de recursos em sistemas operacionais. Considere-se o seguinte texto: “ É possível representar
graficamente a alocação de recursos entre as tarefas de um sistema concorrente. A representação gráfica provê uma visão mais clara da distribuição dos recursos e permite detectar visualmente a presença de esperas 
circulares que podem caracterizar impasses. Em um grafo de alocação de recursos é possível representar graficamente a alocação de recursos entre as tarefas de um sistema concorrente. A representação gráfica provê uma visão mais clara da distribuição dos recursos e permite detectar visualmente a presença de esperas circulares que podem caracterizar impasses.
.” (Mazziero, C. Sistemas Operacionais Conceitos e Mecanismos, 2017).
Considere as seguintes alternativas e assinale, SEM RASURAR a alternativa correta.
a) Apenas a afirmação I diz respeito a um conceito que estende (torna mais geral) o conceito de grafos.
b) As afirmações I e II dizem respeito a conceitos que estendem (tornam mais geral) o conceito de grafos.
c) Sem generalizações, as afirmações I e II apresentam exemplos de uso da teoria dos grafos.
d) Apenas a afirmação II diz respeito a um conceito que estende (torna mais geral) o conceito de grafos.
e) As afirmações I e II dizem respeito a conceitos que reduzem o conceito de grafos.
RESPOSTA: 
Alternativa A, relata o que está escrito nos livros e com o que se aplica à teroria de grafos, e aquestão 2 também 
Faz parte deste conesto.
Questão 3: (2,75 pontos)Responda as perguntas a seguir sobre o grafo na figura a seguir.
i. (0.25 pontos) O grafo e simples?
R: Um grafo simples G=(V,A), é uma estrututa discreta formada por um conjunto não vazio devértices e um conjunto de arestas .
ii. (0.25 pontos) O grafo é completo?
R: Um grafo completoé um grafo simples em todo vértice e adjacente a todos outros vértices
iii. (0.25 pontos) O grafo é conexo?
R: Um grafp é conexo se há pelomenos uma cadeia ligando cada par de vértices.
iv. (0.25 pontos) Encontre dois caminhos de A para D.
R= C1= {51}
 C2= {8,4}
v. (0.25 pontos) Encontre um ciclo de comprimento 6.
R:={4,1,2,3,1,6,4}
vi. (0.25 pontos) Este grafo divide o plano em quantas regiões? Justifique sua resposta.
Resposta: Neste grafo podemos identificar 5 formasplanares que são 2 isoceles, 1 triângulo e dois losangos.
vii. 
(0,25 ponto) Apresente o algoritmo de Dijkstra para encontrar o caminho mínimo entre os nós A e E. 
viii. (0,25 ponto) Apresentar a matriz de adjacência modificada do grafo.
Resposta: 
ix. (0,75 ponto) Apresentar as diversas iterações para a obtenção da árvore geradora mínimA
 (
2
B
C
3
4
1
5
2
1
A
G
H
D
8
1
1
5
4
F
6
E
)
 A
 F B
 
 
 C 
 
 
 
 D H
 
 
 E G
 
 (
5
)
Questão 4: (0,5 pontos) Pede-se:
a) (0,25 ponto) O grafo K3,3 é planar? Justifique sua resposta.
Resposta: Não, por que um grafo planar não pode existir intersecção entre as arestas, e permite uma representação no plano sem que as linhas se cruzem. 
b) (0,25 ponto) Para o grafo seguinte, apresente: o número cromático e o mapa dual;
R= Número cromático é de 3,logo usaremos 3 cores. 
 Azul ={G,H}
 Amarelo={C,E}
 Verde={B,F}
 (
B
C
G
H
F
 
E
)
Questão 5: (0,25 pontos) O grafo seguinte é homeomorfo a K5 ou a K3,3?.
Resposta: K5, Por que temos um formato de estrela, que écomposto por 5 arestas, no interno e no externo.
e	f
j
g
d	i		h	b c
Questão 6: (0,5pontos) Considere o grafo K6.
a) (0,25 ponto) Pergunta-se: quantas arestas devem ser removidas deste grafo a fim de se obter um grafo planar?
Resposta: Tamamosumexemplo este grafo k6, e para torna-loum grafo planar, temos que retirar 3 arestas pois um grafo planar não pode existir linha cruzando o seu plano. 
(0,25 ponto) A relação de Euler é válida para o grafo obtido no item a) ?
Resposta: O caminho de Euler é ocaminho que utiliza o caminho de todas asarestas de um grafo uma unica vez. E não condiz com esta regra pois precisariamos de pelomenos 2 arestas impares, sendoque temosque começar e terminar nos vértices que tem grau impar .
Questão 7: (0,25 pontos): Mostre que os dois grafos abaixo são isomorfos
Resposta: Estes grafos são isomorfos por que a relaçãode incidência esta cendo preservada. 
Onde existe uma funçãounivoca , tal que (i,j) éelemento de G e se somente s fi , fj é elemento de H.
123
1FV
2FV
3FF
Plan1
		1	2	3
	1	F	V
	2	F	V
	3	F	F
VPasso1Passo2Passo 3Passo 4Passo 5
A(0,A)
B(3,A)
C(5,A)
D***
E(8,A)(7,F)(7,F)
F(1,A)(6,F)
G***(6,F)
H***(7,G)
Plan1
	V	Passo1	Passo2	Passo 3	Passo 4	Passo 5
	A	(0,A)
	B	(3,A)
	C	(5,A)
	D	***
	E	(8,A)	(7,F)	(7,F)
	F	(1,A)	(6,F)
	G	***		(6,F)
	H	***		(7,G)
ABCDEF
A3581
B32
C521
D14
E846
F16
G45
H21
Plan1
		A	B	C	D	E	F	G	H
	A		3	5		8	1
	B	3		2				4
	C	5	2		1				2
	D			1		4
	E	8			4		6		1
	F	1				6		5
	G		4				5		1
	H			2		1		1