Av2 -Teoria dos Grafos 2

Prévia do material em texto

CURSO: 
	
	CÓD/ DISCIPLINA: Teoria dos Grafos
	
	PROFº.: 
	TURNO: 
	
	TURMA: 
	SALA: Virtual
	MAT.: 
	NOTA
	GRADUAÇÃO
	ALUNO(A): 
	
	
	AV1 ( ) – AV2 ( X ) – AV3 ( )
	
1- As figuras a seguir representam grafos. Marque a opção que representa o grafo G, onde V={1,2,3,4,5,6} e E={(1,2),(1,4),(2,3),(2,5),(3,6),(4,5),(5,6)}
Letra A.
2- Seja o grafo G abaixo. Marque a opção que representa o grafo G:
 a) ( ) ({a, b, c, d, e}, {{a, b}, {a, c}, {a, d}, {b, e}, {c, d}}).
 b) (X) ({a, b, c, d, e}, {{a, b}, {a, d}, {a, e}, {c, d}, {b, e}}).
 c) ( ) ({a, b, c, d, e}, {{a, c}, {b, d}, {b, e}})
 d) ( ) ({a, b, c, d, e}, {{a, b}, {a, c}, {a, d}, {b, e}, {c, d}})
 e) ( ) ({a, b, c, d, e}, {{a, b}, {b, c}, {d, e}})
3- Sabendo que o número de clique de G é o tamanho do maior clique; denota-se por ω(G). Sejam G e H os dois grafos da figura abaixo:
a) ( ) ω(G) = 2 e ω(H) = 1
b) ( ) ω(G) = 1 e ω(H) = 2
c) ( ) ω(G) = 2 e ω(H) = 3 FOTO NO FINAL
d) (X) ω(G) = 2 e ω(H) = 4
e) ( ) ω(G) = 1 e ω(H) = 3
4- Sabendo que o número de independência de G é o tamanho do maior conjunto independente; denota-se por α (G). Sejam G e H os dois grafos da figura abaixo:
 a) ( ) α (G) = 1 e α (H) = 2
 b) ( ) α (G) = 2 e α (H) = 3
 c) ( ) α (G) = 3 e α (H) = 3 FOTO NO FINAL
 d) (X) α (G) = 2 e α (H) = 2
 e) ( ) α (G) = 3 e α (H) = 4
5- Seja G o grafo da figura abaixo. Quantos caminhos diferentes há de a a b?
 a) ( ) 6
 b) ( ) 7
 c) ( ) 8
 d) (X) 9
 e) ( ) 10
6- Qual a opção abaixo onde a concatenação se comuta:
a) ( ) W1 = 1~2~4~6 e W2 = 6~2~3~2
b) ( ) W1 = 1~2~3~4 e W2 = 4~2~1~5
c) (X) W1 = 1~3~5~6 e W2 = 6~2~5~4
d) ( ) W1 = 1~2~2~6 e W2 = 6~4~1~3
e) ( ) W1 = 1~3~4~5 e W2 = 5~2~3~1
	
7- Seja G um grafo em que todo vértice tem grau 2. G é necessariamente um ciclo? Explique usando um exemplo. Sim, Pois se não for ciclo, nem todos ficaram com grau 2
8- Existem exatamente três árvores com conjunto de vértices {1, 2, 3}. Note que todas essas árvores são caminhos; a única diferença é que vértice tem grau 2. 
Quantas árvores têm conjunto de vértices {1, 2, 3, 4}?
9- Seja G um grafo. Um passeio em G que atravessa cada aresta exatamente uma vez é chamado trilha euleriana. Se, além disso, a trilha começa e termina no mesmo vértice, o passeio é denominado um tour euleriano. Por fim, se G tem um tour euleriano, dizemos que G é euleriano.
Qual dos passeios representa um tour eureliano?
a) ( ) 1~2~4~5~3~1~5
b) (X) 1~2~5~3~4~5~1
c) ( ) 1~3~5~4~2~1~5
d) ( ) 1~2~3~4~5~2~4
e) ( ) 1~3~5~2~4~3~5
10- Seja G um grafo. Um passeio em G que atravessa cada aresta exatamente uma vez é chamado trilha euleriana. Se, além disso, a trilha começa e termina no mesmo vértice, o passeio é denominado um tour euleriano. Por fim, se G tem um tour euleriano, dizemos que G é euleriano.
Qual dos passeios representa uma trilha eureliano mas não um tour eureliano?
a) ( ) 1~2~4~5~3~1~5~4
b) (X) 1~2~5~3~4~5~1~3
c) ( ) 1~3~5~4~2~1~5~3
d) ( ) 1~2~3~4~5~2~4~1
e) ( ) 1~3~5~2~4~3~5~1