Digrafos |
Referências |
Dicionário |
Diário Alunos | Notas |
Um
digrafo,
ou
grafo dirigido,
é um grafo com flechas nas arestas.
Digrafos são objetos mais gerais que grafos.
Num certo sentido,
digrafos são objetos mais naturais
que grafos.
[A palavra digrafo
é um neologismo
feio mas útil.
Cuidado: escrever dígrafo
, com acento,
não faz o menor sentido.]
Veja
texto do Roteiro em formato PDF
A maioria dos cursos de teoria dos grafos trata apenas de grafos não-dirigidos. Cursos que estudam digrafos são mais raros. Isso acontece, talvez, porque as propriedades de grafos são mais fáceis de apreender intuitivamente. Também porque muitos problemas fundamentais sobre digrafos são mais difíceis que os correspondentes problemas sobre grafos.
MAC5872 (Tópicos em Teoria dos Grafos e Otimização)
Paulo Feofiloff
Primeiro semestre de 2007
De 5/3/2007 a 22/6/2007
Horário:
segundas às 10 e quartas às 10
Sala: 243, bloco A
Convém que os alunos já tenham cursado alguma disciplina de teoria dos grafos e que tenham alguma noção de fluxo em redes e de análise de algoritmos.
A disciplina pretende cobrir as partes mais interessantes do livro de Bang-Jensen e Gutin. Eis uma lista de possíveis tópicos:
A título de revisão de pré-requisitos, trataremos preliminarmente e rapidamente de
Outros assuntos:
Projeto de Algoritmos em C |
Livro Algoritmos em C
|
Desenvolvimento de Algoritmos |
Estruturas de Dados |
Literate Programming & CWEB |
O que é uma prova? |
Uma Introdução Sucinta à Teoria dos Grafos |
Exercícios de Teoria dos Grafos |
Graph Theory Exercises |
Algoritmos em Grafos com Stanford GraphBase |
Algoritmos para Grafos via Sedgewick |
Curso Avançado de Teoria dos Grafos |
Análise de Algoritmos |
Minicurso de Análise de Algoritmos |
Algoritmos de Programação Linear |
Otimização Combinatória |
Algoritmos de Aproximação