Lista 2 16Q

Prévia do material em texto

1- Na teoria dos grafos, uma árvore é um grafo conexo (existe caminho entre quaisquer dois 
de seus vértices) e acíclico (não possui ciclos). Toda árvore é um grafo, mas nem todo grafo 
é uma árvore. Toda árvore é um grafo bipartido e planar. Todo grafo conexo possui pelo 
menos uma árvore de extensão associada, composta de todos os seus vértices e algumas 
de suas arestas. Seja uma árvore com n vértices, quantas arestas têm essa árvore? 
A) Tem n arestas. 
B) Tem várias arestas. 
C) Tem n - 1 arestas. 
D) Tem 1 aresta. 
E) Tem n + 1 arestas. 
 
2- De acordo com sua resposta da questão 1 qual das alternativas abaixo representa uma 
justificativa correta da resposta dada na questão anterior? 
A) Toda árvore com n vértices tem n – 1 arestas, n ≥ 1. 
B) Toda árvore com n vértices tem várias arestas, n ≥ 1. 
C) Toda árvore com n vértices tem n arestas, n ≥ 1. 
D) Toda árvore com n vértices tem n + 1 arestas, n ≥ 1. 
C) Toda árvore com n vértices tem 1 arestas, n ≥ 1. 
 
3- Um grafo é conexo se, para qualquer par {v, w} de seus vértices, existe um caminho com 
extremos v e w. Por exemplo, o grafo bispo não é conexo (a menos que o tabuleiro tenha 
uma só linha e uma só coluna). Sabendo disso, analise o grafo simples conexo abaixo e 
determine a sequência de graus correta. 
 
A) (3, 3, 3, 3, 3, 5, 5, 5) 
B) (3, 7, 3, 6, 3, 1, 5, 2) 
C) (1, 4, 2, 8, 3, 2, 7, 5) 
D) (1, 1, 2, 3, 3, 4, 4, 6) 
E) (2, 3, 4, 1, 5, 6, 2, 3) 
 
4- Como está escrito na questão anterior, “um grafo é conexo se, para qualquer par {v, w} de 
seus vértices, existe um caminho com extremos v e w.” Na questão anterior a partir do grafo 
determinamos a sequência de graus correta, agora vamos determinar o grafo correto apartar 
da sequência. De acordo com a sequência de graus (3, 3, 3, 3, 3, 5, 5, 5) qual das alternativas 
representa o grafo correto. 
A) 
B) 
C) 
D) 
E) 
 
5- Os amigos João, Pedro, Antônio, Marcelo e Francisco sempre se encontram para botar 
conversa fora e às vezes jogar dama, xadrez e dominó. As preferências de cada um são as 
seguintes: João só joga xadrez; Pedro não joga dominó; Antônio joga tudo; Marcelo não joga 
xadrez e dominó e Francisco não joga nada. Marque a alternativa que representa o subgrafo 
em que todos, menos Francisco joguem ao mesmo tempo. 
V{(J(oão), P(edro), A(ntônio), M(arcelo), F(rancisco), Da(ma), X(adrez), Do(minó)} 
E= {(J, X), (P,Da), (P, X), (A,X), (A,DA), (A,Do), (M,Da)}, 
 
A) 
B) 
C) 
D) 
E) 
 
6- Os amigos João, Pedro, Antônio, Marcelo e Francisco sempre se encontram para botar 
conversa fora e às vezes jogar dama, xadrez e dominó. As preferências de cada um são as 
seguintes: João só joga xadrez; Pedro não joga dominó; Antônio joga tudo; Marcelo não joga 
xadrez e dominó e Francisco não joga nada. Qual das alternativas NÃO é um subgrafo. 
A) 
B) 
C) 
D) 
 
E) Todas as alternativas são subgrafos 
 
7- Um isomorfismo entre dois grafos G e H é uma bijeção f de V(G) em V(G) tal que dois 
vértices v e w são adjacentes em G se, e somente se f(v) e f(w) são adjacentes em H. Dois 
grafos G e H são isomorfos se existe um isomorfismo entre eles. Em outras palavras, dois 
grafos são isomorfos se é possível alterar os nomes dos vértices de um deles de tal modo 
que os dois grafos fiquem iguais. Identifique se os grafos A B e C a seguir são isomorfos, e 
marque a alternativa correta. 
A) B) 
C) 
 
A) Somente A é isomorfo. 
B) Somente B é isomorfo. 
C) A e B são isomorfos. 
D) A e C são isomorfos. 
E) Somente C é isomorfo. 
 
8- De acordo com o texto da questão 7 “Dois grafos G e H são isomorfos se existe um 
isomorfismo entre eles. Em outras palavras, dois grafos são isomorfos se é possível alterar 
os nomes dos vértices de um deles de tal modo que os dois grafos fiquem iguais.” Marque a 
alternativa em que os grafos NÃO são isomorfos. 
A) 
 B) 
C) 
D) 
E) 
 
 
9- Ainda sobre isomorfismo, seguindo a mesma ideia da questão 8. Marque a alternativa em 
que os grafos são isomorfos. 
A) 
B) 
C) 
D) 
E) 
 
10- Um caminho é qualquer grafo da forma ({v1, v2,..., vn}, {vivi+1 : 1 ≤ i < n}). Em outras 
palavras, um caminho é um grafo C cujo conjunto de vértices admite uma permutação (v1, 
v2,..., vn) tal que {v1v2, v2v3, ..., vn-1 vn} = A(C). Como sabemos o que é um caminho, qual 
das alternativas representa o caminho (simples) do grafo abaixo. 
 
A) a, c, d, e, b 
B) b, c, d, a, b 
C) a, b, c, d, e 
D) e, c, a, b, d 
E) d, b, a, c, e 
 
11- Um Caminho Euleriano é um caminho em um grafo que visita cada aresta apenas uma 
vez. Sabendo disso marque a alternativa que representa o caminho Euleriano do grafo 
abaixo. 
 
A) a, b, e, d, c, b, a 
B) a, b, e, d, c 
C) a, b, c, d, e 
D) b, c, d, e, b, a 
E) c, b, e, d, c, a, b 
 
12- Diz-se que um grafo é n-conexo ou que tem n-conectividade se o número mínimo de 
vértices (bem como as arestas que nela incidem) que é preciso suprimir para o desconectar 
ou reduzir ao grafo trivial K1 for n ou mais. Uma consequência imediata é que, se G for conexo 
e não tiver vértices de articulação, então G é 2-conexo. De acordo com a definição de 
conectividade, analise o grafo abaixo e marque a alternativa correta sobre a conectividade 
K(G). 
 
A) K(G) = 5 
B) K(G) = 2 
C) K(G) = 1 
D) K(G) = 3 
E) K(G) = 4 
 
13- O corte associado a (ou cofronteira de) um conjunto X de vértices é o conjunto de todas 
as arestas que têm uma ponta em X e outra em V(G) \ X (complemento). O corte associado 
a X será denotado por: . Para o grafo G = (V, E) abaixo, marque a alternativa que 
representa corretamente um corte de vértice. 
 
A) (4, 3) 
B) (2, 3) 
C) (1, 2) 
D) (4, 2) 
E) (5, 2) 
 
14- De acordo com a conceito de corte “O corte associado a (ou cofronteira de) um conjunto 
X de vértices é o conjunto de todas as arestas que têm uma ponta em X e outra em V(G) \ X 
(complemento). O corte associado a X será denotado por: . ” Analise o grafo abaixo e 
marque a alternativa que NÃO representa corretamente um corte de arestas. 
 
A) (6, 3) 
B) (4, 3) 
C) (1, 2) 
D) (5, 2) 
E) (2, 3) 
 
15- Um grafo G é dito planar se puder ser representado graficamente no plano de tal forma 
que não haja cruzamento de suas arestas. Caso contrário o grafo é dito não-planar. O grafo 
G abaixo é planar? 
 
A) Sim, é planar. Basta refazer a aresta entre 6 e 1 passando por fora. 
B) Sim, é planar. Basta refazer a aresta entre 1 e 5 passando por fora. 
C) Sim, é planar. Basta refazer a aresta entre 5 e 2 passando por fora. 
D) Sim, é planar. Basta refazer a aresta entre 4 e 5 passando por fora. 
E) Não é planar. 
 
16- De acordo com a definição de grafos planares “Um grafo G é dito planar se puder ser 
representado graficamente no plano de tal forma que não haja cruzamento de suas arestas. 
Caso contrário o grafo é dito não-planar.” Marque a alternativa onde o grafo NÃO é planar. 
A) 
B) 
C) 
D) 
E)