Teoria dos Grafos

Programa

Introdução e Motivação ao estudo da Teoria dos Grafos
Revisão da Teoria dos Conjuntos
Conceitos Fundamentais
Isomorfismo, Automorfismo e Homomorfismo
Planaridade
Passeios Eulerianos
Caminhos Hamiltonianos
Árvores
Algoritmos de Busca em Árvores
Complexidade de Algoritmos de Grafos
Emparelhamento
Coloração de Grafos (Arestas)
Conjuntos Independentes e Cliques
Fluxo em Redes
Grafos Direcionados
Bibliotecas computacionais para suporte a grafos em linguagens de programação populares
Aplicações de Grafos em Computação

Sistema de Avaliação (Notas)

A avaliação da disciplina será composta por duas provas escritas, individuais e sem consulta (P1 e P2) valendo 100 (cem) pontos cada. Pontos extra (PE) poderão ser eventualmente computados. A média do semestre (MS) será computada de acordo com a equação abaixo:

Provas substitutivas serão aplicadas para os casos previstos nas normas de graduação.

Para alunos que obtiverem média do semestre no intervalo [20,59] e possuírem frequência suficiente será ofertada uma prova de recuperação (REC) valendo 100 pontos. A nota final (NF) após a prova de recuperação será calculada de acordo com a fórmula abaixo:

nota final do semestre

Atendimento

• Dúvidas podem ser solucionadas via e-mail a qualquer momento: abdala@ufu.br

• Dúvidas também podem ser solucionadas presencialmente nos seguintes horários:

– SEG: 14:50h ~ 17:40h

– TER: 13:10h ~ 14:50h

– QUA: 14:50h ~ 17:40h

• Requer-se agendamento prévio para atendimento presencial. Um simples e-mail para o endereço acima citado basta.

• Uma confirmação de agendamento será enviada.

• Atendimento de dúvidas não é o mesmo que aula particular de reposição!

• Notas das avaliações serão afixadas na porta do gabinete do professor (1B121) dentro do período previsto nas normas de graduação

Listas de Exercícios

Lista1 - Conceitos Básicos, Isomorfismo, Automorfismo, Homomorfismo e Planaridade
Lista 2

Exercícios Extra

Extra 2 - Isomorfismo

Páginas de Interesse

GraphTea	Open Source - GLP Ótima ferramenta. Permite a criação de vários tipos de grafos automaticamente, fácilidade em criar e editar grafos quaisquer e implementa ainda vários algoritmos clássicos em teoria dos grafos. Em suma uma boa opção para acompanhar sua caminhada pelo maravilhoso mundo dos grafos.
SageMath	SageMath é um ambiente baseado em Python que tem como objetivo prover uma alternativa a softwares como Matlab e Mathematica. Ele é fácil de usar e possui dentre outras, uma extensa biblioteca de funções e suporte a teoria dos grafos.
Sarada Herke	Sarada Herke é uma professora de matemática na Austrália. Ela edita um canal no youtube sobre teoria dos grafos. O material é correto e de fácil entendimento. As explicações são diretas e simples e populadas por exemplos. Provavelmente este é o melhor canal sobre Teoria dos Grafos disponível no Youtube.
Networks, Crowds, and Markets	Livro Free online Escrito por David Easley e Jon Kleinberg. Ele possui um capítulo introdutório sobre grafos. De um modo geral um ótimo livro. Nosso interesse nele recai no aspecto de como utilizar grafos para resolver problemas, em especial, problemas em redes de computadorese redes sociais.
Graphs and Networks	Curso sobre teoria dos grafos ministrado por Dan Spielman. em Yale. As notas de aula são muito boas.

OBS: Caso vocês encontrem outros links para material online do qual não estão certos de sua corretude, por favor enviem os links para meu e-mail que eu os verificarei.

UFU

volta para home

FACOM