Ir para o conteúdo
BETA

Portal de Informações Institucionais

Universidade Federal de Pelotas

Nome da Disciplina
ANÁLISE COMBINATÓRIA E TEORIA DOS GRAFOS
CÓDIGO
1110181
Carga Horária
68 horas
Atividade Complementar
Não
Periodicidade
Semestral
Modalidade
CRÉDITOS
4
CARGA HORÁRIA TEÓRICA
4
CARGA HORÁRIA OBRIGATÓRIA
4
FREQUÊNCIA APROVAÇÃO
75%

Ementa

Grafos: Representação,Conectividade, Planaridade, Coloração e Árvores. Análise Combinatória: Princípios da Contagem, Técnicas de Contagem em Permutações e Combinações, Simples e com Repetição. Teorema Binomial.

Objetivos

Objetivo Geral:

Capacitar os alunos com os conceitos teóricos a respeito de grafos e de análise combinatória.

Conteúdo Programático

1. Grafos: definição, representação, terminologia de elementos de grafos.
• Grafos dirigidos, subgrafos, classificações, propriedades, caminhos, circuitos.
• Homomorfismos e isomorfismos de grafos.
• Planaridade.
• Árvores: definição, representação, classificações. Algoritmos de percurso e árvores de pesquisa.
2. Análise Combinatória.
• Princípios: aditivo e multiplicativo, da inclusão e exclusão, da casa dos pombos.
• Permutações e Combinações: simples e com repetição.
• Permutações circulares,
• Números binomiais, funções geradoras.

Bibliografia

Bibliografia Básica:

  • GOLDBARG, M., GOLDBARG, E. Grafos: Conceitos, Algoritmos e Aplicações. Rio de Janeiro: Elsevier, 2012.
  • ROSEN, K. H. Matemática Discreta e Suas Aplicações, McGraw Hill, 2009.
  • GERSTING, J. L. Fundamentos Matemáticos para Ciência da Computação. Rio de Janeiro: LTC, 2004
  • SZWARCFILER, Jaime. L. Grafos e Algoritmos Computacionais. Rio de Janeiro: Campus, 1988.

Bibliografia Complementar:

  • BONDY, J. A.,MURTY, U. S.R., Graph Theory, Springer, 2008.
  • HAZAN, S. Fundamentos da matemática elementar: combinatória e probabilidade. São Paulo: Atual, 2004.
  • BOAVENTURA NETTO, P.O. Grafos: teoria, modelos, algoritmos. São Paulo: Editora Edgard. Blücher, 4a ed., 2006. 313 p.
  • DIESTEL, R. Graph theory. New York: Springer, 2000.
  • THULASIRAMAN, K., SWAMS, M. N. S. Graphs: theory and algorithms. New York: John-Wiley & Sons, 1992.
  • WEST, D. B. Introduction to Graph Theory. Upper Saddle River: Pretice-Hall, 1996.
  • SZWARCFILER, Jaime. L. Grafos e Algoritmos Computacionais. Rio de Janeiro: Campus, 1988.
  • SANTOS, J. P. O., MELLO M. P., MURARI, I. T. C. Introdução à análise combinatória, Campinas: Unicamp, 2002.
  • GRAVER, J. E., WATKINS, M. E. Combinatorics with emphasis on the theory of graphs. New York: Springer - Verlag, 1977.
  • PRATER, R. – Discrete Mathematical Structures for Computer Science, Editora Houghton Mifflin, 1976

Turmas Ofertadas

Turma Período Vagas Matriculados Curso / Horários Professores
T1 2017 / 2 51 50 Ciência da Computação
SEG (08:00-08:50) SEG (08:50-09:40) QUA (15:10-16:00) QUA (16:00-16:50)
HORASEGTERQUAQUISEXSAB
08:00X
08:50X
10:00
10:50
11:40
12:30
13:30
14:20
15:10X
16:00X
16:50
17:10
18:00
RENATA HAX SANDER REISER
Professor responsável pela turma