2020 2 AV1 Teoria em Grafos

Prévia do material em texto

CENTRO UNIVERSITÁRIO CARIOCA – UNICARIOCA 
TEORIA EM GRAFOS – PROF.: JÚLIO SILVEIRA – 2020/2 
AV1 
 
 O trabalho é INDIVIDUAL: trabalho com indícios de similaridade, todos serão avaliados com grau ZERO. 
 FORMA DE ENTREGA: postagem de arquivo EXCLUSIVAMENTE no formato PDF, no link disponível no AVA. 
 DATA DA ENTREGA: até 30/09/2020 
 FORMATO DO TRABALHO: o arquivo PDF deve ser gerado a partir de um editor eletrônico de textos e gráficos (para 
os autômatos). NÃO SERÃO CONSIDERADAS postagens com FOTOS ou com TEXTO MANUSCRITO. 
 LEIA AS INSTRUÇÕES: o DESENVOLVIMENTO DA QUESTÃO É OBRIGATÓRIO, quando solicitado! 
 ATENÇÃO: o cabeçalho do arquivo deve conter as informações abaixo: 
NOME COMPLETO: _______________________________________________________________________________ 
MATRÍCULA: ________________ DISCIPLINA: _______________________________________TURMA: _____________ 
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. 
D
EA
B
F
C
 
 
Questão 3 (1.0 ponto) 
Quantos vértices possui um grafo 5-regular contendo m = 90 arestas. Mostre TODOS os seus cálculos. 
 
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. 
 
Questão 6 (0.6 pontos) 
Quantos vértices possui um grafo completo contendo 780 arestas? Mostre TODOS os seus cálculos. 
 
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. 
 
 
 
BONS ESTUDOS!