Enginyeria Tècnica en Informàtica de Gestió - Segon curs

Objectiu genèric de l’assignatura: Introduir un conjunt d’eines formals, basades en els grafs, per a la representació i l’anàlisi de problemes d’optimització. Estudiar algunes de les propietats bàsiques dels tipus principals de grafs per tal de poder-les aplicar a la resolució de problemes pràctics. Mostrar una alternativa algorísmica rigorosa a la resolució intuïtiva (i sovint errònia) de problemes tan senzills d’enunciar com difícils de resoldre. Introduir des d’un punt de vista aplicat a l’anàlisi algorísmica (complexitat d’un algorisme) i la teoria de la complexitat (problemes tractables, intractables, etc.).

Introduir el model de graf, conèixer els tipus de grafs més usuals i algunes de les seves propietats. Existència de grafs amb una seqüència de graus fixada. Grafs plans. Arbres camins i connectivitat. Seqüències  de Prüfer. Algorismes bàsics de grafs que produeixen un arbre generador: BFS, DFS, Dijkstra, Prim, Ford. Algorismes semblants per a resoldre problemes diversos. Anàlisi de la complexitat dels algorismes. Circuits hamiltonians i circuits eulerians: problemes tan semblants, però tan diferents, tractabilitat i intractabilitat. El problema del carter xinès i el problema del viatjant. Coloració de vèrtexs. Tot mapa es pot pintar amb 4 colors.