MAC328 - Algoritmos em grafos

BCC - 1o. Semestre de 2004

Sinopse das aulas - Março

Aula 1 Terça 2/3/2004	Apresentação da disciplina Bibliogtrafia Definições básicas Um exemplo de problema computacional envolvendo grafos: o problema do isomorfismo de grafos Exercícios 1 e 2
Aula 2 Sexta 5/3/2004	Definições básicas, continuação: passeios, trilhas, caminhos, circuitos, etc. Árvores e forestas. Caracterizações de árvores Exercício 4
Aula 3 Terça 9/3/2004	Entrega dos Exercícios 1 e 2 Caracterizações de árvores, continuação A fórmula de Cayley. A prova bijetiva de André Joyal da fórmula da Cayley Exercício 5
Aula 4 Sexta 12/3/2004	Entrega do Exercício 4 Definições básicas, continuação: cliques/grafos completos, conjuntos independentes/estáveis. A noção de grafos densos e esparsos. Representação de grafos: vetor de arestas, matrizes de adjacência, e listas de adjacência Reflexo da representação adotada no espaço e no tempo de resolução de problemas computacionais ("o vértice `v` é isolado?") Exercício 6
Aula 5 Terça 16/3/2004	Entrega do Exercício 5 O tipo abstrato `Graph` e a interface `GRAPH.h` Um cliente simples: prog17.2.c Implementação com matrizes de adjacência: prog17.3.c Implementação com listas de adjacência: prog17.6.c Leitura de grafos: prog17.9.c. Um cliente simples: prog17.2.b.c. Uma implementação da tabela de símbolos com TST (ternary search tries): ST.h, prog17.10.c Transparências Exercício 7
Aula 6 Sexta 19/3/2004	Entrega do Exercício 6 Busca em profundidade: prog18.1.c (matriz de adjacência); prog18.2.c (listas de adjacência). Um cliente: prog18.3.driver.c Como determinar rapidamente se `v` e `w` estão no mesmo componente conexo? Preprocessamento: prog18.4.c Transparências Exercício 8
Aula 7 Terça 23/3/2004	Entrega do Exercício 7 Busca em profundidade, continuação. Os programas neste diretório podem ser usados para gerar exemplos de buscas em profundidade em que todas as arestas (ou ponteiros) são classificadas nos 4 tipos discutidos (tipo árvore, tipo pai, tipo ascendente, tipo descendente), como neste exemplo Transparências Os grafos nas transparências dessa aula desenhados com o MetaPost, uma excelente linguagem gráfica baseada no METAFONT, de Knuth. Exercício 9
Aula 8 Sexta 26/3/2004	Entrega do Exercício 8 Aresta-conexidade: caracterização de pontes baseada na busca em profundidade. Determinação das pontes: prog18.7.c, prog18.7.out. Transparências Exercício 10
Aula 9 Terça 30/3/2004	Entrega do Exercício 9 2-conexidade: a relação de equivalência "ser igual ou estar contido em um mesmo circuito" nas arestas de um grafo; caracterização de grafos 2-conexos; existência de dois caminhos internamente disjuntos entre quaisquer dois vértices em grafos 2-conexos; blocos e decomposição em blocos de um grafo. Exercício 11

Calendário


     March 2004               April 2004                May 2004      
Su Mo Tu We Th Fr Sa     Su Mo Tu We Th Fr Sa     Su Mo Tu We Th Fr Sa 
    1  2  3  4  5  6                  1  2  3                        1 
 7  8  9 10 11 12 13      4  5  6  7  8  9 10      2  3  4  5  6  7  8 
14 15 16 17 18 19 20     11 12 13 14 15 16 17      9 10 11 12 13 14 15 
21 22 23 24 25 26 27     18 19 20 21 22 23 24     16 17 18 19 20 21 22 
28 29 30 31              25 26 27 28 29 30        23 24 25 26 27 28 29 
                                                  30 31

     June 2004        
Su Mo Tu We Th Fr Sa  
       1  2  3  4  5  
 6  7  8  9 10 11 12  
13 14 15 16 17 18 19  
20 21 22 23 24 25 26  
27 28 29 30

Sinopse das aulas de MAC328 (BCC - 1o. Semestre de 2004).
Página principal de MAC328 (BCC - 1o. Semestre de 2004).

Y. Kohayakawa <yoshi@ime.usp.br>

Last modified: Mon May 31 20:37:22 BRT 2004