Av2 -Teoria dos Grafos

Prévia do material em texto

CURSO: SI-CC
	
	CÓD/ DISCIPLINA: CCT0738 / Teoria dos Grafos
	
	PROFº.: Elano Diniz
	TURNO: Manhã
	
	TURMA: 1001
	SALA: Virtual
	MAT.: 
	NOTA
	GRADUAÇÃO
	ALUNO(A): 
	
	DATA: até 25/11 às 9h10min
	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
 Pois é a única figura que as arestas indicadas em E estão traçadas.
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}})
Alternativa B é a única que apresenta a ligação dos vértices mencionados.
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
d) (X) ω(G) = 2 e ω(H) = 4
e) ( ) ω(G) = 1 e ω(H) = 3
{2},{1,2},{1,4} ω(G) = 2.
{3,9,5,4} ω(H) = 4.
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
 d) (X) α (G) = 2 e α (H) = 2
 e) ( ) α (G) = 3 e α (H) = 4
{1},{2,5},{3,6} (G) = 2.
{1,9},{3,6} (H) = 2.
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) ( ) W1 = 1~3~5~6 e W2 = 6~2~5~4
 d) ( ) W1 = 1~2~2~6 e W2 = 6~4~1~3
 e) (X) W1 = 1~3~4~5 e W2 = 5~2~3~1
 O item E é o único que se comuta, assim como 
 mostrado no exemplo acima com as ligações de {1,1} e {5,5}.
7- Seja G um grafo em que todo vértice tem grau 2. G é necessariamente um ciclo? Explique usando um exemplo
G é necessariamente um ciclo, pois para não formar um ciclo o grafo deveria ter uma folha, e a partir do momento que tenha uma folha, o vértice dessa folha terá grau 1, assim como mostra o exemplo a seguir em que o vértice 6 teve de ser ligado ao 5 e formar um ciclo, pois sem esta ligação ele teria grau 1.
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}?
Nenhuma, pois há 3 árvores com 3 vértices cada, logo não faz sentido entre uma delas haver um conjunto com 4 vértices assim como é pedido na questão.
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
Somente a letra B termina no mesmo vértice que começa (vértice 1).
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
A letra D e E iniciam e terminam no mesmo vértice, na letra A o passeio repetiria a aresta {4,5}, já na letra C o passeio repetiria o caminho nas arestas de {5,3}, por tanto, apenas a letra B realizaria o passeio sem repetir arestas e sem terminar o trajeto no mesmo vértice que iniciou.