Atividade_Modulos

Prévia do material em texto

Curso: Ciência da Computação Campus: Ribeirão Preto
J702 - TEORIA DOS GRAFOS
Nome: Eduarda Rossato Martins	RA: n2612h-4
Turma: CC5P18
Março, 2020
Módulo 1 
Questão 1: No grafo da figura, vértice 4 possui grau à:
A) 2 
B) 3
C) 4
D) 5
E) 6
Justificativa: Alternativa A – pois do vértice 4 saem duas arestas, portanto grau 2
Questão 2: No grafo da figura, ao passarmos pelos vértices 1;3;2;5;1 respectivamente, é correto afirmar que:
A) Estamos fazendo um ciclo de comprimento igual a 5 mas este ciclo não é simples.
B) Estamos fazendo um ciclo simples de comprimento igual a 4.
C) Não estamos fazendo ciclo, pois o grafo é acíclico.
D) Para o percurso ser considerado um ciclo é necessário passar pelo vértice 4.
E) Para o percurso ser considerado um ciclo é necessário que tenha pelo menos um laço.
Justificativa: Alternativa B – o caminho percorrido pelas arestas formam o comprimento 4 e se torna um grafo simples, sem nenhum laço e apenas 1 aresta saindo de casa vértice.
Questão 3: 
No grafo acima o vértice de maior grau é o de número:
A) 5
B) 6
C) 7
D) 8
E) 9
Justificativa: Alternativa B – o vértice 6 possui grau 4 pois saem 4 arestas dele, o maior de todos os outros.
Módulo 2 
Questão 4: Um grafo completo simples indicado por K7:
A) possui 7 arestas.
B) possui 21 vértices (ou nós).
C) possui 21 arestas.
D) é isomorfo ao grafo K5.
E) é isomorfo ao grafo K9.
Justificativa: Alternativa C – Por se tratar de um grafo completo todas as vértices se conectando, resultando em 21 arestas.
Questão 5: Com relação aos grafos G, H e K dados abaixo, podemos afirmar que:
A) G, H e K não são dois a dois isomorfos.
B) H e K são isomorfos, mas G não é isomorfo à H.
C) G e K são isomorfos, mas H não é isomorfo à K.
D) G e H são isomorfos, mas K não é isomorfo à G.
E) G, H e K são isomorfos entre si.
Justificativa: Alternativa E – Todos os grafos possuem o mesmo número de arestas e de vértices, podendo assim serem representados de outras maneiras diferentes.
Questão 6:
 
Com relação aos grafos G, H e K dados acima, podemos afirmar que:
A) A, B e C são isomorfos entre sí, mas não são isomorfos à D.
B) A é isomorfo à B e C é isomorfo à D, mas A não é isomorfo à C.
C) não é isomorfo à nenhum dos outros três grafos.
D) não existem grafos isomorfos neste grupo.
E) os quatro grafos são isomorfos entre si.
Justificativa: Alternativa E - Todos os grafos possuem o mesmo número de arestas e de vértices, podendo serem representados de outras formas.