Árvores geradoras mínimas

Questões-guia:

1. O que é uma árvore geradora mínima?  O que pode ser aproveitado da teoria sobre árvores geradoras mínimas se estivermos procurando uma árvore geradora máxima?
2. Como funciona o algoritmo genérico?  Como encontrar uma aresta segura?
3. Para que serve a estrutura de union-find?  Como funciona?
4. Como funciona o algoritmo de Kruskal?  Qual é sua complexidade?  Dá para pará-lo antes?  Isto modifica sua complexidade de pior caso?  Você pararia antes?
5. Para que servem heaps binários?  Como funcionam?  Que outros algoritmos os usam?
6. Como funciona o algoritmo de Prim?  Qual é sua complexidade com heaps binários?  Por que não aparece uma chamada de DECREASE-KEY nele?
7. O que poderia ser usado em lugar de heaps binários no algoritmo de Prim?  Como isto afetaria a complexidade?  Esta solução afetaria outros algoritmos, p.ex., os citados na questão 5?

Exercícios:

1. Ache uma árvore geradora mínima com o LEMON no exemplo usado no Cormen na seção 23.2.  Dica: use a função kruskal.
2. Exercício 23.1-11 do Cormen.
3. Exercício 23.2-4 do Cormen, só a primeira pergunta.
4. Exercício 23.2-5 do Cormen, só a primeira pergunta.

Emparelhamentos bipartidos

Questões-guia:

1. Quantos emparelhamentos perfeitos existem em K_n,n?
2. Para cada inteiro n ≥ 3, mostre um grafo com n vértices onde existe um emparelhanto maximal que não é máximo.  Mostre um caminho aumentante para estes emparelhamentos.
3. Qual a importância algorítmica do teorema de Hall?
4. Como coberturas por vértices podem nos ajudar a garantir que um emparelhamento é máximo?
5. Nos números α(G), α'(G), β(G), β'(G), o que significa a linha (')?  E quais destes números somam n(G)?  Em que condições?
6. O efeito do Algoritmo 3.2.1 pode ser conseguido com uma BFS ou DFS modificada?  Qual seria a complexidade deste algoritmo modificado?
7. Por que o problema de emparelhamento de peso máximo em grafos bipartidos ponderados pode ser reduzido a bipartidos completos?  E, ainda por cima, com partes do mesmo tamanho?
8. Como se generaliza a noção de cobertura por vértices em grafos bipartidos ponderados?
9. O Algoritmo Húngaro p/ resolver o problema de emparelhamento de peso máximo num grafo bipartido utiliza qual outro algoritmo como subrotina fundamental?

Exercícios:

Para entender o Algoritmo Húngaro, um bom exercício é ver as coisas acontecendo numa planilha de cálculo.  Pegue um exemplo do livro e coloque numa planilha da seguinte forma.

1. Separe uma região n × n da planilha para colocar a entrada.
2. A seguir, ao lado ou embaixo da entrada, escolha outra região n × n da planilha para codificar um emparelhamento.  Esta região terá apenas zeros e uns.
3. Numa outra região do mesmo tamanho, faça a multiplicação da região entrada pela do emparelhamento, elemento a elemento, obtendo os pesos das arestas do emparelhamento.  Faça uma célula conter o peso total deste emparelhamento.
4. Finalmente, numa outra região do mesmo tamanho, compute a matrix de excessos.  Nesta região é interessante ladear as bordas superior e esquerda com uma cobertura.  Faça uma célula conter o peso total desta cobertura.
5. Após este arranjo, o algoritmo pode ser "executado" mexendo apenas no emparelhamento e na cobertura, até que seus pesos fiquem iguais.

DFS, ordenação topológica, conexão forte

Questões-guia:

1. Qual a explicação que Cormen dá para a BFS ser single-source enquanto que a DFS é multiple-source?  Você concorda com ela?
2. Por que Cormen exemplifica BFS em grafos não orientados, e DFS em grafos orientados?  Em LEMON, dá pra rodar BFS e DFS em quais tipos de grafos?
3. Quais são as saídas mais importantes de uma DFS?
4. Por que o código da DFS é dividido em duas funções, enquanto que o da BFS fica em uma só função?
5. O que é um DAG?
6. O que é ordenação topológica e como ela pode ser resolvida por DFS?
7. O que são componentes fortemente conexas?  Como diferem das componentes conexas que vimos anteriormente?
8. Se G é um grafo orientado, o que é G^SCC?  Que propriedade interessante tem G^SCC?
9. Como obter uma ordenação topológica em G^SCC a partir de uma DFS em G?
10. Se G é um grafo orientado, o que é o grafo G^T?  Como se relacionam G^SCC e (G^T)^SCC?

Exercícios:

1. Rode uma DFS da biblioteca LEMON no grafo usado como exemplo na Figura 22.4 do Cormen.  Quantas linhas deu seu código?  Deu a mesma busca do livro?
2. Resolva o Exercício 22.4-1 com a biblioteca LEMON.  Dica: use a class DfsVisit em lugar da Dfs normal.
3. Implemente o algoritmo para componentes fortemente conexas da Seção 22.5 do Cormen usando LEMON.  Teste no grafo da Figura 22.9.  Dica: além da DfsVisit, use o adaptador de grafos que calcula G^T e controle fino de DFS com os métodos init, addSource e start.

BFS, distâncias

Questões-guia:

1. Em grafos, temos em geral dois parâmetros que medem o tamanho da entrada: V e E.  O que significa formalmente f(V,E) = O(g(V,E))?
2. Qual a diferença entre as definições de grafos em West e em Cormen?  LEMON é mais próximo de qual dos dois?
3. Quais as vantagens de desvantagens da representação por listas de adjacência, em relação a matrizes de adjacência?
4. Quais são as saídas mais importantes de uma BFS?
5. Como seria a tradução do algoritmo BFS(G,v) do Cormen (página 595) para LEMON?  O que você usaria para ENQUEUE e DEQUEUE?
6. O que é análise agregada?  Qual a complexidade de BFS em termos de V e E?
7. A árvore BFS de um grafo é única?  Se não for, dê exemplos.

Exercícios:

1. Modifique BFS para descobrir se um grafo é bipartido e, se não for, exibir um ciclo ímpar.
2. Como seria a adaptação de BFS para grafos com arestas múltiplas e laços?
3. Se fosse para imprimir um caminho mais curto de v para s, como você escreveria o algoritmo PRINT-PATH (página 601)?

Componentes conexas, bipartidos, eulerianos

Questões-guia:

1. Qual a diferença entre indução fraca e indução forte?
2. Qual a diferença entre passeio (walk), trilha (trail) e caminho (path)?  Como é o uso destes termos no Cormen?
3. Todo passeio entre u e v contém um caminho de u a v.  Contém também uma trilha? As trilhas de u a v sempre contém caminhos de u a v?
4. O que é uma componente conexa de um grafo?  Quantas componentes conexas tem um grafo conexo?
5. O que é vértice de corte?  E aresta de corte?  Uma aresta paralela pode ser de corte?
6. Um passeio fechado ímpar sempre contém um ciclo ímpar.  Um passeio fechado par sempre contém um ciclo par?
7. Qual a diferença entre união de grafos e decomposição de grafos?
8. Que propriedades deve ter um grafo para podermos desenhá-lo (vértices e arestas) sem tirar o lápis do papel e sem repetir traços?  É o mesmo que ser euleriano?
9. Para um grafo qualquer, qual o número mínimo de vezes que precisamos tirar o lápis do papel para desenhá-lo, sem repetir traços?  Expresse sua resposta em termos de parâmetros do grafo (número de vértices, graus, número de componentes conexas, etc.)
10. Qual a diferença entre máximo e maximal?  Esta diferença se aplica a números inteiros?

Exercícios:

1. Exercício 1.2.1 do West.
2. Exercício 1.2.2 do West.
3. Diagrama JSP para construir uma trilha de Euler num grafo.  Você tem duas opções aqui, uma oriunda da demostração do Teorema 1.2.26 e outra oriunda da demostração alternativa, dada no item 1.2.32, no final da página 29.  Para ajudar, veja a seguir a "primeira linha" de cada um destes diagramas:

Páginas 27 e 27:

Páginas 29 e 30:

Grafos, matrizes, isomorfismo

Questões-guia:

1. O que é um grafo?  E um grafo simples?
2. O complemento de um grafo bipartido será sempre bipartido?
3. O que se pode dizer do número cromático de um grafo k-partite?
4. Um subgrafo de um grafo conexo será sempre conexo?  Mesma questão para um grafo desconexo.
5. Como obter a matrix de adjacência A(G) a partir da matriz de incidência M(G) de um grafo sem laços?  E se o grafo tiver laços?
6. Como se relacionam as matrizes de adjacência de dois grafos isomorfos?  E as de incidência?
7. O que é um n-ciclo?  E um grafo completo?  E um biclique?  Quais são as notações para estes grafos?
8. Desenhe os seguintes grafos: triângulo, garra, pata, pipa, casa, touro, gravata-borboleta, dardo.
9. Qual a cintura do grafo de Petersen?  E de seu complemento?
10. Quais dos grafos em (8) são vértice-transitivos?  Quais tem maior número de automorfismos?

Exercícios:

1. Exercício 1.1.11 do West.
2. Exercício 1.1.15 do West.
3. Exercício 1.1.27 do West.

Lab: Apresentação

Exibir apresentação sobre LEMON.

Note que LEMON já traz vários algoritmos relacionados aos nossos tópicos de laboratório.

Apresentar ferramenta para JSP.

Ver se LEMON está instalado nos computadores do laboratório.

Praticar com alguns exercícios simples.

Revisão MC458

Questões-guia:

1. O que é um algoritmo?
2. O que é um problema computacional?
3. O que é um invariante de malha (ou de laço)? [em inglês: loop invariant]
4. Qual o modelo de computação usado no Cormen?
5. O que é o tamanho da entrada de um algoritmo?
6. Qual a diferença entre análise de caso médio e análise de pior caso?
7. O que é e para que serve uma árvore de recursão?
8. O que significa f(n) = O(g(n))?
9. O que diz e para que serve o Teorema Mestre?

Exercícios:

1. Faça o diagrama JSP para um dos seguintes algoritmos: insertion sort, merge sort, selection sort.
2. No exercício C3-3a, escolha uma linha ou uma coluna e faça o exercício só para estas funções.
3. No exercício C4-1, escolha uma das recorrências (a-g) e resolva.