COS742 e MAE478 - Teoria dos Grafos

2026/1
Professora Márcia R. Cerioli, Instituto de Matemática - UFRJ

Motivação

A Teoria dos Grafos, um dos ramos da Matemática Discreta, passou a ser uma área reconhecida e desenvolvida junto com o progresso da Ciência da Computação, nas últimas décadas. Porém, teve início muito antes, como resultados teóricos motivados por jogos e quebra-cabeças. Atualmente, estes mesmos resultados clássicos são a base de toda a evolução e resolução de problemas algorítmicos e de otimização combinatória, constituindo um dos grandes ramos da matem´atica e em franco desenvolvimento.

Objetivos:

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

Programa em 2026:

Cada item corresponde ao conteúdo de uma semana de aulas, aproximadamente.
  1. Conceitos, definições e notações básicas de grafos
  2. Teoremas de caracterização de árvores
  3. Conectividade (cortes de vértices e de arestas)
  4. Teorema de Euler - grafos eulerianos. Ciclos e Grafos Hamiltonianos: Condição necessária, Teorema de Ore e Teorema de Dirac
  5. Emparelhamentos: Teorema de Berge. Emparelhamentos em grafos bipartidos: Teorema de Hall. Emparelhamentos perfeitos.

  6. Coberturas e conjuntos independentes. Teorema de Konig.
  7. Coloração de arestas: Teorema de Vizing
  8. Coloração de vértices: Teorema de Brooks, algoritmo guloso e suas consequências
  9. Grafos planares: número limitado de arestas, Teorema de Kuratowsky
  10. Coloração de grafos planares e periplanares
  11. Grafos direcionados e torneios

  12. Números de Ramsey
  13. Algum outro tópico a escolha dos alunos

Ementa (formal, do SIGA):

COS742 Conceitos básicos. árvores. Conectividade. Ciclos Eulerianos e Hamiltonianos. Emparelhamentos. Coloracão de vértices e de arestas. Planaridade.

MAE478 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 quinto período, tendo obtido aprovação em boa parte das disciplinas dos primeiros anos.

Informações importantes:

COS742 é uma das Disciplinas Introdutórias do Mestrado em Engenharia de Sistemas e Computaçã da UFRJ. É altamente recomendada para os alunos da linha de Algoritmos e Combinatória e é oferecida uma vez ao ano. As vezes no período 1 e as vezes, no 2.

MAE478 é uma das Disciplinas Optativas (Escolha Condicionada) da grade do curso de Bacharelado em Matemática, ênfase em Matemática Computacional, de Engenharia Matemática e de Matemática Aplicada, ênfase em Computação Científica.

Para os alunos do curso de Ciência da Computação, MAE478 é equivalente a ICP518 - Teoria de Grafos mas é recomendado verificar o que é necessário com a coordenação do curso para efetivar a equivalência.

Para os alunos de Engenharia de Computação e Informação, COS742 - Teoria dos Grafos (eletiva, 3 créditos, 45 horas) faz parte da lista das eletivas já previstas no curso e que também contribuiem para os créditos no futuro mestrado no PESC. A inscrição é direto via SIGA na aba de disciplinas da pós-graduação, via requerimento. Observem que o calendário de inscrição pode ser diferente do da graduação. Não é necessário abrir processo com a solicitação de equivalência.
Alternativamente, alunos de ECI podem se inscrever em MAE478 (4 créditos, 60 horas) mas assim ela será contabilizada como eletiva livre.
Atenção: Ela não é equivalente a disciplina obrigatória COS242 Teorias 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 5 mar 2026 por Márcia R. Cerioli