Saltar para:
Logótipo
Você está em: Início > M3026
Mapa das Instalações
FC6 - Departamento de Ciência de Computadores FC5 - Edifício Central FC4 - Departamento de Biologia FC3 - Departamento de Física e Astronomia e Departamento GAOT FC2 - Departamento de Química e Bioquímica FC1 - Departamento de Matemática

Combinatória e Grafos

Código: M3026     Sigla: M3026

Áreas Científicas
Classificação Área Científica
OFICIAL Matemática

Ocorrência: 2024/2025 - 2S Ícone do Moodle

Ativa? Sim
Unidade Responsável: Departamento de Matemática
Curso/CE Responsável: Licenciatura em Matemática

Ciclos de Estudo/Cursos

Sigla Nº de Estudantes Plano de Estudos Anos Curriculares Créditos UCN Créditos ECTS Horas de Contacto Horas Totais
L:B 0 Plano de Estudos Oficial 3 - 6 48 162
L:CC 0 Plano estudos a partir do ano letivo 2021/22 2 - 6 48 162
3
L:F 0 Plano de Estudos Oficial 3 - 6 48 162
L:G 0 Plano estudos a partir do ano letivo 2017/18 2 - 6 48 162
3
L:M 30 Plano de Estudos Oficial 3 - 6 48 162
L:MA 4 Plano de Estudos Oficial 3 - 6 48 162
L:Q 1 Plano estudos a partir do ano letivo 2016/17 3 - 6 48 162

Docência - Responsabilidades

Docente Responsabilidade
Pedro Ventura Alves da Silva Regente

Docência - Horas

Teorico-Prática: 3,69
Tipo Docente Turmas Horas
Teorico-Prática Totais 1 3,692
Pedro Ventura Alves da Silva 3,692

Língua de trabalho

Português

Objetivos




Familiarizar-se com vários conceitos e técnicas da combinatória, com ênfase na teoria dos grafos e combinatória enumerativa.




Resultados de aprendizagem e competências

Capacidade de resolver problemas na área. Autonomia na resolução de exercícios.

Modo de trabalho

Presencial

Programa






  1. NOÇÕES BÁSICAS DE TEORIA DE GRAFOS: isomorfismo, passeios, subgrafos, conexidade, circuitos eulerianos, grafos bipartidos.




  2. COMBINATÓRIA ENUMERATIVA: relações de recorrência, funções geradoras, per- mutações, desarranjos, involuções, números de Catalan, números de Bell.




  3. PRINCÍPIO DA INCLUSÃO-EXCLUSÃO: O Princípio e suas aplicações, números de Stirling de primeira e de segunda espécie.




  4. GRAFOS E MATRIZES: matriz de adjacência, matriz de incidência, polinómio mínimo e espectro de um grafo, espectro de um grafo bipartido.




  5. ÁRVORES: florestas e árvores, caraterizações alternativas, Teorema de Cayley, árvores geradoras.




  6. COLORAÇÕES: coloração dos vértices de um grafo, polinómio cromático e número cromático, grafos críticos.




  7. GRAFOS PLANARES: Fórmula de Euler, critérios para a planaridade, caraterizações envolvendo menores, Teorema das Cinco Cores.




  8. EMPARELHAMENTOS: Teorema dos Casamentos, sistemas de representantes, ma- trizes duplamente estocásticas, emparelhamentos perfeitos, Teorema de Tutte.




  9. CICLOS HAMILTONIANOS: Teorema de Ore, condições necessárias para a existência de um ciclo hamiltoniano.






Bibliografia Obrigatória

Sebastian M. Cioabc483; A first course in graph theory and combinatorics. ISBN: 978-81-85931-98-2

Bibliografia Complementar

J. A. Bondy; Graph theory. ISBN: 978-1-84628-969-9

Métodos de ensino e atividades de aprendizagem




Exposição pelo docente, discussão de exercícios. São disponibilizadas folhas de exercícios e outros materiais de apoio às aulas na página da disciplina no Sigarra.




Tipo de avaliação

Avaliação distribuída com exame final

Componentes de Avaliação

Designação Peso (%)
Teste 100,00
Total: 100,00

Componentes de Ocupação

Designação Tempo (Horas)
Estudo autónomo 114,00
Frequência das aulas 48,00
Total: 162,00

Obtenção de frequência

Sem requisitos.

Fórmula de cálculo da classificação final

A matéria desta UC será dividida em duas partes, cada uma avaliada por um teste cotado para 10 valores.

O segundo teste realiza-se na altura marcada para o exame da época normal. No mesmo dia, haverá a possibilidade de repetição do primeiro teste, prevalecendo a nota aí obtida para os estudantes que assim o decidam.

Época normal:

1. A classificação final da época normal é a soma das classificações dos dois testes, excepto eventualmente no seguinte caso.

2. Notas superiores a 18 só serão concedidas após a realização de uma prova complementar (oral ou escrita).

Época de recurso:

1. No exame da época de recurso os estudantes podem repetir novamente os dois testes ou somente um deles (exceto nos casos de melhoria).

2.A classificação de um (mas só um) dos testes poderá ser substituída a posteriori pela classificação obtida no teste correspondente da época normal, na versão mais favorável ao estudante (exceto nos casos de melhoria).

3. A classificação final da época de recurso será a soma das classificações dos 2 testes, arredondada à unidade, excepto eventualmente nos casos considerados a seguir.

4. Os alunos que tenham obtido uma classificação igual ou superior a 8,0 valores e inferior a 9,5 valores terão acesso a uma prova complementar para decidir sobre a sua aprovação (com 10 valores) ou reprovação (com 8 ou 9 valores).

5. Notas superiores a 18 só serão concedidas após a realização de uma prova complementar (oral ou escrita).

Avaliação especial (TE, DA, ...)

Os exames requeridos ao abrigo de estatutos especiais constarão de uma prova escrita que poderá ser precedida de uma prova oral eliminatória, para avaliar se o aluno está em condições mínimas de tentar obter aprovação à disciplina na prova escrita.

Melhoria de classificação

Nos casos de melhoria, não é possível aproveitar classificações parciais obtidas previamente.
Recomendar Página Voltar ao Topo
Copyright 1996-2025 © Faculdade de Ciências da Universidade do Porto  I Termos e Condições  I Acessibilidade  I Índice A-Z  I Livro de Visitas
Página gerada em: 2025-06-15 às 00:20:42 | Política de Utilização Aceitável | Política de Proteção de Dados Pessoais | Denúncias