Curso – Ano: Engenharia da Comunicação – 4º Ano

Regime: Semestral (2º semestre)

Horário Semanal: 4 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.

A classificação final de cada aluno será obtida pela escolha da melhor nota entre a correspondente à do exame final e a ponderada entre a do exame final e notas de um ou mais trabalhos práticos. Os alunos que escolham realizar trabalhos práticos poderão portanto ver a classificação desses trabalhos como parte integrante da classificação final. Cada trabalho prático terá uma valoração máxima de 3 valores (com um máximo de 2 trabalhos práticos), ficando nesse caso o exame cotado para 14 valores.

Para se poder optar entre as 2 melhores notas é condição necessária que o aluno tenha efectivamente realizado os trabalhos práticos.

0. Apresentação
0. Lógica Básica

1. Proposições
1. Implicações e equivalências
1. Quantificação

0. Conjuntos

1. Definição de conjunto
1. O conjunto vazio
1. Subconjuntos
1. Operações boloeanas em conjuntos
1. Produto cartesiano de conjuntos

0. Relações binárias

1. Relações reflexivas, simétricas, anti-simétricas e transitivas
1. Relações de equivalência
1. Ordens parciais

0. Funções

1. Definição de função
1. Isomorfismo
1. Cardinalidade de um conjunto

0. Grafos

1. Problema das pontes de Königsberg
1. Definição de Grafo
1. Notação
1. Subgrafo
1. Grafo completo
1. Grafo bipartido
1. Propriedades básicas de grafos
1. Equivalência de Grafos

0. Caminhos e circuitos

1. Circuitos Eulerianos
1. Ciclos Hamiltonianos

0. Matriz de Adjacências
0. Algoritmos de "caminho mais curto"
0. Aplicações de Grafos

1. Problema do Carteiro Chinês
1. Cadeias de RNA
1. Torneios
1. Problemas de Calendarização

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

1. Definição e algoritmo
1. Exemplos

0. Grafos planares e colorações

1. Definições
1. Propriedades
1. Problema das 4 e 5 cores

1. Goodaire, Edgar; Parmenter, Michael – Discrete Mathematics with Graph Theory – Prentice-Hall, 1998, ISBN: 0-13-602079-8
2. Harary, Frank – Graph Theory – Perseus Books, 1969, 10ª impressão 1998, ISBN: 0-201-41033-8
3. Trudeau, Richard J. – Introduction to Graph Theory – Dover Publications, 1993, ISBN: 0-486-67870-0
4. Balakrishnan, V.K. – Graph Theory – McGraw-Hill, Shaum’s Outlines, 1997, ISBN: 0-07-005489-4

0. Apresentação

Horas Previstas: 2

Bibliografia: -

1. Lógica Básica

Horas Previstas: 2

Bibliografia: [1]

2. Conjuntos

Horas Previstas: 4

Bibliografia: [1]

3. Relações binárias

Horas Previstas: 2

Bibliografia: [1]

4. Funções

Horas Previstas: 4

Bibliografia: [1]

5. Grafos

Horas Previstas: 10

Bibliografia: [1,2,3]

6. Caminhos e circuitos

Horas Previstas: 4

Bibliografia: [1,2,3,4]

7. Matriz de Adjacências

Horas Previstas: 2

Bibliografia: [1,4]

8. Algoritmos de caminho mais curto

Horas Previstas: 2

Bibliografia: [1,4]

9. Aplicações de Grafos

Horas Previstas: 12

Bibliografia: [1]

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

Horas Previstas: 2

Bibliografia: [1,4]

11. Grafos planares e colorações

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

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, cadeias de RNA, 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, RNA chains, tournaments, scheduling. Depth-first search applications. Planar graphs and colorings: definition, properties, the 4 and 5 color problem.