[UP: INTRODUÇÃO À TEORIA DOS GRAFOS - MAC5770]

Programa

Segundo o programa oficial, o objetivo de MAC5770 é  introduzir o estudante aos problemas, aos métodos e à linguagem da teoria dos grafos.  Ainda segundo o programa oficial, o conteúdo de MAC5770 é o seguinte:

Representação eficiente de grafos. Algoritmos eficientes.
Caminhos e componentes conexos.
Caminho mínimo entre dois vértices dados.
Árvores e florestas; subárvore geradora de custo mínimo de um grafo.
Emparelhamentos máximos em grafos bipartidos (teorema de Hall, teorema de König).
Coloração de arestas. Coloração de vértices.
Grafos eulerianos. Grafos hamiltonianos.
Seqüências gráficas; teorema de Gallai.
Grafos orientados: componentes fortes; grafos acíclicos.

MAC5770 é vulgarmente conhecida como "Grafinhos". A disciplina seguinte, MAC5771, é conhecida como "Grafões".

---

Livros

Como referência para os conceitos e fatos básicos da teoria dos grafos, usaremos o livro

• J.A. Bondy, U.S.R. Murty,  Graph Theory with Applications,
  Macmillan, London, 1976.

  Clássico. Antigo, mas ainda muito bom. Murty visita o Brasil (especialmente a UNICAMP) com regularidade.

• Robin J. Wilson,  Introduction to Graph Theory,  4th.ed.,  Addison-Wesley, 1997.

  Leve e suave.

• B. Bollobás,  Graph Theory: an Introductory Course,
  Springer-Verlag, 1979.

  Clássico. Tem caráter mais matemático.

• L. Lovász,  Combinatorial Problems and Exercises,  2nd. ed.,
  North-Holland, 1993.

  Aprenda teoria dos grafos fazendo exercícos!  A segunda parte do livro traz as soluções de muitos dos exercícos.

• T.H. Cormen, C.E. Leiserson, R.L. Rivest,  Introduction to Algorithms,
  MIT Press & McGraw-Hill, 1992.

  Somente as seções 5.4 e 5.5 e os capítulos 23 a 27.

Há uma grande quantidade de outros livros sobre a teoria dos grafos nas bibliotecas e livrarias. Escolha um!

---

Horário, critério de avaliação, etc.

A disciplina tem carga horária semanal de 4 horas de aulas (aproximadamente 30 horas de aulas no semestre) e dá direito a 8 créditos.

Horário: 

Terças-feiras das 8 às 10 e quintas-feiras da 10 às 12. 

 

Local: 

Sala 259 do bloco A, prédio do IME.

 

Provas: 

As provas serão realizadas no horário das aulas, usualmente às quintas-feiras, e poderão se estender um pouco além de 12h00m. Veja datas no registro de aulas e provas.

 

Exercícios: 

Faremos alguns exercícos/projetos.  Alguns poderão acontecer durante as aulas. 

 

Publicação das notas e conceitos: 

Minha avaliação dos alunos será publicada na página  www.ime.usp.br/~pf/mac5770-2001/marks/notas.html.

 

Critério de avaliação: 

O conceito final (A, B, C, R) será baseado em uma média ponderada dos conceitos e notas obtidas nas provas e nos exercícios/projetos.  As provas terão peso de 70% e os exercícios terão peso de 30%.  A média de exercícios será dada por  10×X/S ,  onde X é o total de pontos acumulado pelo aluno e S é um pouco menos que a soma dos valores de todas as listas de exercícios.

 

---

Mailing list

Há uma mailing list para troca de mensagens, avisos e informações entre os envolvidos com MAC5770 (alunos, professores, demais interessados).  Qualquer mensagem para o endereço

xxx

será automaticamente redistribuída para todos os assinantes da lista.  A lista se destina principalmente à troca de idéias entre os alunos. Eu pretendo participar, mas meu papel será secundário.

Procure mandar mensagens sem qualquer formatação (sem mime, sem html, em texto puro).  Ao mandar uma mensagem, não deixe de dizer qual o assunto (campo "Subject").  Só use reply (resposta) a partir de uma mensagem se você estiver tratando do mesmo assunto que a mensagem em questão; caso contrário, componha uma nova mensagem.   A propósito, veja a página de netiqueta de Maria Alice Soares de Castro.

Assinatura

 

Todos os alunos de MAC5770 devem ser assinantes da mailing list. Candidatos a alunos e demais intressados também são bem-vindos. O procedimento de assinatura é simples: basta mandar uma mensagem vazia, sem subject, para

xxx

Você receberá um pedido de confirmação por e-mail; basta dar um reply.  Para pedir ajuda sobre o funcionamento da lista (por exemplo, instruções para cancelar a inscrição), mande mensagem vazia para  xxx.

 

Arquivo da lista

 

As mensagens enviadas para a lista serão arquivadas de maneira organizada. Você pode examinar as mensagens arquivadas  por assunto  ou  em ordem cronológica inversa.