Curso
– Ano: Engenharia da
Comunicação – 4º Ano
Regime: Semestral – S2
Categoria: Nuclear
Horário
Semanal: 4 horas
Enquadramento e Objectivos da
Disciplina:
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.
Sistema de Avaliação
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
Cadeias de RNA
9.3
Torneios
9.4
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
Bibliografia
[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
Distribuição dos Tempos Lectivos
e da Bibliografia
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
Horas Previstas: 6
Bibliografia: [1,2,4]
O restante das horas será dedicado à realização de trabalhos práticos e
á revisão para a avaliação final.
Horário de Atendimento ao Aluno:
A definir
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.