CONTEUDOTGa439154 (1)

Prévia do material em texto

CURSO: Bacharelado em Sistemas de Informação 
COORDENAÇÃO: Prof. Me. Antônio Carlos Marques do Amaral Guerra 
ANO LETIVO: 2021 
Prof. Dr. Paulo Roberto Schroeder de Souza. 
 
CÓDIGO NOME 
 Teoria dos Grafos 
 
CARGA HORÁRIA SEMESTRAL SEMESTRE 
36 h.a. 5º 
 
OBJETIVOS: 
• Introduzir conceitos sobre da Teoria de Grafos e aplicar na avaliação e resolução de problemas 
característicos. 
• Proporcionar conhecimento da Teoria de Grafos e aplicar estes conhecimentos na avaliação e 
resolução de problemas característicos. 
 
EMENTA: 
• Introdução à Teoria dos Grafos. 
• Problemas de coloração. Ciclos e aplicações. Grafos planares. 
 
CONTEÚDO PROGRAMÁTICO: 
• Conceitos básicos de grafos 
o Introdução; 
o Grafo simples; 
o Grafo rotulado; 
o Grafo valorado; 
o Grafo completo; 
o Vértices e arestas adjacentes; 
o Grau de um vértice e cardinalidade; 
o Grafo conexo; 
o Subgrafo; 
o Grafo orientado. 
• Representação Matricial de um grafo. 
o Matriz de aresta; 
o Matriz de incidência (para um grafo não orientado); 
o Matriz de incidência (para um grafo orientado); 
o Matriz de adjacência. 
• Caminhos em grafos 
o Passeio (walk); 
o Caminho simples (path); 
o Trilha (trail); 
o Grafos Eulerianos; 
o Grafos Hamiltonianos. 
• Problemas de coloração 
o Definição; 
o Coloração mínima; 
o Polinômio Cromático; 
o Teoremas Básicos. 
• Conexidade em Grafos 
o Recordação; 
o Grafo reduzido; 
o Algoritmo de Malgrange; 
o Processo Iterativo 
• Ciclos e aplicações 
o Problemas eulerianos em grafos não orientados; 
o O problema do carteiro chinês; 
o Problemas eulerianos em grafos orientados; 
o Problemas hamiltonianos; 
o O problema do caxeiro-viajante; 
• Grafos planares 
o Definições e resultados simples; 
o Teorema de Kuratowski; 
o Dualidade; 
o Problema das 4 cores. 
 
METODOLOGIA DE ENSINO: 
• Aulas expositivas (Ae): Durante estas aulas será dada ênfase aos atributos relevantes de cada 
tópico do conteúdo, para que haja formação do conceito. As aulas expositivas são os conteúdos 
expostos direto na lousa; 
• Atividades práticas (Ap): Constitui atividades práticas, qualquer tarefa designada pelo professor 
ao aluno, visando sempre alcançar os objetivos propostos para o curso. 
• O desenvolvimento das atividades se dará fora ou dentro da Universidade. 
 
CRITÉRIOS DE AVALIAÇÃO: 
• Avaliação bimestral (Ab) - (individual, escrita e agendada pela UNISANTA). valor: (0 a 8,0) 
• Atividade prática (Ap) - (Agendada pelo professor) valor: (0 a 2,0). 
• Média bimestral (Mb) = ( Ab + Ap) 
 
SALAS ESPECIAIS E LABORATÓRIOS UTILIZADOS: 
• Não se aplica 
 
BIBLIOGRAFIA BÁSICA: 
• BOAVENTURA NETTO, P. O.; JURKIEWICZ, S. Grafos – Introdução e Prática. 1. ed. São 
Paulo: ed. Edgard Blucher, 2009. 
• BOAVENTURA NETTO, P. O. Grafos: Teoria, Modelos e Algoritmos. 4. ed. São Paulo: ed. 
Edgard Blucher, 2006. 
• SIMÕES-PEREIRA, J. M. S. Grafos e Redes - Teoria e Algoritmos Básicos. 1.ed. Editora 
Interciência, 2014. 
 
BIBLIOGRAFIA COMPLEMENTAR: 
• PEREIRA, J. S. S. Matemática Discreta: Grafos, Redes, Aplicações, Coimbra: ed. Luz da 
vida, 2009. 
• CARDOSO, D. M. Matemática Discreta: Combinatória – Teoria dos Grafos – Algoritmos. 
ed. Escolar Editora, 2009. 
• BONDY, J. A.; MURTY, U. S. R. Graph Theory. Graduate Texts in Mathematics, vol. 244. 
Springer, 2008. 
• HARRIS, J. M.; HIRST, J. L.; MOSSINGHOFF, M. J. Combinatorics and Graph Theory, 
Springer Science+Business Media, LLC, second edition, 2008. 
• TENENBAUM, A. M.; LANGSAM, Y.; AUGENSTEIN, M. J. Estruturas de Dados Usando C. 1. 
ed. São Paulo: ed. Makron Books, 2000.