Digrafos  |  Referências  |  Dicionário  |  Diário
Alunos  |  Notas

 

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 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

 

 


Pós-Graduação em Ciência da Computação no IME-USP
FênixWeb  |  Janus

http://www.ime.usp.br/~pf/digraphs/
Last modified: Wed Sep 27 13:10:36 BRT 2017
Paulo Feofiloff
Departamento de Ciência da Computação
Instituto de Matemática e Estatística
Universidade de São Paulo

Valid HTML 4.0!     Valid CSS!

Outros assuntos:   Análise de Algoritmos  |  Minicurso de Análise de Algoritmos  |  Algoritmos de Aproximação  |  Projeto de Algoritmos em C  |  Estruturas de Dados  |  Uma Introdução Sucinta à Teoria dos Grafos  |  Exercícios de Teoria dos Grafos  |  Fluxo em Redes  |  Algoritmos em Grafos com Stanford GraphBase  |  Algoritmos para Grafos via Sedgewick  |  Algoritmos de Programação Linear  |  Literate Programming & CWEB  |  O que é uma prova?  |  Opiniões e notícias