MAC5770
Introdução à Teoria dos Grafos

MAC5770 tem por objetivo introduzir o estudante de pós-graduação em Ciência da Computação aos problemas, aos métodos, e à linguagem da teoria dos grafos.  Esta disciplina é útil em todas as áreas da computação. Ela é particularmente importante nas áreas de teoria da computação e otimização combinatória. MAC5770 é vulgarmente conhecida como "Grafinhos". A disciplina MAC5771, mais avançada, é conhecida como "Grafões". Teoria dos grafos A Teoria dos Grafos não é uma teoria:  é uma  coleção de problemas computacionais.  Todos esses problemas são formulados sobre um objeto combinatório conhecido como  grafo.  Os problemas tornaram-se célebres porque ocorrem em diversas áreas da computação, da engenharia, e em muitas aplicações industriais. A preocupação central da teoria dos grafos é a busca por algoritmos eficientes que resolvam problemas sobre grafos.  Mas nesta edição de MAC5770 nossa atitude será menos algorítmica (por exemplo, como encontrar um circuito hamiltoniano num grafo?) e mais estrutural (por exemplo, que tipos de grafos têm circuito hamiltoniano?).   [Se você está interessado na implementação de algoritmos para grafos, veja minhas notas sobre análise de algoritmos e algoritmos em grafos.]

Principais tópicos Isomorfismo Caminhos e circuitos Cortes Grafos conexos Grafos bipartidos Florestas e árvores Caminhos mínimos Subárvores geradoras de um grafo Ciclos eulerianos Circuitos hamiltonianos Conjuntos estáveis Emparelhamentos Coloração de arestas Coloração de vértices Planaridade Se houver tempo, trataremos também de grafos biconexos, grafos aleatórios, grafos orientados. Pré-requisitos MAC5770 não tem pré-requisitos oficiais. Convém entretanto que o aluno tenha familiaridade com a notação da teoria dos conjuntos, os conceitos de indução e recursão, o conceito de algoritmo. Alguma experiência de programação em C também é útil.

Aulas Eu não gostaria que as aulas fossem meramente expositivas. Eu prefiro que elas sejam um laboratório de resolução de problemas. Para isso, preparei uma coleção de exercícios em formato PDF.   Evite imprimir esse material em papel, pois ele será alterado e corrigido freqüentemente. É melhor ler os exercícios na tela do monitor. Use o Acrobat Reader para tirar proveito dos hyperlinks.

Tarefas Veja a página de tarefas