DC-UFRPE/Bacharelado em Ciência da Computação/Teoria dos grafos
Programa da Disciplina
editarNome: | 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
editarNoçõ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
editarGeral:
editar• 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:
editar• 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
editar- História da Teoria dos Grafos
- Definição formal de grafos não-dirigidos e definições estruturais básicas: graus, vizinhança, cortes, conjuntos independentes, cliques, coberturas
- Isomorfismo de grafos, conexidade, árvores
- Coloração de vértices: Teorema de Brooks
- Emparelhamentos: Teorema de Hall, Teorema de König, Teorema de Tutte
- Coloração de arestas: Teorema de Vizing
- Circuitos hamiltonianos: Teorema de Dirac, Teorema de Ore
- Tópicos de Teoria de Ramsey
- Planaridade: Teorema de Kuratowski, Teorema de Euler
- Fluxos em grafos
Métodos Didáticos de Ensino
editarOs 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
editarBásica
editar- 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/
- 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.
- DIESTEL, Reinhard. Graph theory. New York: Springer-Verlag, 2000. Disponível com autorização do autor em https://diestel-graph-theory.com/
Complementar
editar- 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/