2020 2 AV1 Teoria em Grafos

Prévia do material em texto

F 
 
 
 
NOME COMPLETO: Carolyne Rodrigues Santana Ferreira 
MATRÍCULA: 2016200472 DISCIPLINA: Teoria em Grafos TURMA: 141 
 
 
 
Questão 1 (0.6 pontos) 
Desenhe um grafo 4-regular que seja planar, ou prove que tal grafo não existe. Mostre TODOS os seus cálculos. 
 
 
 
 
 
 
Questão 2 (1.4 pontos) 
Enumere todos os ciclos simples existentes no grafo abaixo. 
 
B C 
 
D 
 
A E 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
CENTRO UNIVERSITÁRIO CARIOCA – UNICARIOCA 
TEORIA EM GRAFOS – PROF.: JÚLIO SILVEIRA – 2020/2 
AV1 
1º = ABCDFA 2º = ABFDEA 3º = ABCDEA 4º = ABFA 
5º = BCDFB 6º = DFAED 7º = EAFBCDE 
 
 
 
 
Questão 3 (1.0 ponto) 
Quantos vértices possui um grafo 5-regular contendo m = 90 arestas. Mostre TODOS os seus cálculos. 
 
m = 
(𝑟 .𝑛)
2
 
 
90 = 
(5 .𝑛)
2
 
 
5n = 90 . 2 
5n = 180 
n = 
180
5
= 36 
 
Resposta é 36 vértices. 
 
 
 
 
 
Questão 4 (1.8 pontos) 
Desenhe todos os grafos 2-regulares distintos (não isomorfos) existentes contento n = 12 vértices. 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
Questão 5 (1.0 pontos) 
Qual o número máximo de arestas em um grafo bipartido contendo 25 vértices no total. 
JUSTIFIQUE sua resposta COM CLAREZA. Mostre ao menos um cálculo diferente do valor máximo. 
 
E(K1,24) = 1 . 24 = 24 
E(K2,23) = 2 . 23 = 46 
E(K3,22) = 3 . 22 = 66 
E(K4,21) = 4 . 21 = 84 
E(K5,20) = 5 . 20 = 100 
E(K6,19) = 6 . 19 = 114 
E(K7,18) = 7 . 18 = 126 
E(K8,17) = 8 . 17 = 136 
E(K9,16) = 9 . 16 = 144 
E(K10,15) = 10 . 15 = 150 
E(K11,14) = 11 . 14 = 154 
E(K12,13) = 12 . 13 = 156 
 
Resposta é 156 arestas no máximo. 
 
 
 
 
 
 
Questão 6 (0.6 pontos) 
Quantos vértices possui um grafo completo contendo 780 arestas? Mostre TODOS os seus cálculos. 
A = 
𝑛(𝑛−1)
2
 → n2 – n = 780 . 2 → n2 – n = 1560 
n2 – n – 1560 = 0 
Δ = b2 – 4.a.c 
a= 1 ; b= -1 ; c= -1560 
Δ = (-1)2 – 4.1.(-1560) 
Δ = 6241 
n = 
− 𝑏2±√𝛥
2.𝑎
= 
−(−12)± √6241
2.1
= 
1+79
2
= 
80
2
= 40 
Resposta é 40 vértices. 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
Questão 7 (0.6 pontos) 
Desenhe dois grafos Bipartidos Completos contendo SETE vértices ao todo. Um deles deverá ser planar e o outro não. 
Cada partição deve ter NO MÍNIMO DOIS nós. O grafo planar deve ser desenhado com uma representação plana. 
 
 
 
 
	Questão 1 (0.6 pontos)
	Questão 2 (1.4 pontos)
	B C
	Questão 3 (1.0 ponto)
	Questão 4 (1.8 pontos)
	Questão 5 (1.0 pontos)
	Questão 6 (0.6 pontos)
	Questão 7 (0.6 pontos)