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:

Ciclos e caminhos hamiltonianos
- em digrafos semicompletos
- em digrafos localmente semicompletos
- em digrafos com graus elevados
- em digrafos multipartidos semicompletos
Árvores geradoras divergentes
- árvores divergentes disjuntas
- árvore divergente de custo mínimo
Conexidade global
- digrafos fortes e decomposição em orelhas
- inversões de arcos que tornam um digrafo forte (teorema de Lucchesi-Younger)
- inserções de arcos que aumentam a conexidade (teoremas de Mader e Frank )
Orientações de grafos
- orientações versus coloração de vértices
- orientações fortes
- orientações que respeitam restrições de graus
- fluxos inteiros nenhures nulos
Fluxos submodulares
- teorema de Edmonds-Giles
- teoremas de Frank

A título de revisão de pré-requisitos, trataremos preliminarmente e rapidamente de

Fluxo em redes
- fluxo viável máximo de um vértice a outro
- b-fluxo viável
- aplicações
- caminhos internamente disjuntos (teorema de Menger)
- conexidade e arco-conexidade

Veja texto completo do Roteiro em formato PDF.