|
Objectius
|
|
|
|
Introduir a l'alumne en la modelització i resolució de problemes mitjançant la teoria de grafs |
|
|
|
|
|
|
Contingut (Programa)
|
|
|
1.- Introducció a la teoria de grafs. (Temporalització: 10 h.)
1.1 Definicions bàsiques.
1.2 Com es guarda un graf en memòria.
1.3 Recorregut d'un graf.
1.4 Connexió i components.
1.5 Planaritat.
1.6 Coloració de Grafs. El polinomi cromàtic.2.- Arbres i camins mínims. (Temporalització: 5 h.)
2.1 Camins mínims entre dos vèrtexs d'un graf.
2.2 Camí mínim entre qualsevol parella de vèrtexs.
3.- Arbres. (Temporalització: 5 h.)
3.1 Definicions i propietats dels arbres.
3.2 Arbre generat. generació de tots els arbres d'un graf.
3.3 Arbres generats de cost mínim.4.- Xarxes de transport. (Temporalització: 7 h.)
4.1 Definicions i propietats
4.2 Mètode del Flux-màxim Tall-mínim
4.3 Variacions del problema del flux màxim
4.4 Minimització del cost per a un flux fixat5.- Camins i circuits Eulerians i Hamiltonians. (Temporalització: 7 h.)
5.1 Caracterització dels camins i dels circuits eulerians.
5.2 Obtenció d'un circuit eulerià.
5.3 El problema del carter xinès.
5.4 Caracterització dels camins i dels circuits hamiltonians.
5.5 Obtenció de camins hamiltonians. |
|
|
|
|
Bibliografia
|
|
|
Bibliografia bàsica a utilitzar durant el curs.
- BASART, J.M.: Grafs, fonaments i algorismes. Manuals UAB núm. 13
- GONDRAN, M. & MINDUZ, M.: Graphs and algorithms. Wiley Interscience (1994)
- GARCÍA MERAYO: Problemas resueltos de matemática discreta. Thomson (2003) |
|
|
|
|
Mètodes docents
|
|
|
Classes de teoria i problemes: 3.5 crèdits
Pràctiques:1 crèdit |
|
|
|
|
|
|
|
|
|
La bibliografia a la biblioteca