DC-UFRPE/Bacharelado em Ciência da Computação/Teoria dos grafos

Programa da Disciplina

Nome:	Teoria dos Grafos
Código:	06232
Departamento:	Departamento de Computação (DC)
Área:
Carga-horária total:	60 horas
Créditos:	4
Pré-requisitos:

Ementa

Noções básicas: grafos orientados, não-orientados, bipartidos. Percursos em grafos. Casamentos. Subgrafos, hipergrafos, matróides e cliques. Árvores e árvores geradoras. Conectividade. Problemas de caminhos. Grafos planares. Grafos sem circuitos. Redes. Fluxos em redes.

Objetivos

Geral:

• Prover um primeiro contato com a Teoria dos Grafos, de um ponto de vista combinatório, apresentando o objeto formal “grafo” (não dirigido), as principais definições e propriedades estruturais desse objeto, e sobrevoar um recorte dos tópicos e resultados clássicos dessa teoria.

Específicos:

• Apresentar o conceito formal de grafo, uma nomenclatura básica consagrada na Teoria dos Grafos, bem como as definições e propriedades de estruturas fundamentais como conjuntos independentes, coberturas, cortes, cliques.

• Apresentar um conjunto selecionado de problemas e resultados da Teoria dos Grafos, de teoremas clássicos, oriundos de alguns tópicos fundamentais: colorações, emparelhamentos, planaridade, trilhas e circuitos, propriedades extremais, fluxos em grafos.

• Ganhar familiaridade com demonstrações formais de enunciados envolvendo grafos.

• Ganhar familiaridade com a manipulação de grafos em um pacote matemático.

Conteúdo Programático

1. História da Teoria dos Grafos
2. Definição formal de grafos não-dirigidos e definições estruturais básicas: graus, vizinhança, cortes, conjuntos independentes, cliques, coberturas
3. Isomorfismo de grafos, conexidade, árvores
4. Coloração de vértices: Teorema de Brooks
5. Emparelhamentos: Teorema de Hall, Teorema de König, Teorema de Tutte
6. Coloração de arestas: Teorema de Vizing
7. Circuitos hamiltonianos: Teorema de Dirac, Teorema de Ore
8. Tópicos de Teoria de Ramsey
9. Planaridade: Teorema de Kuratowski, Teorema de Euler
10. Fluxos em grafos

Métodos Didáticos de Ensino

Os desafios didáticos oriundos da apresentação de um conteúdo matemático, formal, em regime remoto, serão enfrentados através da realização semanal de aulas síncronas na plataforma Google Meet com o uso de ferramentas abertas para desenho, geração e manipulação de grafos. Uma recurso estará no centro desse esforço: a ferramenta SageMath (https://www.sagemath.org/), que é um pacote de computação matemática baseado na linguagem Python, de código aberto, contendo uma vasta coleção de bibliotecas, abrangendo diversas áreas da Matemática, em especial a Teoria dos Grafos. O SageMath será utilizado como andaime (no sentido de Vygotsky) não somente para promover a compreensão das definições apresentadas, mas também para facilitar a internalização de conhecimento abstrato elaborado, especialmente as demonstrações de teoremas selecionados. Cadernos Jupyter com roteiros escritos em SageMath e LaTeX servirão como documentos-guia tanto para a exposição de conceitos, como para o direcionamento do aluno à solução autônoma de um problema. Os alunos serão levados a praticar com essa ferramenta e também em lápis e papel resolvendo semanalmente problemas de Teoria dos Grafos.

Bibliografia

Básica

1. FEOFILOFF, Paulo; KOHAYAKAWA, Yoshiharu; WAKABAYASHI, Yoshiko. Uma introdução sucinta à teoria dos grafos. II Bienal da Sociedade Brasileira de Matemática, 2011. Disponível com autorização dos autores em https://www.ime.usp.br/~pf/teoriadosgrafos/
2. BONDY, John Adrian; MURTY, U. S. R. Graph Theory with Applications. Amsterdã: North-Holland, 1976. Disponível com autorização dos autores em https://www.freetechbooks.com/graph-theory-with-applications-t559.html.
3. DIESTEL, Reinhard. Graph theory. New York: Springer-Verlag, 2000. Disponível com autorização do autor em https://diestel-graph-theory.com/

Complementar

1. FEOFILOFF, Paulo. Exercícios de teoria dos grafos. Manuscrito. Disponível com autorização do autor em https://www.ime.usp.br/~pf/grafos-exercicios/