2020 2 AV1 Teoria em Grafos

Prévia do material em texto

(
C
ENTRO 
U
NIVERSITÁRIO 
C
ARIOCA 
– U
NI
C
ARIOCA 
T
EORIA EM 
G
RAFOS 
– P
ROF
.: J
ÚLIO 
S
ILVEIRA 
– 2020/2 AV1
)
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.
 (
 
F
)B	C 
D
A	E
 (
4º = ABFA
) (
3º = ABCDEA
) (
2º = ABFDEA
) (
1º = AB
CDFA
)
 (
7º = EAFBCDE
) (
6º = DFAED
) (
5º = BCDFB
)
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 = 
90 = 
5n = 90 . 2
5n = 180
n = 
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 = → 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 = 
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.