Agoritmos e Grafos - Revisão P1

Prévia do material em texto

Questão 1: Seja G(V, E) o grafo não-direcionado cuja matriz de adjacências é
dada abaixo (células em branco indicam arestas inexistentes):
A terceira escolha feita pelo algoritmo de Kruskal para árvore geradora mínima
é:
a) o vértice 2
b) o vértice 4
c) o vértice 5
d) a aresta (1,5)
e) a aresta (1,2)
f) a aresta (2,4)
Resolução:
Primeiramente, o Algoritmo de Kruskal ordena as arestas em ordem crescente:
(4,5,1) ; (1,3,2) ; (1,2,4) ; (1,5,5) ; …
Depois, tenta montar árvores com as arestas de menor peso:
Algoritmos e Grafos - Lista de Revisão
Primeira escolha: aresta (4,5)
Segunda escolha: aresta (1,3)
Terceira escolha: aresta (1,2)
Questão 2: Para qual das operações abaixo a representação de grafos no
computador via matriz de adjacências é mais eficiente do que a representação
via listas de adjacências?
a) percorrer cada uma das arestas do grafo em qualquer ordem
b) obter o grau médio dos vértices do grafo
c) checar se quatro vértices dados constituem um subgrafo completo
d) localizar o vértice com o maior número de vizinhos de grau menor do que 2
e) NRA
Resolução:
Seja N o número de vértices, D o grau de um vértice e M o número de arestas do grafo:
a) percorrer cada uma das arestas do grafo em qualquer ordem;
- Matriz de Adjacências: O(N²)
- Listas de Adjacências: O(N + M)
Portanto, Falso.
b) obter o grau médio dos vértices do grafo;
- Matriz de Adjacências: O(N²)
- Listas de Adjacências: O(N)
Portanto, Falso.
c) checar se quatro vértices dados constituem um subgrafo completo;
- Matriz de Adjacências: O(3 + 2 + 1) => O(1)
- Listas de Adjacências: O(3*D) => O(D) com lista (Verdadeiro)
O(3 + 2 + 1) => O(1) com Hash Map (Falso)
Como é possível implementar as listas de adjacências com Hash Map, tornando
a complexidade a mesma da Matriz de Adjacências, a afirmação é falsa.
d) localizar o vértice com o maior número de vizinhos de grau menor do que 2.
- Matriz de Adjacências: O(N²)
- Listas de Adjacências: O(N)
Portanto, Falso.
Assim, a resposta certa é a letra E: Nenhuma das Respostas Acima (NRA).
Questão 3: Sejam A1 e A2 dois algoritmos para um mesmo problema, que
recebem como entrada um grafo. Se A1 roda em tempo O(n + m log n) e A2
roda em tempo O(n²), onde n é o número de vértices do grafo e m é o número
de arestas do grafo, podemos afirmar que:
A) a execução de A1 leva menos tempo do que a execução de A2 para todo
grafo acíclico;
B) A1 é mais eficiente do que A2 para grafos completos;
C) quando o número de vértices é suficientemente grande, A2 sempre rodará
em mais tempo do que A1;
D) quando o número de vértices é suficientemente grande e o grau mínimo do
grafo é metade do número de vértices do grafo, A2 sempre rodará em mais
tempo do que A1;
E) NRA
Resolução:
A) a execução de A1 leva menos tempo do que a execução de A2 para todo
grafo acíclico;
Todo grafo acíclico tem no máximo n-1 arestas, ou seja, m = 2, o algoritmo A1 sempre roda em menos tempo que o A2.
Porém, para um grafo trivial (n=1), temos que:
O(1 + 0*log1) = O(1²)
Dessa forma, eles performam no mesmo tempo para esse caso, o que comprova que a
afirmação é falsa.
B) A1 é mais eficiente do que A2 para grafos completos;
Em grafos completos, o número de arestas é igual a n*(n-1)/2 = (n²-n)/2. Para que a
afirmação fosse verdade, deveríamos ter: n + (n²-n)/2*log n 4. Logo, a afirmação é falsa.
D) quando o número de vértices é suficientemente grande e o grau mínimo do
grafo é metade do número de vértices do grafo, A2 sempre rodará em mais
tempo do que A1;
Como o grau mínimo do grafo é metade do número de vértices do grafo, temos:
m >= n*(n/2)/2
m >= n²/4
Considerando o limiar mais baixo de m = n²/4, para tentar fazer a sentença verdadeira,
precisaríamos que:
n + (n²/4)*log nde
células não-nulas em uma matriz de adjacências para G.
Falso.
Considerando n o número de vértices, e m o número de arestas, uma matriz de
incidências possui m linhas e n colunas. Em cada uma dessas linhas, são marcadas
as células dos vértices que se relacionam por meio de uma dada aresta. Assim, em um
grafo simples, teríamos 2 células marcadas a cada linha, totalizando 2*m células
não-nulas.
Em uma matriz de adjacências, existem n² células, e cada uma das arestas é marcada
em uma ou duas células, dependendo da aplicação. No primeiro caso, teríamos uma
célula por aresta: 1*m. Já no segundo, teríamos 2 células por aresta: 2*m.
Desse modo, o número de células marcadas na matriz de incidências deve ser maior
ou igual ao da matriz de adjacências.
D) Todo digrafo acíclico admite pelo menos duas ordenações topológicas.
Falso.
Por exemplo, o seguinte grafo só admite uma ordenação topológica:
Questão 6: Seja o digrafo D(V,E), onde:
V = {a,b,c,d,e}
E = {ab, ae, bc, bd, be, ce, dc, de}.
A) Encontre uma ordenação topológica para D.
Uma possível ordenação topológica para D, e a única existente, é: a, b, d, c, e.
B) Quantas arestas possui o menor subgrafo de D que só admite ordenações
topológicas iniciadas em a e terminadas em e?
Uma aresta, como podemos ver no subgrafo de D a seguir:
C) Quantas arestas possui o menor subgrafo gerador de D que só admite
ordenações topológicas iniciadas em a e terminadas em e?
Subgrafo gerador é aquele em que poderíamos gerar o grafo original ao adicionar as
arestas dele que faltam. Basicamente, possui todos os vértices e uma seleção de
arestas do grafo original.
O menor subgrafo gerador de D que só admite ordenações topológicas iniciadas em a
e terminadas em e, possui 4 arestas, como veremos a seguir: