Introdução à Teoria dos Grafos
Mestrado em Ciência da Computação, ano 2006

Objetivos

Apesar de a matemática e a ciência da computação virem se desenvolvendo separadamente como áreas distintas, a primeira permanece como base para a segunda em diversos aspectos. Disciplinas que fazem com que os estudantes de ciência da computação conheçam os fundamentos da área são inseridas nos currículos dos cursos de graduação e sempre incluem teoria dos grafos e suas aplicações.

Como grafos naturalmente são modelos para uma variedade de situações e problemas reais, a teoria dos grafos tem um papel importante dentro da ciência da computação.

A teoria dos grafos pode ser vista através de dois enfoques: um enfoque estrutural e outro algorítimico. Neste curso vamos dar ênfase na visão estrutural da teoria, onde perguntamos sobre que tipos de grafos têm certas propriedades, quais são eles, como são, etc.

Pré-requisitos

Matemática Discreta e Álgebra, Algoritmos e Estruturas de Dados I são os pré-requisitos da disciplina de Introdução à Teoria dos Grafos. Noções de programação também são necessárias.

Tópicos

• Grafos
• Vizinhanças e graus de vértices
• Isomorfismo
• Síntese de grafos a partir dos graus
• Caminhos e circuitos
• Subgrafos
• Cortes
• Grafos conexos
• Componentes
• Grafos bipartidos
• Conjuntos estáveis
• Cliques
• Coberturas por vértices
• Coloração de vértices
• Emparelhamentos
• Emparelhamentos em grafos bipartidos
• Emparelhamentos em grafos arbitrários
• Coloração de arestas
• Circuitos hamiltonianos
• Ciclos eulerianos
• Florestas e árvores
• Subárvores
• Distâncias e caminhos mínimos
• Mapas planos e grafos planares