Na janela de impressão, escolha “Salvar como PDF” para guardar uma cópia no seu dispositivo.
1Fórmulas e métodos
Teoria dos grafos
Lema do aperto de mãos
Σ deg(v) = 2|E|
Grafos completos
|E(Kn)| = n(n − 1)/2, |E(Km,n)| = m·n
Grafo regular
|E| = n·k/2
Árvore e floresta
|E| = n − 1, |E| = n − c
Folhas de uma árvore
L = 2 + Σ (deg(v) − 2) over deg(v) ≥ 3
Euler
circuito: todos os graus pares; caminho: exatamente 2 graus ímpares
Circuitos hamiltonianos em Kn
(n − 1)!/2
Atualização de Dijkstra
d(v) = min(d(v), d(u) + w(u, v))
Passeios de comprimento L
(Mᴸ)ij
Método
Anote o grau de cada vértice; a soma dos graus é igual ao dobro do número de arestas.
Em questões de Euler, verifique se o grafo é conexo e conte os vértices de grau ímpar.
Para árvores, use n − 1 arestas e o lema do aperto de mãos.
Em Dijkstra, mantenha uma tabela de distâncias provisórias e fixe a cada rodada o vértice não fixado de menor distância.
Para uma árvore geradora mínima, ordene as arestas por peso e pule toda aresta que feche um ciclo (Kruskal), ou faça crescer uma árvore a partir de um vértice inicial (Prim).
2Exercícios
1.Algoritmos e complexidadeMédia
Um quicksort usa sempre o primeiro elemento como pivô. Com qual entrada ele apresenta o comportamento de pior caso?
AUm array de tamanho 2
BUm array em ordem aleatória
CUm array que já está ordenado
DUm array com todos os elementos diferentes
2.Algoritmos e complexidadeDifícil
O problema da mochila 0/1 resolvido com programação dinâmica leva tempo O(nW). Por que isso é chamado de pseudopolinomial?
APorque n é sempre pequeno
BPorque o algoritmo é aleatorizado e seu tempo de execução varia a cada entrada
CPorque só funciona para W = 0
DW é um número, então o tempo é exponencial no número de bits usados para escrever W
3.Estruturas de dadosMédia
As chaves 50, 30, 70, 20, 40 são inseridas nessa ordem em uma árvore binária de busca vazia. Qual é o filho esquerdo de 30?
A70
B20
C50
D40
4.Estruturas de dadosDifícil
Na BST com raiz 50, subárvore esquerda 30 (filhos 20, 40) e subárvore direita 70 (filhos 60, 80), a raiz é removida usando o sucessor em ordem. Qual chave se torna a nova raiz?
A80
B40
C70
D60
5.Teoria dos grafosMédia
O grafo conexo tem um circuito euleriano, um caminho euleriano que não é circuito, ou nenhum dos dois? Clique na sua resposta.
|V| = 7|E| = 11
1Circuito euleriano
2Caminho euleriano, sem circuito
3nenhuma das duas
6.Teoria dos grafosDifícil
O algoritmo de Kruskal constrói uma árvore geradora mínima. Clique na aresta que ele acrescenta como aresta de número 3; as arestas descartadas não contam.
k = 3
1aresta AB
2aresta AC
3aresta BC
4aresta BD
5aresta CE
6aresta DE
7aresta BE
3Soluções
1.Algoritmos e complexidade
Resposta: C · Um array que já está ordenado
Porque é esta a resposta
Com entrada ordenada, o pivô é sempre o mínimo, então um lado fica vazio e o outro tem n − 1 elementos, o que dá O(n²).
Resposta
C · Um array que já está ordenado
2.Algoritmos e complexidade
Resposta: D · W é um número, então o tempo é exponencial no número de bits usados para escrever W
Porque é esta a resposta
O tempo de execução é polinomial no valor de W, mas exponencial no seu comprimento (log W bits); a mochila 0/1 é NP-completa.
Resposta
D · W é um número, então o tempo é exponencial no número de bits usados para escrever W
3.Estruturas de dados
Resposta: B · 20
Porque é esta a resposta
20 é menor que 50 e menor que 30, então se torna o filho esquerdo de 30; 40 se torna o filho direito.
Resposta
B · 20
4.Estruturas de dados
Resposta: D · 60
Porque é esta a resposta
O nó mais à esquerda da subárvore direita é 60, então 60 substitui 50 e sua posição antiga é removida; usar o predecessor daria 40.
Resposta
D · 60
5.Teoria dos grafos
Resposta: Caminho euleriano, sem circuito
Euler, Hamilton e árvores: um grafo conexo tem um circuito euleriano (cada aresta uma vez, de volta ao início) quando todo vértice tem grau par, e um caminho euleriano que não é circuito quando exatamente dois vértices têm grau ímpar; o caminho vai então de um vértice ímpar ao outro. Um circuito hamiltoniano visita cada vértice uma vez; Kn tem (n − 1)!/2 deles. Uma árvore com n vértices tem n − 1 arestas, e um grafo conexo com m arestas mantém uma árvore geradora depois de remover m − n + 1 arestas.
O caminho euleriano começa em um vértice ímpar e termina no outro.
6.Teoria dos grafos
Resposta: aresta DE
Caminhos mínimos e árvores geradoras: o algoritmo de Dijkstra fixa um vértice por rodada: o vértice não fixado com a menor distância provisória. Sua distância torna-se definitiva, e cada vizinho v recebe d(v) = min(d(v), d(u) + w(u, v)). O algoritmo de Kruskal constrói uma árvore geradora mínima tomando as arestas da mais leve para a mais pesada e descartando qualquer aresta que feche um ciclo; o algoritmo de Prim faz crescer uma árvore a partir de um vértice inicial acrescentando sempre a aresta mais leve que sai dela. Uma árvore geradora de n vértices tem n − 1 arestas.