Regime: Semestral – S2

Categoria: Nuclear

Horário Semanal: 3 horas

Assistindo-se a um crescente interesse pela Teoria de Grafos, nomeadamente no capítulo das suas aplicações à Física, Química, Ciência de Computadores, Engenharia da Comunicação, Arquitectura, Investigação Operacional, etc, pretende-se, com este curso, dotar os alunos de um suporte teórico forte, grande capacidade de análise de problemas, sua representação gráfica e resolução através de teoremas e propriedades dos grafos.

Será adoptado o regime de avaliação contínua. Os conhecimentos do aluno serão certificados através da realização de um teste escrito cuja data será marcada pelo docente no início do semestre e abrangendo a totalidade do programa. Os alunos terão ainda a possibilidade de realizar um trabalho a ser entregue até ao último dia de aulas e que poderá ponderar com a nota do teste. Cada trabalho prático terá uma valoração máxima de 5 valores ficando nesse caso o exame cotado para 15 valores.

0. Apresentação

1. Lógica Básica

1.1 Proposições

1.2 Implicações e equivalências

1.3 Quantificação

2. Conjuntos

2.1 Definição de conjunto

2.2 O conjunto vazio

2.3 Subconjuntos

2.4 Operações boloeanas em conjuntos

2.5 Produto cartesiano de conjuntos

3. Relações binárias

3.1 Relações reflexivas, simétricas, anti-simétricas e transitivas

3.2 Relações de equivalência

3.3 Ordens parciais

4. Funções

4.1 Definição de função

4.2 Isomorfismo

4.3 Cardinalidade de um conjunto

5. Grafos

5.1 Problema das pontes de Königsberg

5.2 Definição de Grafo

5.3 Notação

5.4 Subgrafo

5.5 Grafo completo

5.6 Grafo bipartido

5.7 Propriedades básicas de grafos

5.8 Equivalência de Grafos

6. Caminhos e circuitos

6.1 Circuitos Eulerianos

6.2 Ciclos Hamiltonianos

7. Matriz de Adjacências

8. Algoritmos de "caminho mais curto"

9. Aplicações de Grafos

9.1 Problema do Carteiro Chinês

9.2 Torneios

9.3 Problemas de Calendarização

10. Aplicações de "Depth-first Search"

10.1 Definição e algoritmo

10.2 Exemplos

11. Grafos planares e colorações

11.1 Definições

11.2 Propriedades

11.3 Problema das 4 e 5 cores

Goodaire, Edgar; Parmenter, Michael – Discrete Mathematics with Graph Theory – Prentice-Hall, 1998, ISBN: 0-13-602079-8

Harary, Frank – Graph Theory – Perseus Books, 1969, 10ª impressão 1998, ISBN: 0-201-41033-8

Trudeau, Richard J. – Introduction to Graph Theory – Dover Publications, 1993, ISBN: 0-486-67870-0

Balakrishnan, V.K. – Graph Theory – McGraw-Hill, Shaum’s Outlines, 1997, ISBN: 0-07-005489-4

 

 

Apresentação

Horas Previstas: 2

Bibliografia: -

Lógica Básica

Horas Previstas: 3

Bibliografia: [1]

Conjuntos

Horas Previstas: 3

Bibliografia: [1]

Relações binárias

Horas Previstas: 3

Bibliografia: [1]

Funções

Horas Previstas: 3

Bibliografia: [1]

Grafos

Horas Previstas: 9

Bibliografia: [1,2,3]

Caminhos e circuitos

Horas Previstas: 6

Bibliografia: [1,2,3,4]

Matriz de Adjacências

Horas Previstas: 3

Bibliografia: [1,4]

Algoritmos de caminho mais curto

Horas Previstas: 3

Bibliografia: [1,4]

Aplicações de Grafos

Horas Previstas: 6

Bibliografia: [1]

Aplicações de "Depth-first Search"

Horas Previstas: 3

Bibliografia: [1,4]

Grafos planares e colorações

Horas Previstas: 3

Bibliografia: [1,2,4]

 

O restante das horas será dedicado à realização de trabalhos práticos e á revisão para a avaliação final.

Segundas feiras das 16h00 às 19h00

Lógica básica: proposições, operadores, quantificação. Conjuntos: definição, conjunto vazio, subconjuntos, operações booleanas, produto cartesiano. Relações binárias: tipos de relações, relações de equivalência, ordens parciais. Funções: definição, isomorfismo, cardinalidade. Grafos: definição, subgrafo, grafo completo, grafo bipartido, propriedades, equivalência de grafos. Caminhos e circuitos: Eulerianos, Hamiltonianos. Matriz de adjacências. Algoritmos de caminho mais curto. Aplicações: carteiro chinês, torneios, calendarização. Aplicações "depth-first search". Grafos planares e colorações: definição, propriedades, o problema das 4 e 5 cores.

Logic: statements, operators, quantifiers. Sets: definition, the empty set, subsets, boolean operations on sets, cartesian producto of sets. Binary relations: types of relations, equivalence relations, partial orders. Functions: definition, isomorphism, cardinality of a set. Graphs: definition, subgraph, complete graph, bipartite graph, properties, equivalence of graphs. Paths and circuits: Eulerian, Hamiltonian. The adjacency matrix. Shortest path algorithms. Applications of graphs: chinese postman, tournaments, scheduling. Depth-first search applications. Planar graphs and colorings: definition, properties, the 4 and 5 color problem.