Enginyeria en Informàtica (3371)

Àlgebra i Matemàtica Discreta II(12404) 

Introducció

Aquesta assignatura és una introducció a la Teoria de Grafs. A partir del plantejament d'una sèrie d'exemples, introduim alguns elements i problemes bàsics de la teoria de grafs. S'estudien circuits recobridors i coloració de grafs. Arbres. Camins de cost mínim. Elements de combinatòria.

Temari

Tema 1: Elements de teoria de grafs.

Tema 2: Circuits recobridors i coloració de grafs.

Tema 3: Arbres.

Tema 4: Camins de cost mínim.

Tema 5: Elements de combinatòria.

Pràctiques

Les pràctiques consten de la realització d'exercicis i també d'una pràctica final.
 

Mètode d'avaluació

La qualificació de l'assignatura es composa de: - 70% de la qualificació de l'exàmen Teòrico-pràctic, basat bàsicament en exercicis. - 30% de la qualificació de la pràctica final. Per poder fer la mitjana, cal tenir les dues parts aprovades amb una nota superior o igual a 5.  

Observacions

Es recomana haver cursat Àlgebra i Matemàtica Discreta I (12402)  

Bibliografia

R. BHARATH, Computers and Graph Theory,Ellis Horwood, 1991.

J. FÀBREGA, Teoria de Grafs,Edicions de la UPC, 1997.

J.R. EVANS, E. MINIEKA, Optimization algorithms for networks and graphs, Marcel Dekker, 1992.

Bibliografia complementària

J.M. BASART i MUÑOZ, Grafs: Fonaments i Algorismes,Manuals de la UAB, 13, 1994.

J.M. BRUNAT BLAY, Combinatoria i Teoria de Grafs,Edicions de la UPC.

X. FRANCH GUTIÉRREZ, Estructuras de Datos, Edicions UPC, 1994.

J. GIMBERT, R. MORENO, J.M. RIBÓ i M. VALLS, Apropament a la Teoria de Grafs i als seus Algorismes, EINES 23, 1998.