Digrafos
(roteiro de curso)

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.

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