Digrafos  |  Referências  |  Dicionário

Digrafos
(roteiro de curso)

 

a directed cycle

 

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 [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 não-dirigidos 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.

Sigla da disciplina

MAC5872 (Tópicos em Teoria dos Grafos e Otimização)

Professor

Paulo Feofiloff

Quando/onde

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

Pré-requisitos

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.

 

Tópicos

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

 

Veja texto completo do Roteiro em formato PDF.

 



 

 

Outros assuntos:   Projeto de Algoritmos em C  |  Livro Algoritmos em C  |  Algorithms Design in 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  |  Teoria dos Grafos via Diestel  |  Análise de Algoritmos  |  Minicurso de Análise de Algoritmos  |  Algoritmos de Programação Linear  |  Otimização Combinatória  |  Algoritmos de Aproximação