MAE478, Teoria dos Grafos

2023/2, Engenharia Matemática, Bacharelado em Matemática e Bacharelado em Matemática Aplicada
Professora Márcia R. Cerioli, Instituto de Matemática - UFRJ

Objetivos:

Conhecer a parte clássica da teoria dos grafos, com os seus resultados principais e mais conhecidos.

Programa:

  1. Conceitos, definições e notações básicas de grafos
  2. Teorema de Euler - grafos eulerianos
  3. Conectividade (cortes de vértices e de arestas)
  4. Teoremas de caracterização de árvores
  5. Hamiltonianos: Condição necessária, Teorema de Ore e Teorema de Dirac
  6. Emparelhamentos: Teorema de Berge
  7. Emparelhamentos em grafos bipartidos: Teorema de Konig, Teorema de Hall
  8. Conjuntos Independentes e Cliques: Teoria de Ramsey
  9. Coloração de vértices: Teorema de Brooks, algoritmo guloso e suas consequências
  10. Coloração de arestas: Teorema de Vizing
  11. Grafos planares: número limitado de arestas, Teorema de Kuratowsky
  12. Coloração de grafos planares e periplanares

Ementa (formal, do SIGA):

Introdução: Grafos e sub-grafos, Isomorfismos, Matrizes de Adjacência e Incidência, Caminhos e Ciclos. Árvores: Caracterização de árvores, Cortes de Arestas, Cortes de Vértices. Conectividade: Conectividade de vértices e Arestas, Blocos. Passeios de Euler e Ciclos de Hamilton. Emparelhamentos: Caracterização de Emparelhamentos Máximos, Emparelhamentos e Coberturas, Emparelhamentos Perfeitos. Coloração de Arestas: Índice Cromático e Teorema de Vizing. Conjuntos Independentes e Cliques, Teoria de Ramsey. Coloração de Vértices: Número Cromático, teorema de Brooks, Conjectura de Hajos, Polinômios Cromáticos. Grafos Planares: Grafos Planos, Grafos Duais, Pontes, Teorema de Kuratowkski, Teorema das 5 Cores. Grafos Direcionados: Caminhos e Ciclos Direcionados, Facho e Redução Transitivas, Conectividade de Dígrafos.

Pré-requisitos:

Alguma maturidade em técnicas de provas de teoremas. Em geral, a partir do terceiro ou quarto período, tendo obtido aprovação em boa parte das disciplinas do primeiro ano.

Informações importantes:

Esta é uma das Disciplinas Optativas (Escolha Condicionada) da grade do curso de Engenharia Matemática e do curso de Matemática Aplicada, ênfase em Computação Científica.
Para os alunos do curso de Ciência da Computação, ela é equivalente a ICP518 - Teoria de Grafos. A equivalência é automática.
Para os alunos de Engenharia de Computação e Informação, ela é equivalente a COS741 - Teoria dos Grafos (3 créditos, e é necessário abrir processo com a solicitação). Não é equivalente a disciplina Teoria dos Grafos obrigatória da ECI.
Se você é aluno de outro curso não listado aqui e deseja cursar esta disciplina, veja com seu coordenador, ou diretamente com a professora, sobre quais as possibilidades para a inscrição ser efetivada e como ela será contada em seu curso.
Página atualizada em 19 ago 2023 por Márcia R. Cerioli