MAC5770
Introdução à Teoria dos Grafos

Veja edição 2005

MAC5770 tem por objetivo introduzir o estudante do 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.  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 existencial (por exemplo, este grafo tem um circuito hamiltoniano?) e estrutural (que tipos de grafos têm circuito hamiltoniano?).

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, o conceito de algoritmo. Alguma experiência de programação em C também é útil. Principais tópicos Isomorfismo Caminhos e circuitos Cortes Grafos conexos 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

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