MAB518, Teoria de Grafos

2017/2, Bacharelado em Ciência da Computação - em Matemática - 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. Coloração de vértices: Teorema de Brooks, algoritmo guloso e suas consequências
  9. Coloração de arestas: Teorema de Vizing
  10. grafos planares: número limitado de arestas, enunciado do Teorema de Kuratowsky
  11. Coloração de grafos planares e periplanares
  12. Algum outro tópico a escolha dos alunos

Ementa (formal, do SIGA):

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

Pré-requisitos:

MAB 368 - Algoritmos e Grafos (formal).
Obs.: Se você está interessado em cursar Teoria dos Grafos e não cursou MAB 368, entre em contato com a professora. Este curso é recomendado mas não é essencial e, dependendo do caso, pode ser dispensado. Porém, como é pré-requisito formal precisa de uma dispensa formal. O objetivo desde pré-requisito é que o aluno tenha alguma formação em provas formais, definições e teoremas, e já tenha alguma formação matemática.

Atenção alunos da Engenharia: MAB518 Teoria de Grafos não é equivalente a disciplina Teoria de Grafos do ECI. A equivalência que vale com Teoria dos Grafos do ECI é MAB368 Algoritmos e Grafos. MAB518 pode ser disciplina eletiva do ECI mas isto precisa ser acordado previamente


Página atualizada em 10 jul 2017 por Márcia R. Cerioli